霍夫曼编码

定义

霍夫曼编码(Huffman Coding)是 David Huffman 于 1952 年提出的无损数据压缩算法,为每个符号分配长度可变的二进制前缀码,使加权平均码长最短。

原理

统计各符号频率后,反复从集合中取出频率最小的两个节点合并为新节点(频率相加),直至只剩一个根,形成霍夫曼树;从根到叶的路径(左 0 右 1)即为各符号编码。前缀性质保证解码无歧义。用优先队列实现的建树复杂度为 O(n log n)。该贪心策略可证明得到最优前缀码。

应用

DEFLATE(ZIP、gzip、PNG)、JPEG 与 MP3 的熵编码阶段都使用霍夫曼编码或其变体;传真标准与许多通信协议也采用类似技术。

局限

码长必须是整数比特,压缩率逊于算术编码与 ANS;符号分布变化时需自适应变体或重建码表。