结论先行：Huffman 编码是一种最优前缀变长编码，核心思想是"高频字符用短码、低频字符用长码"，通过构建哈夫曼树生成编码表，让整体编码长度最短。以"ABRACADABRA"这 11 个字符为例，定长编码需要 33 bit，Huffman 编码仅需 23 bit，节省 30%。Huffman 编码是 DEFLATE（ZIP/GZIP/PNG）等主流压缩格式的核心组件，几乎所有无损压缩算法都包含这一阶段。下面从频率统计讲起，逐步演示哈夫曼树构建和编码生成过程。
如果你对无损压缩和有损压缩的区别还不太熟悉，建议先阅读无损压缩 vs 有损压缩：核心区别。
一、为什么需要变长编码
计算机存储字符时通常用定长编码，如 ASCII 每个字符 8 bit、Unicode 每个字符 16–32 bit。定长编码的优势是随机访问方便，但浪费严重——英文文本中字母 e 出现频率约 12.7%，z 仅 0.07%，两者用同样长的编码显然不合理。变长编码根据字符出现频率分配不同长度的码字，频率越高码字越短，从而压缩整体体积。
| 编码方式 | 原理 | 码字长度 | 解码歧义 | 典型应用 |
|---|---|---|---|---|
| 定长编码 | 每个字符固定N bit | 固定 | 无歧义 | ASCII, Unicode |
| 变长编码（非前缀） | 按频率分配不同长度 | 可变 | 可能歧义 | 不实用 |
| Huffman前缀编码 | 按频率分配+前缀码约束 | 可变 | 无歧义 | DEFLATE, JPEG |
| 算术编码 | 整条消息映射到一个数 | 分数级 | 无歧义 | ZSTD, brotli |
Huffman 编码的关键约束是"前缀码"：任何一个字符的编码都不是另一个字符编码的前缀。比如字符 A 编码为"0"，那么其他字符的编码都不能以"0"开头，只能以"1"开头。这样解码时逐 bit 读取，遇到完整码字就立即解码，不会产生歧义。
二、Huffman 编码原理详解
Huffman 编码的生成分三步：频率统计、构建哈夫曼树、生成编码表。整个过程是一个贪心算法——每次选择频率最低的两个节点合并，最终形成一棵最优二叉树。
1. 频率统计
第一步是统计输入数据中每个字符的出现频率。以"ABRACADABRA"为例，先统计每个字符出现次数。
| 字符 | 出现次数 | 频率(%) | 定长编码(3bit) |
|---|---|---|---|
| A | 5 | 45.5% | 000 |
| B | 2 | 18.2% | 001 |
| R | 2 | 18.2% | 010 |
| C | 1 | 9.1% | 011 |
| D | 1 | 9.1% | 100 |
5 种字符，定长编码需要 ceil(log2(5))=3 bit/字符，11 个字符共 33 bit。注意 ASCII 编码下需要 11×8=88 bit，定长 3 bit 已经省了 70%，但 Huffman 还能进一步压缩。
2. 构建哈夫曼树
哈夫曼树的构建是贪心过程：每次从所有节点中选出频率最低的两个，合并为一个新节点，新节点频率为两者之和。重复直到只剩一个根节点。
| 步骤 | 操作 | 合并前最低两个节点 | 合并后新节点 | 剩余节点 |
|---|---|---|---|---|
| 1 | 合并C(1)和D(1) | C:1, D:1 | CD:2 | A:5, B:2, R:2, CD:2 |
| 2 | 合并B(2)和R(2) | B:2, R:2 | BR:4 | A:5, CD:2, BR:4 |
| 3 | 合并CD(2)和BR(4) | CD:2, BR:4 | CDBR:6 | A:5, CDBR:6 |
| 4 | 合并A(5)和CDBR(6) | A:5, CDBR:6 | Root:11 | 完成 |
构建完成后，从根节点出发，左分支标记 0、右分支标记 1，走到每个叶子节点的路径就是该字符的 Huffman 编码。频率最高的 A（5 次）在树的第二层，编码仅 1 bit；频率最低的 C 和 D 在最深层，编码 3 bit。
3. 生成编码表
从哈夫曼树根节点遍历到每个叶子节点，记录路径上的 0/1 序列，即得到编码表。
| 字符 | 频率 | Huffman编码 | 码长 | 编码贡献(bit) |
|---|---|---|---|---|
| A | 5次 | 0 | 1 | 5×1=5 |
| B | 2次 | 100 | 3 | 2×3=6 |
| R | 2次 | 101 | 3 | 2×3=6 |
| C | 1次 | 110 | 3 | 1×3=3 |
| D | 1次 | 111 | 3 | 1×3=3 |
验证前缀码特性：A 的编码"0"不是任何其他编码的前缀；B"100"、R"101"、C"110"、D"111"互不为前缀。解码时逐 bit 读取，遇到"0"就是 A，遇到"1"再读两位即可区分 B/R/C/D，无歧义。
三、实战案例："ABRACADABRA"编码对比
现在用生成的编码表对"ABRACADABRA"进行完整编码，对比定长编码和 Huffman 编码的体积差异。
原文： A B R A C A D A B R A（11个字符）
编码过程：
| 位置 | 字符 | Huffman编码 | 累计bit |
|---|---|---|---|
| 1 | A | 0 | 1 |
| 2 | B | 100 | 4 |
| 3 | R | 101 | 7 |
| 4 | A | 0 | 8 |
| 5 | C | 110 | 11 |
| 6 | A | 0 | 12 |
| 7 | D | 111 | 15 |
| 8 | A | 0 | 16 |
| 9 | B | 100 | 19 |
| 10 | R | 101 | 22 |
| 11 | A | 0 | 23 |
编码效率对比：
| 编码方式 | 每字符bit | 总bit数 | 总字节 | vs ASCII压缩率 |
|---|---|---|---|---|
| ASCII编码 | 8 | 88 | 11 | —（基准） |
| 定长3bit编码 | 3 | 33 | 5 | 62.5% |
| Huffman编码 | 2.09（平均） | 23 | 3 | 73.9% |
| 理论熵下界 | 2.04 | 22.5 | 3 | 74.4% |
结果： Huffman 编码将 11 个字符从 ASCII 的 88 bit 压缩到 23 bit，节省 73.9%。即使对比定长 3 bit 编码也节省了 30%。而理论熵下界为 22.5 bit，Huffman 编码仅比理论最优多 0.5 bit，效率达到 97.8%。这就是 Huffman 编码被称为"最优前缀码"的原因。
四、Huffman 编码在主流压缩算法中的应用
Huffman 编码很少单独使用，通常作为压缩流水线的最后一个阶段——熵编码。前面先用 LZ77 等字典算法消除重复模式，再用 Huffman 编码对残差数据做频率压缩。下表列出主流压缩格式中 Huffman 的应用方式。
| 压缩格式 | 字典阶段 | 熵编码阶段 | Huffman变体 | 典型压缩率 |
|---|---|---|---|---|
| DEFLATE (ZIP/GZIP) | LZ77 | Huffman | 静态+动态Huffman | 50%–70% |
| PNG | LZ77 | Huffman | DEFLATE内置Huffman | 50%–75% |
| JPEG | DCT变换 | Huffman | 对DC/AC系数分别编码 | 10:1（视觉无损） |
| ZSTD | LZ77变体 | FSE/Huffman | 有限状态熵+Huffman混合 | 60%–80% |
| brotli | LZ77+上下文 | Huffman+算术 | 上下文Huffman | 65%–85% |
| BZIP2 | BWT变换 | Huffman | 多表Huffman | 70%–85% |
关于 LZ77 字典压缩的详细原理，可以参考LZ77 算法详解：字典压缩是怎么工作的？。PNG 格式中 DEFLATE 的具体应用，可以参考PNG 압축 원리详解。
五、常见问题FAQ
Q1：Huffman编码是什么？
Huffman 编码是一种最优前缀变长编码方式，由 David Huffman 于 1952 年提出。核心思想是：出现频率高的字符用短编码，频率低的字符用长编码，从而让整体编码长度最短。它通过构建哈夫曼树来生成编码表，保证任何一个字符的编码都不是另一个字符编码的前缀（前缀码特性），解码时不会产生歧义。
Q2：Huffman编码为什么是最优前缀码？
Huffman 编码的最优性基于贪心策略：每次从频率最低的两个节点合并，频率低的节点被放在树的深层（编码长），频率高的节点在浅层（编码短）。数学上可证明，对于给定字符频率分布，Huffman 编码的期望码长不小于任何其他前缀编码的期望码长，即达到熵编码的理论下界（信源熵 H）。在 ABRACADABRA 示例中，Huffman 编码 23 bit，理论熵下界 22.5 bit，效率 97.8%。
Q3：Huffman编码和算术编码有什么区别？
Huffman 编码按字符级别编码，每个字符分配独立的变长码字；算术编码用整个消息映射到一个 [0,1) 区间的小数，编码粒度更细。Huffman 编码实现简单、速度快，但受限于字符级编码，无法逼近信源熵；算术编码压缩率更高（可逼近熵值），但计算复杂度更高。DEFLATE 用 Huffman，现代 ZSTD/brotli 两者结合使用。
Q4：Huffman编码在哪些压缩格式中使用？
Huffman 编码是 DEFLATE（ZIP/GZIP/PNG）的核心组件，与 LZ77 配合使用；ZSTD 使用 FSE（有限状态熵编码）作为 Huffman 的替代但原理相通；brotli 和 JPEG（DC/AC 系数）也使用 Huffman 编码。几乎所有主流无损压缩格式都包含 Huffman 或其变体作为熵编码阶段。
总结
Huffman 编码是压缩算法的基石，核心原理是"高频短码、低频长码"，通过构建哈夫曼树生成最优前缀编码。以"ABRACADABRA"为例，11 个字符从 ASCII 88 bit 压缩到 23 bit，效率达到理论熵下界的 97.8%。Huffman 编码几乎存在于所有主流无损压缩格式中，与 LZ77 字典算法配合构成 DEFLATE/ZSTD 等经典压缩流水线。
理解 Huffman 编码的关键是三点：一是频率统计决定编码长度分配，二是哈夫曼树的贪心构建保证最优性，三是前缀码约束保证解码无歧义。掌握了 Huffman 编码，就掌握了理解所有现代压缩算法的钥匙。