形式陈述

码字集合 $C\subseteq D^*$$C\subseteq D^{\ast }$ 是前缀码，若任意不同 $x,y\in C$$x,y\in C$，$x$$x$ 不是 $y$$y$ 的前缀。前缀码可从左到右即时译码，并必然唯一可译；反向不成立。$D$$D$ 元前缀码的码长满足 Kraft 不等式 $\sum_i D^{-\ell_i}\le1$$\sum _i{D}^{-{\ell }_i}\le 1$。

直觉

一旦读到完整码字，就不可能还需等待后续字符确认它其实是更长码字的开头。

例子与边界

二元码 $\{0,10,11\}$$\{0,10,11\}$ 是前缀码；$\{0,01\}$$\{0,01\}$ 不是，因为 0 是 01 的前缀。前缀树中码字对应叶子，不能把内部节点也当码字。前缀性依赖码字符号串，不是只看码长是否不同。

推论与应用

前缀码用于流式解码、Huffman 编码、协议字段和自定界表示。

参考资料

• Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd ed., Wiley, 2006，Chs. 2–8。
• Claude E. Shannon, “A Mathematical Theory of Communication,” Bell System Technical Journal 27, 1948，Parts I–II。