霍夫曼编码

霍夫曼编码将符号映射为可变长度的位字符串。前缀无关码中没有任何码字是另一个码字的前缀，因此解码器可以遍历一棵二叉树，并在到达叶节点时立即输出符号。前缀无关码都能唯一解码，但并非所有可唯一解码的编码都具有前缀无关性质。

前缀无关码和 Kraft 不等式 #

对于码字长度为 lᵢ 的二叉前缀码，Kraft 不等式为

Σ 2^(-lᵢ) ≤ 1

该不等式计算每个叶节点占用二叉树的比例。反过来，满足该不等式的每个正整数长度序列都可以由二叉前缀码实现。等号表示完整树；严格不等式表示存在未使用的分支。

构建频率树 #

给定符号频率后，霍夫曼算法反复移除权重最低的两个节点，将它们作为权重为两者之和的节点的兄弟，然后重新插入该节点。符号的深度就是其码长。将低频符号合并到树的更深处，可以通过直观的交换论证说明其最优性：将高频符号移到低频符号之上不会增加加权路径长度。对于给定频率，得到的树会在所有二叉前缀码中最小化期望长度。

while more than one node remains:
    a, b = remove the two lowest-weight nodes
    insert node(weight(a) + weight(b), a, b)

相等的权重允许存在多个最优树。确定性实现必须定义平局处理方式，例如在频率相同后比较稳定的符号序号。即使期望位数不变，确定性仍然对可复现输出和测试很重要。要求最大码长的格式需要使用长度受限的霍夫曼算法；简单截断树可能违反 Kraft 不等式或改变预期的符号顺序。

对于短输入或高熵输入，码表开销可能超过节省的空间。霍夫曼编码是一种表示选择，并不能保证每个输入都会变小。

规范重建 #

许多格式传输的是码长，而不是左右树指针。规范构造会按 (length, symbol order) 对活动符号排序，并在每个长度内分配连续整数码；长度增加时，将下一个码左移。解码器重复该计算，然后将每个码插入查找表或解码树。因此，无需传输树形状，相同的长度仍会生成相同的编码。

例如，对于符号 A 到 D 的长度 (1, 2, 3, 3)，规范表如下：

该表记录逻辑码值。面向位的格式可以按不同顺序序列化这些值；例如，DEFLATE 在将霍夫曼位打包到流中时会反转这些位。

解码器应使用经过检查的算术构建该表，并拒绝：

• 超出外层格式限制的码长；
• 过度订阅的集合，即码长要求的叶节点多于树所包含的叶节点；
• 格式要求完整树时出现不完整集合；
• 重复或超出范围的符号、格式错误的重复指令，以及缺少必需的块结束符号；
• 走过表范围或在一个码内部结束的位序列。

查找表可以一次解码多个位，但慢路径仍必须验证码长和剩余输入。将无效表项当作符号会把格式错误的输入转化为静默损坏。

有关具体的规范格式，请参阅 DEFLATE 和 Gzip 格式。

参考资料 #

• D. A. Huffman，《A Method for the Construction of Minimum-Redundancy Codes》，Proceedings of the IRE，1952 年。
• RFC 1951：DEFLATE，第 3.2.1–3.2.2 节