哈夫曼编码

概述

哈夫曼编码是一种基于字符频率构造最优前缀码的贪心算法。它通过自底向上地合并频率最低的两个节点来构建编码树，生成的编码具有最小加权路径长度。哈夫曼编码是数据压缩领域的基础算法，广泛应用于 DEFLATE/ZIP、JPEG、MP3 等格式中。

定义

哈夫曼编码（Huffman Coding）

输入：字母表 $C=\{c_1,c_2,\dots ,c_n\}$，每个字符 $c$ 的频率为 $f[c]$。

输出：一棵二叉编码树 $T$，使得编码代价最小： $B(T)={\sum }_{c\in C}f[c]\cdot d_T(c)$

其中 $d_T(c)$ 是字符 $c$ 在树 $T$ 中的深度（即编码长度）。

核心性质

1. HUFFMAN 算法

HUFFMAN(C):
    n = |C|
    Q = C    // 以频率为优先级的最小优先队列
    for i = 1 to n - 1:
        allocate a new node z
        z.left = x = EXTRACT-MIN(Q)    // 频率最低的节点
        z.right = y = EXTRACT-MIN(Q)   // 频率次低的节点
        z.freq = x.freq + y.freq
        INSERT(Q, z)
    return EXTRACT-MIN(Q)              // 返回树的根

算法执行 $n-1$ 次合并操作，每次从优先队列中取出两个最小频率节点，合并后放回队列。

2. 贪心选择性质

由 贪心选择性质 中的 Lemma 15.2，频率最低的两个字符 $x$ 和 $y$ 在最优前缀码中一定是最深层的一对兄弟节点。因此，将它们合并为一个新节点不会丢失最优性，且将问题规模从 $n$ 减小到 $n-1$。

3. 最优子结构

合并 $x$ 和 $y$ 后得到的新节点 $z$（频率为 $f[x]+f[y]$），在剩余 $n-1$ 个字符上构造最优前缀码，再加上 $x$ 和 $y$ 作为 $z$ 的子节点，就得到原问题的最优前缀码。

4. 时间复杂度分析

实现方式	EXTRACT-MIN	INSERT	总时间
无序数组	$O(n)$	$O(1)$	$O(n^2)$
二叉堆	$O(\log n)$	$O(\log n)$	$O(n\log n)$
van Emde Boas 树	$O(\log \log n)$	$O(\log \log n)$	$O(n\log \log n)$

使用二叉堆实现时，$n-1$ 次合并，每次需要2次 EXTRACT-MIN 和1次 INSERT，总计 $O(n\log n)$。

5. 编码示例

设字母表 $C=\{a:5,b:9,c:12,d:13,e:16,f:45\}$（频率）：

合并过程：
1. a(5) + b(9) = ab(14)
2. c(12) + d(13) = cd(25)
3. ab(14) + e(16) = abe(30)
4. cd(25) + abe(30) = cdabe(55)
5. cdabe(55) + f(45) = 根(100)

编码结果：
f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111

历史背景

哈夫曼编码由 David A. Huffman 于 1952 年在其 MIT 博士论文中提出。据传这是他在课程作业中超越其导师 Robert M. Fano 的成果——Fano 曾提出 Fano 编码（一种次优的前缀编码方法），而 Huffman 发现了构造最优前缀码的高效算法。

应用场景

• DEFLATE / ZIP：结合 LZ77 和 Huffman 编码的通用压缩算法
• JPEG：图像压缩中对 DCT 系数进行 Huffman 编码
• MP3：音频压缩中对量化后的频谱数据进行 Huffman 编码
• HTTP/2 HPACK：HTTP/2 头部压缩中使用静态 Huffman 表

章节扩展

• 15.3 哈夫曼编码 — 哈夫曼编码的完整求解过程
• 贪心算法 — 贪心算法完整方法论
• 贪心选择性质 — 贪心选择性质的详细说明
• 前缀码 — 前缀码的定义和性质

参见

• 活动选择问题 — 另一个经典贪心问题
• 替换论证 — 证明哈夫曼编码最优性的技术
• 离线缓存 — 贪心算法的另一个应用
• 动态规划 — 与贪心算法的对比