霍夫曼：一棵按概率长出来的树
上一章说地板在熵。这一章造第一台真能踩到地板附近的机器——而且它的算法只有一句话，你在读完这句话之后能自己在纸上把它跑出来。
四个符号 A、B、C、D，概率 0.5 / 0.25 / 0.125 / 0.125。定长编码要 2 比特一个。霍夫曼编码平均要多少？
一个交不出论文的研究生
1951 年，MIT 的信息论课上，罗伯特·法诺（Robert Fano，香农的同事）给学生一个选择：写一篇期末论文，或者解决一个开放问题——找出最优的前缀码。
大卫·霍夫曼（David Huffman）选了后者，然后卡了几个月。据他后来回忆，在决定放弃、准备去写论文的那天，他把笔记扔进垃圾桶的一瞬间想通了。
他不知道的是，法诺本人和香农都试过这个问题，都没解决。
而解法只有一句话：
每次取走概率最小的两个，合并成一个新节点（概率相加），放回去。重复到只剩一个。
剩下的那个就是树根。从根往下走，左边记 0，右边记 1，走到每片叶子记下的那串就是它的码。
为什么这样做是对的？两个观察就够：
- 最不可能的两个符号，一定在树的最深处，而且一定是兄弟。如果不是，你把它们换到最深处会让平均码长变小——所以最优解必然长这样。
- 把这两个合并成一个「超级符号」之后，问题变成了一个少一个符号的同类问题。递归下去。
这两句话就是完整的最优性证明。整个算法和整个证明加起来不到一段话，而它至今仍活在你打开的每一个 zip、每一张 PNG、每一个 JPEG 里。
手算一遍
符号 概率
A 0.5
B 0.25
C 0.125
D 0.125
第一步：最小的两个是 C(0.125) 和 D(0.125) → 合成 CD(0.25)
剩下：A(0.5) B(0.25) CD(0.25)
第二步：最小的两个是 B(0.25) 和 CD(0.25) → 合成 BCD(0.5)
剩下：A(0.5) BCD(0.5)
第三步：合成根(1.0)
剩下：根
从根往下（左 0 右 1）：
A = 0
B = 10
C = 110
D = 111
平均码长 = 0.5×1 + 0.25×2 + 0.125×3 + 0.125×3 = 【1.75 比特】
熵 = 0.5×1 + 0.25×2 + 0.125×3 + 0.125×3 = 【1.75 比特】
↑ 完全相等
平均码长恰好等于熵。定长编码要 2 比特，省了 12.5%。
为什么这次能完美相等？因为每个概率都是 2 的幂，−log₂p 正好是整数——理想码长可以被整数码长精确实现。这个「正好」是特例，不是常态。第 7 章整章都在讲不正好的时候会怎样。
下面这台是真的：换一段文本，树会当场重新长一遍，码表重出，编码解码全跑一遍：
读一读那棵树告诉你的事
把 demo 切到「英文语料前 300 字」那一档，看那张码表。有三件事值得注意。
一、码长就是负对数，四舍五入
表里那一列「理想码长 −log₂p」和「霍夫曼码长」几乎总是差不到 1。空格出现得最多，拿到最短的码；x 只出现一次，拿到最长的。这不是编码器「聪明」，这是它在按第 5 章那条公式办事。
二、克拉夫特和恰好是 1
demo 里那个「克拉夫特和」显示 1.000000。回忆第 5 章：Σ2⁻ˡ ≤ 1 是前缀码的约束，取等号意味着这棵二叉树一片空地都没剩。
这是霍夫曼最优性的一个直观证据：如果树上还有空位，就说明某个码字本可以更短。它把每一寸都用掉了。
三、解码不需要分隔符
demo 底下那串比特是连着写的，没有任何分隔。而解码器能一位一位往下走，走到叶子就吐出一个符号然后回到根。这就是「前缀码」这三个字的全部实际价值。
# A=0 B=10 C=110 D=111 # 解码 0 1 0 1 1 0 1 1 1 0 ： 0 → 叶子 A ✓ 吐出 A，回根 1 0 → 叶子 B ✓ 吐出 B，回根 1 1 0 → 叶子 C ✓ 吐出 C，回根 1 1 1 → 叶子 D ✓ 吐出 D，回根 0 → 叶子 A ✓ 吐出 A # ABCDA。没有一位是浪费在「这里是边界」上的。
- 变长码：不同符号的码字长度不同。这是目标。
- 唯一可译码：任何一串编码只能被解读成一种符号序列。这是必须满足的。
- 前缀码：没有码字是另一个的前缀。这不是唯一可译的必要条件——存在不是前缀码但唯一可译的码。
那为什么大家都用前缀码？因为有一条定理（麦克米伦不等式）说：任何唯一可译码的码长集合，都能被某个前缀码达到。换句话说，非前缀码没有任何长度上的好处，却要付出「解码要往后看」的代价。所以前缀码不是一种限制，是一次免费的简化。
霍夫曼在现实里跑在哪
- DEFLATE（zip / gzip / PNG / HTTP 的
Content-Encoding: gzip）：先 LZ77 找重复（第 9 章），再对结果做霍夫曼。而且它把码表也压缩了——用另一套霍夫曼码去编码「码长序列」。 - JPEG：DCT 变换 + 量化之后的系数，用霍夫曼编码。标准里甚至内置了几张「典型码表」，省得每张图都传一遍。
- MP3：频域系数用霍夫曼，标准里有 32 张预置码表可选。
- HTTP/2 的 HPACK：头部字段用一张固定的霍夫曼表（针对 HTTP 头的字符分布训练出来的）。
注意这些场合的一个共同点：码表要么随数据一起传，要么写死在标准里。这是霍夫曼的一项隐性成本——你不只要传编码后的数据，还要让对方知道你用的是哪棵树。对小文件来说，这个开销可能比省下来的还多。
那个「码表要多大」的账
拿 demo 里的英文语料算一下：27 个符号，码表大约要写 27 个（符号，码长）对。就算精打细算，也要一两百比特。而这段文本压缩后是 8288 比特，码表占 2% 左右——可以接受。
但如果你要压的是一条 20 字节的日志，情况就反过来了。这是「小文件压不动」的主要原因之一，另一个原因是第 13 章那个字母表成本。
这句限定不是学究气，它正好圈出了霍夫曼的两个失效场景：
- 概率极度倾斜时。一个概率 0.9 的符号，理想码长是 0.152 比特，但霍夫曼最少只能给它 1 比特——多付了 6.6 倍。第 7 章会把这笔账算清。
- 符号之间有关联时。霍夫曼只看单个符号的频率。它不知道
q后面几乎一定是u，所以它给u的码长在任何位置都一样。而在q后面，u本该只值 0.05 比特。第 12 章那台模型会把这部分全捞回来。
有一条经典结论把霍夫曼的损失夹住了：
H ≤ L(霍夫曼) < H + 1 # 平均码长不会比熵多出 1 个比特。 # 这个 1 是最坏情况，通常远小于 1。
拿真语料验一下：demo 里英文语料的熵是 4.0365，霍夫曼平均码长 4.0726，只多了 0.036 比特。
所以对英文这种「分布不算极端、符号种类不少」的数据，霍夫曼已经非常接近最优了。它的病只在极端处发作——但极端的地方恰好是最值钱的地方。第 7 章见。
如果你选 A，那是没意识到变长码的威力；选 C 或 D，那是高估了——1.75 已经是地板，不可能更低了。
这一题的答案之所以「正好」，是因为概率全是 2 的幂。而下一章会问一个更尖锐的问题：如果概率是 0.9 和 0.1，霍夫曼能做到多好？答案是它只能给出 1 比特——而熵只有 0.469。多付 113%。
这一章的一句话
霍夫曼编码是一棵按概率长出来的树，算法只有一句话，而且在「一符号一码字」的前提下可证明最优——问题全在这个前提上。
下一章：把那个前提捅破。当一个符号的理想码长是 0.152 比特，而你最少只能给 1 比特的时候，会发生什么？我们会看到一个荒谬的数字（多付 113%），也会看到一条自然但走不远的补救之路，然后被逼到第 8 章那个真正的解法上——一个不给符号分配比特、而是给整条消息分配一个小数的办法。