前缀码 | Codeboy's Blog

形式陈述

设码字母表 $\mathcal D$ 有 $D\ge2$ 个符号。码字集合 $C\subseteq\mathcal D^*$ 称为前缀自由，若对任意不同的 $u,v\in C$ ，都不存在 $w\in\mathcal D^*$ 使

v=uw.

也就是说，任何码字都不是另一不同码字的前缀。把源符号映到 $C$ 就得到一类信源码。在通常的无分隔符串联模型中，前缀自由等价于即时可译：译码器读到一个码字的最后一个符号时即可输出，不需查看下一个码符号。

若码字长度为正整数 $\ell_1,\ldots,\ell_m$ ，每个 $D$ 元前缀码都满足 Kraft 不等式

\sum_{i=1}^mD^{-\ell_i}\le1.

前缀码必然唯一可译，但唯一可译码不必前缀自由。

直觉

把 $\mathcal D^*$ 画成一棵 $D$ 叉树：边标有码字符，根到节点的路径就是一个字。前缀码只能把码字放在叶位置；一旦某节点被选作码字，它的整棵后代子树都不能再放码字。译码时沿输入在树上行走，到叶就输出并回到根。

码长是叶深，因而必须是整数。高概率符号放浅可以降低平均长度，但哪些深度能同时出现受树的容量约束，不能只逐个选择“看起来够短”的长度。

前缀自由保证读到首个叶时不存在“它也许只是更长码字开头”的另一解释，所以首码字唯一。删去这个前缀后对余串重复，得到唯一解析。反过来，若码字 $u$ 是另一代码字 $v$ 的真前缀，读完 $u$ 时必须等待才能判断当前符号是 $u$ 还是 $v$ ，故不可能即时译码。

例子与边界

对二元码

a\mapsto0,\quad b\mapsto10,\quad c\mapsto110,\quad d\mapsto111,

没有码字是另一代码字的前缀。码流 010111 从左到右唯一即时解析为 0|10|111，即 $a,b,d$ 。若概率为 $(0.4,0.3,0.2,0.1)$ ，平均长度为

0.4(1)+0.3(2)+0.2(3)+0.1(3)=1.9\ \text{bit},

而树容量恰好用满：

2^{-1}+2^{-2}+2^{-3}+2^{-3}=1.

$\{0,01\}$ 不是前缀码，因为 0 是 01 的前缀；但它仍唯一可译，这说明“非前缀”不等于“一定歧义”。相反， $\{0,01,10\}$ 的 010 有 0|10 与 01|0 两种解析，连唯一可译也失败。

前缀自由只解决边界解析，不提供纠错能力。一个 bit 翻转可能把译码器带到另一叶并使后续同步丢失。Kraft 和小于一的树仍是合法前缀码，只表示有叶空间未使用；空码字则只有在码本只含一个符号时才可用。

推论与应用

Kraft–McMillan 不等式证明上述长度条件既必要，又足以构造具有这些长度的前缀码。Huffman 编码在有限已知分布的逐符号前缀码中选择最小平均长度的树；无噪声编码定理通过块编码把整数叶深造成的每符号开销降到零。

协议字段、自定界整数和压缩格式也使用前缀结构，但若还要求错误恢复、随机访问或长度上限，就需要额外设计条件；前缀性本身不包含这些保证。

参考资料

Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd ed., Wiley, 2006, §§5.1–5.2.
Robert G. Gallager, Information Theory and Reliable Communication, Wiley, 1968, §3.2.
David J. C. MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003, §§5.1–5.2.