前缀码

前缀码是一组码字，其中任何码字都不是另一个不同码字的开头部分，即前缀。当信源符号被赋予满足这一条件的不同码字时，编码序列就可以从左到右解码：每个码字一结束，相应的符号便能立即被识别。前缀码是信息论和无损数据压缩的基础，尤其适用于用不同长度的码字表示符号的情形。(xlinux.nist.gov)

定义与示例

设 (\Sigma) 为编码字母表，(\Sigma^) 表示由该字母表中的符号组成的所有有限字符串的集合。如果对于不同的 (u,v\in C)，都不存在字符串 (w) 使得 (v=uw)，则称集合 (C\subseteq\Sigma^) 是无前缀的。等价地说，任何完整码字都不能是更长码字的开头。符号编码器是一个将信源符号映射到这些码字的单射函数。(ocw.mit.edu)

例如，下面的二进制码是无前缀的：

编码字符串 010110111 可以无歧义地划分为 0 | 10 | 110 | 111，解码得到 ABCD。这里的分隔符只是为了便于说明，无需传输。相比之下，码 {0, 1, 01} 不是无前缀的，01 既可能表示一个码字，也可能表示 0 和 1 两个码字的拼接。(stanforddatacompressionclass.github.io)

互不相同的定长码字也满足前缀条件。因此，前缀码描述的是一种结构性质，并不要求码字长度必须不同。它也不禁止码字具有相同的开头部分：110 和 111 都以 11 开头，但这两个完整码字都不是对方的前缀。(xlinux.nist.gov)

即时解码与编码树

前缀码可以用一棵有根编码树表示。树的边用编码字母表中的符号标记，每个码字就是从根节点到某个已分配码字的叶节点的路径上，各边标记依次组成的序列。对于二进制码，边的标记为 0 和 1。只在叶节点处分配码字，就能保证任何码字都不位于通往另一个码字的路径上。(xlinux.nist.gov)

基于树的解码算法从根节点出发，每读入一个符号，就沿相应的边前进一步。到达已分配码字的叶节点时，算法输出对应的信源符号，然后返回根节点。它不需要预读当前码字之后的内容，因此前缀码也称为即时码。这里的“即时”指的是解码延迟，并不意味着计算不耗费时间。(stanforddatacompressionclass.github.io)

每个前缀码都是唯一可译码的：码字拼接而成的序列恰好确定一个信源符号序列。反之则不成立；有些唯一可译码需要读入后续内容，或者等到消息结束，才能识别前面的某个符号。(web.mit.edu)

克拉夫特–麦克米伦不等式

对于使用含有 (D\geq2) 个符号的字母表的有限前缀码，若码字长度为 (\ell_1,\ldots,\ell_m)，则克拉夫特–麦克米伦不等式给出

[ \sum_{i=1}^{m}D^{-\ell_i}\leq1. ]

反过来，任何满足这一不等式的有限正整数长度列表，都可以由某个前缀码实现。因此，该不等式刻画的是哪些长度列表可以实现，而不能用来判定某一组具体选定的码字是否无前缀。(ocw.mit.edu)

利用树的表示可以给出一个计数证明。在深度 (L=\max_i\ell_i) 处，长度为 (\ell_i) 的码字所占据的子树包含 (D^{L-\ell_i}) 个节点。这些子树互不重叠，而完整的树在这一深度共有 (D^L) 个节点。将由此得到的计数不等式两边除以 (D^L)，便得到克拉夫特不等式。(ocw.mit.edu)

唯一可译码也满足相同的长度约束。因此，它们的长度列表同样可以由前缀码实现，而且对于给定的信源分布，平均码长保持不变。(stanforddatacompressionclass.github.io)

压缩与最优码

给定信源符号的概率 (p_i)，二进制码的码长期望值为

[ L=\sum_i p_i\ell_i ]

单位为每个信源符号的比特数。压缩利用符号概率的不均等，为更频繁出现的符号分配更短的码字。无前缀性保证了可解码性，但本身并不保证平均码长较短。(web.mit.edu)

对于至少有两个符号的概率为正的有限信源，其信息熵定义为

[ H(X)=-\sum_i p_i\log_2p_i. ]

每个二进制前缀码都满足 (L\geq H(X))，而最优平均码长 (L^*) 满足

[ H(X)\leq L^*<H(X)+1. ]

一种证明存在性的构造方法是取 (\ell_i=\lceil-\log_2p_i\rceil)；这些长度满足克拉夫特不等式。对于给定的有限符号分布，在采用二进制逐符号编码且每比特成本相同的条件下，霍夫曼编码可以生成平均码长最小的前缀码。并非所有前缀码都是霍夫曼码。(ocw.mit.edu)

对于独立同分布信源，将 (n) 个符号组成的块作为一个整体进行编码，可以减少每个原始符号分摊的取整开销：

[ H(X)\leq\frac{L_n^*}{n}<H(X)+\frac1n. ]

这将前缀编码与信源编码定理联系起来：增加块长度，可以使每个符号的平均编码长度趋近于熵。(ocw.mit.edu)

参考来源

1. prefix codexlinux.nist.gov
2. MIT 6.02 DRAFT Lecture Notesweb.mit.edu
3. 441 Information Theory, Lecture 5ocw.mit.edu
4. Prefix Free Codesstanforddatacompressionclass.github.io
5. Kraft Inequalitystanforddatacompressionclass.github.io
6. MITOCW: 18.200 Lecture 17 transcriptocw.mit.edu