哈夫曼树(Huffman Tree)

定义

哈夫曼树(Huffman Tree,又称最优二叉树)是给定一组带权叶子节点后,带权路径长度(WPL)最小的二叉树,由 David Huffman 于 1952 年在 MIT 读研期间提出,用于构造最优前缀码。

构造

采用贪心策略:每次从集合中取出权值最小的两棵树,合并为一棵新树(根权值为二者之和)放回集合,重复直到只剩一棵。用优先队列实现的复杂度为 O(n log n)。频率越高的符号离根越近,编码越短,且任何编码都不是另一编码的前缀,可无歧义解码。

应用

哈夫曼编码是无损压缩的基石:DEFLATE(zip、gzip、PNG)、JPEG 的熵编码阶段、MP3 等格式都使用哈夫曼编码或其变体;数据结构课程中它也是贪心算法正确性证明的标准例题。

优缺点

优点是构造简单、可证明在逐符号整数码长前提下最优;缺点是码长必须为整数比特,压缩率不及算术编码和 ANS,且需要传输或约定码表。