前缀码

概述

前缀码是一种编码方案，其中任何字符的编码都不是另一个字符编码的前缀。前缀码保证了编码字符串的唯一可解码性——无需分隔符即可无歧义地解码。前缀码与满二叉树之间存在一一对应关系，而 哈夫曼编码 构造的就是一棵最优前缀码树。

定义

前缀码（Prefix Code / Prefix-Free Code）

设 $C$ 为字母表，$f:C\to \{0,1{\}}^{\ast }$ 为编码函数。如果对于 $C$ 中任意两个不同的字符 $c_1,c_2$，$f(c_1)$ 不是 $f(c_2)$ 的前缀，则称 $f$ 为前缀码。

等价地，前缀码是一组二进制字符串的集合 $\{f(c):c\in C\}$，满足其中任何字符串都不是另一个字符串的前缀。

核心性质

1. 唯一可解码性

前缀码保证了唯一可解码性：给定编码后的二进制串，可以从左到右逐字符解码，无需任何分隔符。

解码过程：从编码树的根节点开始，根据二进制串中的每一位（0向左，1向右）遍历树，到达叶节点时输出对应字符，然后回到根节点继续解码。

前缀码 vs. 唯一可解码码

前缀码一定是唯一可解码的，但唯一可解码的码不一定是前缀码。例如，$\{0,01\}$ 不是前缀码（0是01的前缀），但它仍然是唯一可解码的。然而，前缀码在实际应用中更为方便，因为解码过程可以实时进行（在线解码），而不需要看到整个编码串。

2. 前缀码与满二叉树的对应

前缀码与二叉树之间存在一一对应关系：

• 编码树：每个字符对应一个叶节点，从根到叶的路径上的 0/1 序列就是该字符的编码
• 前缀性质：因为字符只出现在叶节点上，一个字符的编码路径不可能包含另一个字符的编码路径——这正是前缀码的定义

满二叉树（每个内部节点恰好有两个子节点）与前缀码的对应：

• 若编码树不是满二叉树（存在只有一个子节点的内部节点），则可以”提升”其子节点来缩短某些编码，从而降低编码代价
• 因此，最优前缀码对应的编码树一定是一棵满二叉树

3. 编码代价

给定一棵编码树 $T$，编码代价定义为：

$B(T)={\sum }_{c\in C}f[c]\cdot d_T(c)$

其中 $f[c]$ 是字符 $c$ 的频率，$d_T(c)$ 是字符 $c$ 在树中的深度。

等价地，也可以用内部节点来定义：

$B(T)={\sum }_{\text{所有内部节点 }x}f[x]$

其中 $f[x]$ 是以 $x$ 为根的子树中所有叶节点的频率之和。这个等价性可以通过展开定义来验证。

4. 最优前缀码定理

Theorem：对于给定的字符频率集合，哈夫曼编码 产生的编码树是最优前缀码（即编码代价最小）。

该定理的证明基于两个关键引理：

• Lemma 15.2（贪心选择性质）：频率最低的两个字符在最优前缀码中一定是最深层的兄弟
• Lemma 15.3（最优子结构）：合并频率最低的两个字符后，在缩小的问题上构造最优前缀码，再展开得到原问题的最优前缀码

5. 前缀码的编码长度范围

对于 $n$ 个字符的字母表：

• 定长编码：每个字符 $\lceil {\log }_{2}n\rceil$ 位
• Huffman编码：高频字符编码短，低频字符编码长，平均编码长度小于定长编码
• 最坏情况：当字符频率极度不均匀时，Huffman编码的优势最明显
• 最好情况：当所有字符频率相同时，Huffman编码退化为定长编码

章节扩展

• 15.3 哈夫曼编码 — 最优前缀码的构造算法
• 贪心算法 — 贪心算法完整方法论
• 贪心选择性质 — 贪心选择性质的详细说明

参见

• 哈夫曼编码 — 最优前缀码的构造
• 活动选择问题 — 另一个经典贪心问题
• 动态规划 — 与贪心算法的对比