哈夫曼编码

哈夫曼编码是一种用于无损数据压缩的算法，根据符号的出现频数或概率，为其分配长度不等的码字。在二进制形式中，出现频繁的符号获得较短的比特序列，而出现较少的符号获得较长的序列。对于给定的符号分布，它构造出的前缀码具有最小的平均码字长度。戴维·A. 哈夫曼在1952年9月发表的论文《最小冗余码的构造方法》中提出了这一方法。(compression.ru)

编码模型

输入是一个有限的符号集，其概率分布已知或可通过估计获得。符号可以代表字符、字节或更大的单位。若符号 (i) 的概率为 (p_i)，码字长度为 (\ell_i)，则要最小化的量是码字长度的期望值：

[ L=\sum_i p_i\ell_i. ]

用出现次数代替概率，得到的优化问题与之等价，因为将所有出现次数除以同一个总数进行归一化，并不会改变使平均长度最小的编码。(ocw.mit.edu)

前缀条件指的是，任何一个完整码字都不是另一个码字的开头。因此，解码器在到达码字末尾时就能立即识别相应符号，无须使用分隔符。这种结构可以用一棵二叉树表示：符号位于叶节点，分支标记为0或1，从根节点到叶节点的每条路径构成一个码字。码字长度等于该叶节点的深度。(ocw.mit.edu)

构造与解码

哈夫曼方法是一种贪心算法。初始时，每个符号各自构成一个节点，以其概率或出现频数作为权重。构造过程反复执行以下步骤：

1. 选出权重最小的两个节点。
2. 将它们设为一个新父节点的子节点。
3. 将两个节点的权重之和赋给父节点。
4. 将父节点放回待选节点集合。

对于 (n) 个符号，经过 (n-1) 次合并后便得到一棵树。随后为树的分支分配0和1，即可确定各个码字。若存在相同权重，就可能有不同的选择，因此最优编码不一定唯一。(ocw.mit.edu)

优先队列支持选取节点和重新插入节点，通常用二叉堆实现。构造过程的时间复杂度为 (O(n\log n))，这里使用的是大O记号。如果权重已经排好序，构造过程可以在 (O(n)) 时间内完成。这些复杂度界限针对的是编码的构造，而非整条消息的处理。(ocw.mit.edu)

解码时，从根节点出发，按每个输入比特所指示的分支向下遍历。到达叶节点后，输出该节点对应的符号，再回到根节点，继续解码下一个符号。(datatracker.ietf.org)

示例

考虑四个符号，其概率分别为 (A=0.5)、(B=0.25)、(C=0.125) 和 (D=0.125)。按照上述构造过程，先合并 (C) 和 (D)，得到权重为 (0.25) 的节点。再将该节点与 (B) 合并，得到权重为 (0.5) 的节点，最后将其与 (A) 合并。一种可能的编码分配如下：(ocw.mit.edu)

对于这一示例分布，平均码字长度为

[ L=0.5(1)+0.25(2)+0.125(3)+0.125(3)=1.75 ]

即每个符号1.75比特，而定长表示需要每个符号2比特。消息“ABCD”被编码为 010110111。这一比较没有计入传递码表所需的信息。

最优性与熵

最优性的数学证明采用交换论证：存在一棵最优树，其中概率最小的两个符号是位于最大深度的兄弟叶节点。用这两个叶节点的共同父节点取代它们，就将问题化为符号数减少一个的编码问题。对这一简化问题求得最优解，再恢复两个叶节点，即可得到原问题的最优解。反复运用这一论证，便可证明贪心构造的正确性。(math.mit.edu)

在信息论中，信息熵（香农熵）衡量一个分布的平均信息量：

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

对于至少包含两个正概率符号的有限符号集，二进制哈夫曼编码满足

[ H(X)\le L<H(X)+1. ]

因此，其平均码字长度比熵高出的部分不足1比特。当每个概率都恰好是2的负整数次幂时，码字长度可以等于各符号的自信息，从而达到 (L=H(X))。(ocw.mit.edu)

这一关系将哈夫曼编码与信源编码定理联系起来。将 (k) 个满足统计独立性且同分布的符号组成一块进行编码，可以使每个原始符号的平均码长超出熵的部分降至 (1/k) 以下。不过，块符号集的规模会随 (k) 呈指数增长。(ocw.mit.edu)

实用形式与局限

规范哈夫曼编码保留码字长度，但按照标准化的顺序分配比特模式。只要知道符号顺序和码字长度，解码器就能重建编码，无须接收完整的树结构。这改变的是编码的表示方式，而不是平均编码长度。一些格式还会限制码字的最大长度，此时需要采用受约束的构造方法，而不能直接使用不受约束的算法。(datatracker.ietf.org)

哈夫曼编码的最优性适用于给定的分布和逐符号前缀编码模型，并不意味着它能生成尽可能小的压缩文件。对各个符号分别编码，并不能直接利用相邻符号之间的依赖关系。相比之下，算术编码对符号序列进行编码，可以避免为每个符号单独分配整数个比特。(ocw.mit.edu)

DEFLATE压缩格式展示了哈夫曼编码如何用于更完整的数据压缩系统。它将LZ77匹配与哈夫曼编码相结合，对字面值、匹配长度和向后距离进行编码。DEFLATE既支持预定义码表，也支持动态传输的码表，并采用规范排序，根据码字长度重建编码。(datatracker.ietf.org)

参考来源

1. A Method for the Construction of Minimum-Redundancy Codescompression.ru
2. 046J Complete Lecture Notesocw.mit.edu
3. 441S16: Course Notesocw.mit.edu
4. MITOCW: 18.200 Lecture 17 Transcriptocw.mit.edu
5. Finding Efficient Compressions; Huffman and Hu-Tucker Algorithmsmath.mit.edu
6. RFC 1951: DEFLATE Compressed Data Format Specification version 1.3datatracker.ietf.org