Huffman 编码

是什么

Huffman 编码是一套按出现频率给符号分配二进制位的压缩方法。日常类比：

写中文的时候，“的”、“了” 出现得最多，给它们配 1 位代号；“鳙”、“魉” 几乎不出现，给它们配 12 位代号。平均下来，整段文字的总位数比”每个字一律 8 位”少很多。

你的电脑里现在跑着的 ZIP / GZIP / PNG / JPEG / MP3，底层全都还在用这个 1952 年的算法。

它的核心是一句话：频率高的符号，给短码；频率低的，给长码——但所有码字之间不能”开头一样”，不然解码会歧义。

为什么重要

不理解 Huffman，下面这些事都没法解释：

为什么同一段英文文本压缩后能小一半，但加密后的随机数据几乎压不动
为什么 GZIP 一个 100 字节的小文件反而变大——因为码表本身要存
为什么 Shannon 在 1948 年说的”信息熵下界”不是空话，70 年后还是工业代码的天花板
为什么一个 MIT 学生为了逃期末考试写出来的作业，直接打败了他教授提出的算法

核心要点

Huffman 的过程拆三步：

频率统计：扫一遍数据，看每个符号出现多少次。类比：先数清楚一篇文章里”的”出现 200 次、“鳙”出现 0 次。
构建二叉树（最小堆贪心）：把所有符号当作”小树”放进堆里。每次取出权重最小的两棵合并，新节点的权重等于两个子节点之和，放回堆。重复到堆里只剩一棵——这就是 Huffman 树。
左右路径就是编码：从根开始，左走标 0、右走标 1，到叶子的路径就是该符号的二进制码。自动是前缀码——任何码都不是另一个的前缀，所以解码无歧义。

第 2 步的”贪心”听起来不靠谱，但 Huffman 证明了它是最优的（同 shannon-1948 的熵下界相比误差 ≤ 1 bit/symbol）。证明用的是”交换论证”：假设有更优的码，把最小两个频率换到树最深处，能证明换完不会更差——所以 Huffman 已经是最优。

实践案例

案例 1：手算一棵 Huffman 树

5 个字母 A B C D E，频率分别为 0.4 / 0.2 / 0.2 / 0.1 / 0.1。

构造步骤（每次合并两个最小）：

步骤	操作	当前森林
0	初始	A:0.4, B:0.2, C:0.2, D:0.1, E:0.1
1	合并 D+E → 0.2	A:0.4, B:0.2, C:0.2, 0.2
2	合并 B+C → 0.4	A:0.4, 0.2, 0.4
3	合并 0.2+0.4 → 0.6	A:0.4, 0.6
4	合并 0.4+0.6 → 1.0	根:1.0

最终码：A=1、B=010、C=011、D=0010、E=0011。注意 A 用 1 位（最常出现）、D/E 用 4 位（最罕见）。

案例 2：“ABBA” 压缩对比

普通 8-bit ASCII：4 个字符 × 8 bit = 32 bit。用上述 Huffman：A=1、B=010，“ABBA” = 1 + 010 + 010 + 1 = 8 bit。

压缩比 75%。当然这是玩具例子——真实场景还要存码表，所以小文件未必划算。

案例 3：5 行 Python 实现

import heapq
from collections import Counter

def huffman(text):
    heap = [[w, [s, ""]] for s, w in Counter(text).items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        lo, hi = heapq.heappop(heap), heapq.heappop(heap)
        for pair in lo[1:]: pair[1] = '0' + pair[1]
        for pair in hi[1:]: pair[1] = '1' + pair[1]
        heapq.heappush(heap, [lo[0]+hi[0]] + lo[1:] + hi[1:])
    return sorted(heap[0][1:], key=lambda p: (len(p[1]), p))

跑 huffman("ABBA") 立刻看到码表。整个核心思想就是这么轻——这也是 Huffman 能撑 70 年的原因。

踩过的坑

静态 vs 自适应：教科书讲的是”先扫一遍统计频率再编码”（静态 Huffman），需要两遍扫描。流式数据（聊天记录、日志）做不到——要用 自适应 Huffman（FGK / Vitter），编码端和解码端同步更新树。代价是慢 2-3 倍。
频率均匀压不动：如果数据已经加密 / 已经压缩过，每个字节的概率几乎相同，熵接近 8 bit/byte，Huffman 给每个字节也接近 8 bit。再压一遍反而变大（因为多了码表开销）。
小文件不划算：100 字节的输入，码表本身就要 100+ 字节存。GZIP 用了一个 hack——静态 Huffman 模式直接复用 RFC 1951 写死的码表，不传码表。但这个码表是给”英文文本 + 源代码”调优的，对中文/二进制效果不好。
整数 bit 是天花板：信息熵 H 可以是 0.469 bit/symbol，但 Huffman 必须给每个符号至少 1 bit。当一个符号概率特别高（如 0.9），Huffman 的冗余可达 100%。算术编码（1976）和 ANS（2009）能突破这道墙——后者已经在 Zstd / JPEG XL 里取代 Huffman。
bit endianness 写错全错：自己写解码器最容易踩的坑——DEFLATE 的码字是 LSB-first（最低位先发），写成 MSB-first 整流就是乱码。这种 bug 不会”部分错”——要么全对要么全错。

适用 vs 不适用场景

适用：

文本压缩，符号频率分布明显偏斜（自然语言、源代码、日志）
已知概率分布不变的场景（HTTP 头部压缩 / HPACK 用静态 Huffman）
速度敏感场景——表查询每符号约 1ns，比算术编码快 5 倍

不适用：

已加密 / 已压缩的数据（熵接近最大，Huffman 帮不上忙）
极低熵分布（如 99% A、1% B）—— 用算术编码或 ANS
流式数据无法预扫描时——需要自适应 Huffman 或 ANS
对压缩率敏感、速度可以让步——ANS 同样快、压缩率更高

历史小故事（可跳过）

1948：Shannon 在 shannon-1948 定义信息熵，证明编码下界是 H(X)，但他给出的 Shannon-Fano 编码不是最优。
1949：Robert Fano 改进 Shannon 的算法，叫 Shannon-Fano。仍然次优。
1951 秋：MIT 信息论课，Fano 给学生选项：“期末考试 OR 写论文证明 Shannon-Fano 最优（或给出更好的）“。学生 David Huffman 选了写论文——理由是不想考试。
1951 冬：Huffman 卡住几乎放弃，想”自顶向下”的 Shannon-Fano 一直证不出来。在最后一刻他换思路：“自底向上”——每次合并两个最小频率。瞬间解开。
1952 年 9 月：4 页论文发表在 Proc. IRE，10 个公式。
1977：Lempel-Ziv 提出 LZ77（字典匹配），打开”前置压缩”思路。
1991：DEFLATE = LZ77 + Huffman，被 ZIP / GZIP / PNG 吸收，成为事实标准。
2009：Duda 提出 ANS，速度匹敌 Huffman、压缩率匹敌算术编码。
2016：Zstd 用 LZ77 + ANS，逐步蚕食 Huffman 的工业份额——但 HTTP / PNG / ZIP 因为生态锁定还在用 Huffman。

教授提出的算法被自己学生在期末作业里超越——计算机史上没几个这种故事。

学到什么

简单算法 + 正确证明 = 70 年：Huffman 论文 4 页，C 实现 50 行，但因为有数学最优性证明，70 年没被根本性取代——只是被 ANS 在边缘场景蚕食。
贪心配最小堆是经典套路：每次取最小两个、合并、放回。这种结构后来在 Dijkstra、Prim、A* 里反复出现。
整数 bit 是 Huffman 的边界：理论下界 H 可以是分数，但 Huffman 必须给整数 bit——这就是它和算术编码 / ANS 的本质差距。
生态比算法重要：ANS 技术上更优，但 HTTP / PNG / ZIP 还在用 Huffman——因为换协议需要全行业升级，门槛远高于”算法更好”本身。

关联

shannon-1948 —— Shannon 定义信息熵，给出编码下界 H(X)；Huffman 的最优性证明就是逼近这个下界
turing-1936 —— 计算理论根基；Huffman 是”什么是最优编码”这个可计算问题的具体解
lambda-calculus —— 同样诞生在 1930s-50s 的”用极简结构表达普适问题”思潮中
godel-1931 —— 数学不完备性；Huffman 反方向证明”在整数 bit 限制下最优是可达的”

反向链接

godel-1931 —— Gödel 1931 — 不完备性定理
lambda-calculus —— λ-演算 — 用三条规则表达所有可计算函数
shannon-1948 —— Shannon 1948 — 信息论的诞生
turing-1936 —— Turing 1936 可计算性