前缀码 · Elea Notes

先看一个麻烦

你要用 0 和 1 给四个字母编码，而且想省位数。常用的 A 给短码，罕见的 D 给长码，听起来很合理：

A = 0，B = 1，C = 01，D = 10

现在我发给你 01。这是 C，还是 A 接着 B？

无解。这套码是歧义的。

第一个想法是加分隔符：0,1,01,10。但分隔符本身要占位数，省下来的又还回去了。

第二个想法是所有码字等长：00、01、10、11。这样每两位切一刀，绝不歧义。可它放弃了变长编码的全部好处——常用字母和罕见字母花一样多的位数，而我们知道概率不均时这是浪费（见熵）。

我们想要的是：变长，但仍然能唯一切开。

条件出乎意料地简单：没有任何码字是另一个码字的前缀。

把上面那套坏码修一下：

A = 0，B = 10，C = 110，D = 111

检查一遍：0 不是 10、110、111 的开头；10 不是 110、111 的开头。满足条件。

现在解码 0101110111，从左往右贪心读：

0        -> A     剩 101110111
10       -> B     剩 1110111
111      -> D     剩 0111
0        -> A     剩 111
111      -> D     剩 (空)

得到 ABDAD，唯一解，没用一个分隔符。之所以能贪心，是因为一旦读到的位串匹配某个码字，它就不可能是别的更长码字的开头——前缀条件保证了这一点。

用二叉树看更清楚：把码字放在叶子上，走 0 向左走 1 向右。前缀条件等价于”没有码字落在另一个码字的路径上”：

        ·
       / \
      A   ·          A = 0
         / \
        B   ·        B = 10
           / \
          C   D      C = 110, D = 111

上面那套码配上概率 1/2、1/4、1/8、1/8，平均码长是

0.5×1 + 0.25×2 + 0.125×3 + 0.125×3 = 1.75 比特

而这组概率的熵也正好是 1.75。这不是巧合：每个概率都是 2 的负整数次幂，此时 −log₂pᵢ 恰好是整数，码长能精确匹配理论最优。

概率不是 2 的幂时就有零头，平均码长只能逼近熵而无法相等。这正是香农第 9 定理里那个”任意小的 ε”的来源——它不是设备缺陷，是整数码长与实数熵之间的必然缝隙。

香农证明了最优编码存在，但明确说自己不给构造方法。四年后霍夫曼给出了一个，而且是作为课程作业交的：反复把概率最小的两个节点合并成一个父节点，自底向上建树。

前缀码是”唯一可解码”的充分条件，不是必要条件——存在非前缀但仍可唯一解码的码（比如把前缀码整个反转）。但前缀码可以即时解码：读完最后一位立刻知道是哪个符号，不用回看。这个性质在流式传输里价值很大。