我们每天都在跟压缩打交道，下载的 zip 包、浏览的 PNG 图片、听的 MP3 歌曲，体积之所以能远小于原始数据，背后多半站着同一位老将：霍夫曼编码。它是 1952 年由 David Huffman 提出的一种无损压缩算法，核心想法朴素得很，出现次数多的字符用短编码，出现次数少的字符用长编码，并且保证任何一个字符的编码都不是另一个字符编码的开头。这样一边把平均长度压下来，一边还能无歧义地还原。今天它虽然很少单独使用，却几乎嵌在所有现代压缩格式的收尾阶段，是理解数据压缩绕不开的一块基石。
这一节我们先从为什么要给字符变长编码讲起，再用权值 2、4、5、8 这样的小例子一步一步搭出霍夫曼树，随后拿一段真实文本走完整的统计频率、建树、出编码表、压缩和解码流程，最后专门说清楚它为什么能保证总位数最短，以及它在真实压缩软件里的位置和边界。读之前只需要知道二叉树长什么样、二进制位是什么，别的都不用提前准备。
1. 变长编码
我们先从压缩要解决的麻烦说起。
一段文本里每个字符都用 8 位 ASCII 存着，7 个字符 ABCDEFG 就占 7 个字节。问题在于，字符出现的次数并不均匀。把只出现一次的 E 和出现了几百次的 A 一视同仁地都给 8 位，显然浪费。最直接的想法就是重新编码，让高频字符少占几位、低频字符多占几位。
ABCDEFG
但变长编码马上撞上一个坑。假设我们把 A 编成 “100”、把 B 编成 “10”，接收方拿到一串 1000 时就犯难了，它到底该先读出 10 还是先读出 100，两种拆法还原出的字符不一样。所以，好的变长编码必须满足一条硬规矩：任何一个字符的编码都不能是另一个字符编码的前缀，这就叫前缀码。有了这条规矩，编码流才能从左到右一趟扫完就还原，不用回头猜。
2. 建树原理
变长编码加上前缀码这两条要求，靠人工给字符拍脑袋分配长度是拍不出来的。霍夫曼的解法，是把它变成一个建树问题。
给定 N 个字符，我们把每个字符的出现次数当作权值，让这 N 个权值各自当一片叶子，去拼一棵二叉树。拼好之后，从根走到某片叶子路过几条边，那个字符的编码就有几位。我们希望出现次数越多的字符离根越近，这样它的编码就越短。形式化地说，就是要让带权路径长度最小，它等于每片叶子的权值乘以它到根的边数再求和。达到这个最小值的二叉树，就叫霍夫曼树，也叫最优二叉树。
建树的动作，其实是反复做同一件事。先把所有叶子按权值从小到大排好，每次取出当前权值最小的两个，让它们当左右孩子，再新建一个父节点，父节点的权值就是这两个孩子权值之和。然后把这个父节点插回队列重新排序，不断重复，直到队列里只剩一个节点，那就是根。
我们拿一组权值 2、4、5、8 走一遍，合并过程如下表。
| 步骤 | 待合并队列(从小到大) | 取出的两个最小权值 | 新父节点 |
|---|---|---|---|
| 1 | 2、4、5、8 | 2、4 | 6 |
| 2 | 5、6、8 | 5、6 | 11 |
| 3 | 8、11 | 8、11 | 19 |
第一步，把最小的 2 和 4 合成 6，队列变成 5、6、8。第二步，把 5 和 6 合成 11，队列变成 8、11。第三步，把 8 和 11 合成 19，根就出来了。整棵树里 8 离根最近，只走一条边，5 走两条边，2 和 4 要走三条边。权值越大的叶子离根越近，这正是我们想要的。
这棵树的带权路径长度是 8×1 + 5×2 + 2×3 + 4×3 = 36。如果反过来，把大的权值放在深处、小的权值放在浅处，这个和立刻就变大。整棵树的形状示意待补图。
还有一个细节要交代。当队列里出现两个权值相同的节点时，谁左谁右、先合并谁后合并谁，拼出来的树可能长得不一样。但只要每一步都选最小的两个合并，不管怎么选，最终的带权路径长度都一样，都是最小值。这个非唯一性，我们在第三节的真实例子里还会再碰到。
3. 完整实例
树会建了，我们再回到压缩这件事本身。拿一段真实文本从头到尾走一遍，你就能自己写出一个压缩解压程序。
3.1 频率统计建树
待压缩的文本是 ABAABCDCCCE，一共 11 个字符。我们先数每个字符出现多少次，把次数当权值。
ABAABCDCCCE
| 字符 | A | B | C | D | E |
|---|---|---|---|---|---|
| 出现次数 | 3 | 2 | 4 | 1 | 1 |
按权值从小到大排队，就是 D1、E1、B2、A3、C4。然后反复取两个最小的合并，过程如下表。
| 步骤 | 待合并队列(从小到大) | 取出的两个最小权值 | 新父节点 |
|---|---|---|---|
| 1 | D1、E1、B2、A3、C4 | D(1)、E(1) | DE = 2 |
| 2 | B2、DE2、A3、C4 | B(2)、DE(2) | BDE = 4 |
| 3 | A3、C4、BDE4 | A(3)、C(4) | AC = 7 |
| 4 | BDE4、AC7 | BDE(4)、AC(7) | 根 = 11 |
第三步这里有个分叉。队列里 A 是 3，剩下 C 和 BDE 都是 4，按规则只能再拿一个 4 跟 A 合并。到底拿 C 还是拿 BDE？两种选择都合法，会长出两棵不同的树。我们这里先选 C，让 A 和 C 合成 AC。另一棵树放到本节末尾再对比。整棵树的形状待补图。
3.2 生成编码表
树拼好之后，编码规则一句话就能说清。从根出发往左走记 0、往右走记 1，把走到某片叶子路过的 0 和 1 连起来，就是那个字符的编码。
我们沿着这棵树逐条边走边记，五个字符的编码如下表。
| 字符 | 出现次数 | 从根出发的路径 | 霍夫曼编码 |
|---|---|---|---|
| A | 3 | 左、左 | 00 |
| B | 2 | 右、左 | 10 |
| C | 4 | 左、右 | 01 |
| D | 1 | 右、右、左 | 110 |
| E | 1 | 右、右、右 | 111 |
我们拿这张表把原文逐个替换，压出来的比特流如下。
A B A A B C D C C C E 00 10 00 00 10 01 110 01 01 01 111
我们数一下总位数。A 出现 3 次，每次 2 位，共 6 位。B 两次共 4 位，C 四次共 8 位，D 和 E 各一次都是 3 位。加起来 24 位，正好 3 个字节。而原来用 ASCII 存这 11 个字符要 11 个字节，压缩掉了一大半。等长编码和霍夫曼编码的账对比如下。
| 编码方式 | 单字符位数 | 11 个字符总位数 | 占用字节 |
|---|---|---|---|
| 等长 ASCII | 8 | 88 | 11 |
| 霍夫曼编码 | 1 到 3 不等 | 24 | 3 |
3.3 解码流程
压出来是一串没有间隙的 0 和 1，接收方怎么知道在哪断开呢？答案是再走一遍这棵树。
解码从根开始，一位一位读比特，遇到 0 往左、遇到 1 往右，一旦走到叶子就输出那个字符，然后立刻回到根重新开始。比如开头读到 0 往左走一步，再读 0 又往左走一步，已经落到 A 这片叶子，就先解出一个 A，再回到根。接下来读到 1 往右、0 往左，落到 B，解出 B。就这么一趟扫到底，11 个字符自动切开，不需要任何分隔标记。
之所以不用分隔符也切得开，靠的还是前缀码这条性质。字符全在叶子上，没有哪个字符的编码会在半路就命中另一个叶子，所以一旦走到叶子，必然是一个完整字符。
我们回到前面那个分叉。第三步如果当时选的是 BDE 而不是 C，会得到另一棵树，编码表变成 A=10、B=110、C=0、D=1110、E=1111。用它压同一段文本如下。
A B A A B C D C C C E 10 110 10 10 110 0 1110 0 0 0 1111
数一下还是 24 位、3 个字节。两棵树形状不同，平均码长却一模一样，这不是巧合，第四节会说明原因。
4. 最短性证明
例子看完了，我们最该追问的问题是：霍夫曼凭什么保证它压出来一定最短，而不是我们随手排的另一种长度。
4.1 贪心最优性
我们先把目标摆清楚。总位数就是带权路径长度，等于每个字符的出现次数乘以它的编码位数，我们要让这个和最小。霍夫曼每一步都选当前权值最小的两个节点合并，这个贪心动作背后的理由是：权值最小的字符一辈子都要待在树的最深处，多绕一层对总位数的贡献最小，那就把最不常见的字符往深里放。反过来，权值最大的字符一定在最浅的位置，它每少一位，省下的位数都要在它身上乘上最大的出现次数，这笔账最划算。
我们再用一个交换的思路看得严格一点。任何一棵最优前缀树里，权值最小的两个叶子一定可以被放到最深的一层做兄弟。如果它们不在最深，把它们跟最深的那两个兄弟叶子交换位置，总带权路径长度不会变大。把这两个最小权值合并看成一个新节点，原问题就缩小了一圈，变成在少一个叶子的树上继续求最优。这样一层层缩下去，正好就是霍夫曼每次合并两个最小节点的过程。所以，霍夫曼树达到的确实是带权路径长度的最小值。
4.2 前缀码原理
顺带说清楚另一件事，为什么霍夫曼编码天生就是前缀码。因为所有字符都放在叶子节点上，内部节点只是中转，不对应任何字符。从根走到某片叶子的路径，中途经过的都是内部节点，不会命中任何字符，也就不存在哪条路径是另一条路径的开头。前缀码这条要求，在建树的那一刻就自动满足了，不用额外设计。
这里要补一句边界。我们说的最优是有前提的，它是已知字符频率、按单个字符独立编码前提下的最优前缀码，并不等于世上最短的压缩。频率表本身要存进文件，编解码双方必须共用同一棵树，而且它不利用相邻字符之间的关联，所以后面会被更强的编码方法比下去。
5. 应用与局限
原理站得住了，我们看看它在真实软件里到底怎么出场，又有哪些做不好的地方。
霍夫曼很少单独当压缩软件，它通常是整条流水线的最后一道工序。gzip、PNG、JPEG、传真编码这些格式，前面先用字典替换或者预测变换把数据整理成符号流，最后才交给霍夫曼，按符号的实际频率配上变长前缀码收尾。你用 zip 压一个文本包，背后大致就是这条路。
用它的时候，有几条边界要心里有数。第一，频率表得跟着压缩文件一起存，不然对方解不出来，这也是为什么压缩包开头总有一段字典或表，文件特别小时这张表的开销可能比正文还大。第二，编解码两端必须用同一棵树，频率统计错了一位，解出来就是乱码。第三，当字符出现频率差不多时，长短编码拉不开差距，压缩收益很小。第四，它一个字符一个字符地编码，不看上下文，所以在强相关的数据上，算术编码和基于字典的 LZ 系列能压得比它更小，霍夫曼更多是作为这些方法的收尾搭档出现。
我们绕回来看，霍夫曼编码做的事其实就三步。数频率，按贪心合并出一棵权值越大离根越近的二叉树，再从根走分支给每个叶子配前缀码。它用深度换长度，把最常见的字符放在最短的路径上，换来理论上最短的平均码长，又因为字符全在叶子上而天然解码无歧义。今天它依然是几乎所有主流压缩格式的最后一环，理解了这棵树，再看 gzip、PNG 的压缩流程就有了主心骨。
冀公网安备13050302001966号