跳转到内容
← 返回算法
经典算法计算机科学 · 信息论 · 数据压缩约 14 分钟阅读

霍夫曼编码

Huffman Coding

1951 年，麻省理工学院一门信息论课程上，教授 Robert Fano 给学生一个选择：要么参加期末考试，要么写一篇学期论文，证明一种最优的数据编码方案——能把信息压缩到尽可能短。Fano 自己（与香农一道）已经有一个接近但并非最优的方案（Shannon-Fano 编码）。 学生 David Huffman 选择了写…

霍夫曼编码数据压缩贪心前缀码

1951 年，麻省理工学院一门信息论课程上，教授 Robert Fano 给学生一个选择：要么参加期末考试，要么写一篇学期论文，证明一种最优的数据编码方案——能把信息压缩到尽可能短。Fano 自己（与香农一道）已经有一个接近但并非最优的方案（Shannon-Fano 编码）。

学生 David Huffman 选择了写论文。他一直证明不出谁是最优，几乎要放弃、转去准备期末考试时，突然想到了用"按频率排序的二叉树"自底向上构造——并很快证明了它确实最优，反而胜过了出题的老师。

Huffman 编码不仅是最优前缀码，也是贪心算法在信息论中最完美的应用之一。时至今日，它仍是 JPEG、ZIP、MP3 等无数压缩标准的组成部分。

问题：如何用更少的比特表示信息

标准 ASCII 编码用 7 位（或 8 位）表示每个字符——无论该字符出现频率高低，代价相同。但实际文本中，字符频率差异极大。英文中，'e' 出现频率约 12%，'z' 约 0.07%。如果能给高频字符分配短编码，低频字符分配长编码，整体就能用更少的总比特表示文本。

前缀码（Prefix-free Code）：任何编码都不是另一个编码的前缀。这保证解码时无歧义——不需要分隔符，从左到右扫描就能唯一分割。

目标：在所有无歧义（前缀码）编码方案中，找最小化期望编码长度的方案：

最小化∑i=1nfi⋅li\text{最小化} \sum_{i=1}^{n} f_i \cdot l_i

其中 fif_i 是字符 $i$ 的频率，lil_i 是其编码长度。

霍夫曼算法：贪心构造

Huffman 发现，最优前缀码对应一棵二叉树（叶节点是字符，根到叶的路径就是编码），且这棵树可以用贪心算法自底向上构造。

贪心策略：每次合并频率最低的两棵树

  1. 初始化：每个字符是一棵只有叶节点的树，频率就是字符频率
  2. 重复以下直到只剩一棵树：
  3. - 从所有树中取出频率最小的两棵 T1,T2T_1, T_2
  4. - 创建新节点，频率 = f(T1)+f(T2)f(T_1) + f(T_2)，左右子树分别为 T1,T2T_1, T_2
  5. 最终的树就是最优前缀码树；0 表示走左分支，1 表示走右分支

例子：字符频率：A:45, B:13, C:12, D:16, E:9, F:5（单位：千次）

初始叶节点（按频率）：F(5) E(9) C(12) B(13) D(16) A(45)

步骤1：合并 F(5) + E(9) → 新节点(14) C(12) B(13) 新(14) D(16) A(45)

步骤2：合并 C(12) + B(13) → 新节点(25) 新(14) D(16) A(45) 新(25)

步骤3：合并 新(14) + D(16) → 新节点(30) A(45) 新(25) 新(30)

步骤4：合并 新(25) + 新(30) → 新节点(55) A(45) 新(55)

步骤5：合并 A(45) + 新(55) → 根节点(100) ```

读出最终编码（0 走左、1 走右）：A: 0，C: 100，B: 101，D: 111，F: 1100，E: 1101。平均编码长度：0.45×1+0.13×3+0.12×3+0.16×3+0.09×4+0.05×4=2.240.45 \times 1 + 0.13 \times 3 + 0.12 \times 3 + 0.16 \times 3 + 0.09 \times 4 + 0.05 \times 4 = 2.24 比特/字符。而 3 位固定编码需要 3 比特/字符——节省约 25%。

最优性的证明

霍夫曼算法的最优性由贪心交换论证证明：

引理1（最低频率字符在最优树中最深）：存在一个最优树，使得频率最低的两个字符是兄弟节点（在最深的某一层）。

证明：假设最优树中频率最低字符 $x$ 不在最深层，那里有字符 $y$（深度更深，频率可能更高）。交换 $x, y$，编码长度不会增加，因为 fx≤fyf_x \leq f_y 而 $x$ 深度增加、$y$ 减少。

引理2（子树独立性）：若把频率最低的两个字符合并为一个"超级字符"，对剩余字符的最优编码不变，只是超级字符处的代价分配给了两个子字符。由这两个引理出发做归纳，就能证明贪心选择（每次合并最小的两棵树）给出整体最优。

为什么必须自底向上？ 对比一下 Shannon-Fano 编码就清楚了。Shannon-Fano 自顶向下：把符号按频率排序后分成频率和接近的两半，递归下去。问题在于"对半分"的边界未必对齐最优树的分支——一次粗糙的分组就把某些符号锁死在了错误的深度上，后面无法挽回，所以 Shannon-Fano 只能接近最优而非达到。Huffman 反过来自底向上：引理 1 保证"频率最低的两个符号必在最深处做兄弟"，于是每次合并锁死的是最安全的那一层——越深的位置代价越敏感，先把最深的安排妥当，浅层怎么排都不会错。贪心的方向不是随意选的，是由引理 1 指定的。

信息论极限

Shannon（香农）在 1948 年证明：无损压缩的理论极限是信息熵：

H=−∑i=1npilog⁡2piH = -\sum_{i=1}^{n} p_i \log_2 p_i

这是每个符号需要的平均最少比特数。霍夫曼编码极其接近这个极限：

H≤LHuffman<H+1H \leq L_{\text{Huffman}} < H + 1

即每个符号的平均编码长度最多比熵大 1 比特。这个"1 比特的间隙"来自于前缀码必须使用整数位长度——若允许分数位，可以逼近熵（算术编码做到了这一点）。

实现：优先队列驱动

霍夫曼算法用优先队列（最小堆）高效实现：

  • 初始化：将 $n$ 个字符频率插入最小堆，$O(n)$ 建堆
  • $n-1$ 次合并，每次 2 次 Extract-Min + 1 次 Insert，O(log⁡n)O(\log n) 每次
  • 总计：O(nlog⁡n)O(n \log n)

若符号频率已排好序（实际中常见，如按码点统计后排序），还可以用两个队列做到 $O(n)$：叶节点队列与合并节点队列各自单调，每次从两个队首取较小者。解码端则是逐位走树，每符号 O(li)O(l_i)；工程实现通常改用查表——一次读出若干位，在预计算的表里直接查到符号与码长，把"逐位走树"换成"一次内存访问"。

工程实现：规范霍夫曼码

霍夫曼树给出的编码方案并不唯一：交换任意内部节点的左右子树，得到的仍是最优码。这带来一个工程问题——压缩文件必须附带码表，解码器才能工作，而一棵 256 个符号的树的完整描述可能上千字节。对小文件，码表比省下的空间还大。

规范霍夫曼码（Canonical Huffman Code）用一个约定解决这个问题：所有码字按"先按码长排序、同码长按符号顺序"连续分配。有了这个约定，解码器只需知道每个符号的码长这一个整数，就能唯一重建全部码字——码表从"一棵树"压缩成"一串小整数"，解码也无需遍历树，查表即可。

DEFLATE：两种冗余的分工

霍夫曼编码今天最常见的露面方式不是单独使用，而是作为 DEFLATE 的另一半。DEFLATE 由 Phil Katz 为他的归档工具 PKZIP 2.0 设计，1996 年 5 月由 Peter Deutsch 整理为公开规范 RFC 1951——ZIP、gzip、PNG 用的都是它。

DEFLATE 的设计洞察是：真实数据里有两种独立的冗余，需要两种工具分别处理。

第一种是重复：同一段字节序列在文件中反复出现（模板文本、日志格式、图像中的同色区域）。这是 LZ77 的地盘——用一个滑动窗口记住最近的历史（32KB），遇到重复时不输出字节本身，而输出一个"（长度，距离）"对："回去 1540 字节，照抄 27 个字节"。

第二种是偏斜：即使去重之后，剩下的符号流（字面字节、长度代码、距离代码）分布仍极不均匀——有些符号出现千百次，有些只出现一次。这是霍夫曼的地盘：高频符号给短码，低频符号给长码。

关键在于这两种冗余几乎正交：LZ77 处理"序列层面"的重复，霍夫曼处理"符号层面"的分布。单独用霍夫曼，重复序列里每个字节仍要占至少一个码；单独用 LZ77，长度和距离这些数字本身的分布偏斜就白白浪费。串联起来——先 LZ77 去重，再对 LZ77 的输出符号做霍夫曼——才同时逼近两者的极限。

DEFLATE 还把规范霍夫曼码的思路推到底：它传输的是每个符号的码长（用游程编码压掉连续的零），而这串码长本身再用一个小的霍夫曼码压缩一次——用霍夫曼编码来传输霍夫曼码表，整个码表描述常常只占几十字节。

霍夫曼编码的实际使用

DEFLATE 压缩（ZIP、gzip、PNG）：结合 LZ77（重复字符串压缩）+ 霍夫曼编码（符号概率压缩）。先用 LZ77 找重复模式，再用霍夫曼对符号和距离编码。

JPEG：DC 和 AC 系数的哈夫曼编码是 JPEG 的最后压缩步骤。

MP3（MPEG Audio Layer III）：频谱系数用多个霍夫曼表编码，不同频率范围用不同的霍夫曼树。

HTTP/2 的 HPACK 头部压缩：HTTP 头字段用静态霍夫曼表编码，大幅减少网络传输量。

自适应霍夫曼编码

标准霍夫曼需要先统计全文频率，再编码（两遍扫描），但流式数据（实时传输）无法两遍扫描。自适应霍夫曼编码（Adaptive Huffman，Faller 1973 / Gallager 1978）的做法是让编码器和解码器同步维护并更新树——每处理一个符号，就根据新频率调整树。实现更复杂，但适用于流式场景。

局限与超越

霍夫曼编码是符号级（symbol-level）压缩，每次编码一个符号。局限也正在这里：独立编码每个符号，无法利用符号间的相关性（如英文中 'q' 后几乎总跟 'u'）。

更强的方案： - 算术编码（Arithmetic Coding）：将整个消息视为一个整体，编码为 $[0,1)$ 中的一个实数。机制是逐符号缩小区间：每读入一个符号，就按各符号的概率把当前区间切成对应比例，然后钻进该符号的子区间。消息越可能，最终区间越大，表示它所需的比特越少——码长可以是分数比特，恰好跨过霍夫曼"每符号整数位"的那 1 比特间隙。上世纪八九十年代，算术编码的核心专利（主要由 IBM 持有）曾显著阻碍其普及；专利陆续到期后，它成为现代压缩标准的主流，H.264/AVC 视频编码中的 CABAC（上下文自适应二进制算术编码）就是代表。 - LZW（Lempel-Ziv-Welch）：基于字典的压缩，利用符号序列的重复，GIF 格式使用此算法。

跨域连接

  • 贪心算法：这里的贪心不是启发式，而是可证明的最优——"频率最低的两个符号必是最深处的兄弟"这条交换论证一旦成立，逐次合并就锁死了全局最优。判据因此可以外推：凡是"把两个最小元素合并成一个新元素"不改变剩余问题结构的场合，贪心就精确；一旦给叶子加上顺序约束，合并不再自由，同一族问题立刻退回动态规划。
  • 统计力学与玻尔兹曼：信息熵与热力学熵不是比喻性的同名，两者都是"对数状态数的期望"，只是一个数码字、一个数微观态。由此推出一条物理下界：擦掉一比特信息必须耗散一份与温度成正比的最小热量。压缩省下的存储与擦除放出的热，记在同一本账上。
  • 语言演化：语言自己在做同一件优化——高频词倾向于更短，罕用词更长，这与"按频率分配码长"是同一条原理。可检验的推论是：某种语言的词长若严重偏离频率排序，说明另有压力（形态标记、避免同音、敬语层级）在与省力原则竞争，而不是这门语言"没优化好"。
  • Unicode 与文本编码：UTF-8 也是前缀码，却不是最短码——它按码点区间而非使用频率决定字节数，换来的是自同步：从任意字节起都能找回字符边界。霍夫曼码没有这个性质，丢一位则后面全乱，所以压缩流必须靠外层分块与校验止损。同为前缀码，优化目标不同，结构就不同。
  • 概率论：前缀码与概率分布一一对应，码长 $l$ 对应概率 2−l2^{-l}，克拉夫特不等式就是概率之和不超过一。这解释了那道"最多多一比特"的间隙：整数码长只能表示二的负整数次幂那一族概率，真实频率落在两者之间时必然浪费；允许分数码长的算术编码正是把这道间隙抹掉。

参考文献

  • Huffman, D.A. "A Method for the Construction of Minimum-Redundancy Codes." Proceedings of the IRE 40(9), 1952.
  • Shannon, C.E. "A Mathematical Theory of Communication." Bell System Technical Journal 27, 1948.
  • Deutsch, P. "DEFLATE Compressed Data Format Specification version 1.3." RFC 1951, IETF, 1996.
  • Cormen, T. et al. Introduction to Algorithms (CLRS). 4th ed. MIT Press, 2022. （第16.3节 Huffman Codes）

延伸阅读

  • Sayood, K. Introduction to Data Compression. 5th ed. Morgan Kaufmann, 2017.

正文中引用本条 · 2 · 其中 2 条来自其他领域

生命科学中心法则：从DNA到蛋白质的信息之流
数学信息论基础