整数比特的税：霍夫曼不够好
上一章那个「多付不到 1 比特」的保证听起来很不错。但如果整个熵才 0.469 比特，多付 0.53 就是多付一倍还多。这一章把这笔税算清，并被它逼到墙角。
一个信息源只有两种符号，概率 0.9 和 0.1。熵是 0.469 比特。用霍夫曼编码，平均码长是多少？
一个荒谬的数字
答案是 D，而且理由简单得让人生气：只有两个符号，霍夫曼树只能长成一个根加两片叶子。两个码字必然是 0 和 1，各占 1 比特。
不管概率是 0.9/0.1、0.99/0.01 还是 0.999999/0.000001，霍夫曼给出的答案永远是同一个：1 比特。
熵 H = 0.469 比特/符号 霍夫曼 L = 1.000 比特/符号 多付 0.531 比特/符号 多付的比例 0.531 / 0.469 = 【113.2%】 # 你付了两倍多的钱。 # 而第 6 章那条「不超过 H+1」的保证，在这里毫无安慰作用—— # 因为 H 本身就不到 1。
理想码长是 −log₂ 0.9 = 0.152 比特。
霍夫曼必须给一个整数。而 0.152 向上取整是 1。
这就是全部病因，它有个名字叫取整损失。而且注意：概率越极端，损失越大——恰恰在「最应该省」的地方，霍夫曼最省不下来。
一条自然的补救：打包
既然一个符号分不到小数个比特，那就把好几个符号绑在一起当成一个「超符号」，再对超符号做霍夫曼。这样那些小数就有机会互相抵消。
把两个符号绑在一起，就有四种超符号：
超符号 概率 理想码长 00 0.9×0.9 = 0.81 0.304 01 0.9×0.1 = 0.09 3.474 10 0.1×0.9 = 0.09 3.474 11 0.1×0.1 = 0.01 6.644 霍夫曼给出：00→0 01→10 10→110 11→111 平均码长 = 0.81×1 + 0.09×2 + 0.09×3 + 0.01×3 = 1.29 比特 / 【两个符号】 折合每符号 = 0.645 比特 # 从 1.000 降到 0.645。多付的比例从 113% 降到 【37.5%】。
有效。继续加：
把「打包几个符号」的滑杆一路拖过去，看那条柱子怎么往地板贴：
| 打包 k 个 | 超符号种数 | 每符号码长 | 多付 | 多付比例 |
|---|---|---|---|---|
| 1 | 2 | 1.0000 | 0.5310 | 113.2% |
| 2 | 4 | 0.6450 | 0.1760 | 37.5% |
| 3 | 8 | 0.5327 | 0.0637 | 13.6% |
| 4 | 16 | 0.4925 | 0.0236 | 5.0% |
| 5 | 32 | 0.4802 | 0.0112 | 2.4% |
| 6 | 64 | 0.4702 | 0.0012 | 0.2% |
| 7 | 128 | 0.4743 | 0.0053 | 1.1% |
| 8 | 256 | 0.4758 | 0.0068 | 1.5% |
两件事值得停一下。
一、它不是单调下降的
k = 6 的时候多付 0.2%，k = 7 反而涨回 1.1%。这不是计算错误。
霍夫曼的冗余量是随分布「抖动」的——它取决于那一组概率和 2 的幂之间的相对位置，而这个关系随 k 变化时并不单调。理论保证的是「k 足够大时冗余趋于 0」，不是「每一步都更好」。
这种「渐近保证不等于逐步改善」的现象在工程里很常见，值得记一笔。
二、代价是指数级的
这才是要命的地方：超符号的数量是 2ᵏ（更一般地，是 |字母表|ᵏ）。
# 二元信源： 打包 8 个 → 256 个超符号 还行 打包 16 个 → 65536 个超符号 码表开始变大 打包 20 个 → 1048576 个超符号 一百万行的码表 # 而如果字母表是 27 个字符（英文）： 打包 2 个 → 729 还行 打包 3 个 → 19683 勉强 打包 4 个 → 531441 五十万行 打包 5 个 → 14348907 一千四百万行，为了压一个文本文件
而这一千四百万行的码表你还得传给解码方。
打包这条路的困境非常清楚：
- 要把取整损失压到可忽略，k 必须足够大；
- 但码表大小随 k 指数增长；
- 而码表本身也要传输或存储。
于是省下来的和多花出去的在某个 k 上打平，再往后就是纯亏。这不是实现得不够好，是这套办法的结构缺陷。
问题的根源在最开始那个假设：「每个符号对应一个码字」。只要还抱着这个假设，你就必须给每个符号一个整数长度，就必须付取整的税。
所以真正的出路是放弃这个假设。
换一个问法
停下来重新想一遍这件事。
我们一直在问：「怎么给每个符号分配一段比特？」
但第 5 章那个典型集的论证其实提示了另一个问法：「怎么给整条消息分配一个编号？」
回忆一下：长度 n 的序列里，真正会出现的只有约 2^(nH) 条。如果我能给这些序列排个号，一个号就是 nH 比特——而 nH 是一个整数，取整损失只在整条消息上发生一次，不是每个符号发生一次。
# 霍夫曼的账： 每个符号取整一次，n 个符号 → 【n 次取整损失】 # 「给整条消息编一个号」的账： 整条消息取整一次 → 【1 次取整损失】 # 消息越长，第二种办法的平摊损失越接近 0。 # 而第一种办法的损失是恒定的每符号 0.531 比特，永远不会变小。
问题只剩一个：怎么在不枚举 2^(nH) 条序列的前提下，给它们编号？
这个「怎么」就是下一章。而答案的形状会有点出人意料：不需要枚举，也不需要码表，只需要一个不断变窄的区间。
取整损失听起来很学术，但它在几个地方是真金白银：
- 黑白传真 / 二值图像。大片白色区域里，「白」的概率可能是 0.99，理想码长 0.014 比特。霍夫曼给 1 比特，多付 70 倍。这就是为什么 JBIG2 和 JPEG 2000 用的是算术编码，不是霍夫曼。
- 视频编码的熵编码层。H.264 有两种模式：CAVLC（变长码，本质是霍夫曼那一路）和 CABAC（上下文自适应二元算术编码）。CABAC 通常比 CAVLC 省 9%–14% 码率，代价是算得慢。H.265/H.266 干脆只保留了 CABAC。
- 现代通用压缩。zstd 和 Brotli 用的是 ANS（非对称数系）——它是一种「兼具算术编码的精度和查表的速度」的新做法，2013 年才被提出。压缩这门老学问里，最基础的一层在十几年前还在出新东西。
永远看相对损失：(L − H) / H。
这是一个很通用的读数警觉。「误差不超过 0.5」这类绝对界，在被测量本身很小的时候没有意义。同样的陷阱在模型评估里也有：「准确率提高了 2 个百分点」，从 50% 到 52% 和从 97% 到 99% 是完全不同的两件事——后者把错误率砍了三分之二。
如果你选了 A 或 B，那是被第 6 章那句「霍夫曼是最优的」带偏了——它确实是最优的，但只在「一符号一码字」这个笼子里最优。笼子外面还有很大空间。
这一章真正的收获不是这个数字，是这个思路：当一个方法在某处表现荒谬时，去看它最开始接受了什么前提。霍夫曼的荒谬全部来自「一个符号对应一段比特」这个从来没人质疑过的假设。
这一章的一句话
霍夫曼必须给每个符号一个整数长度，于是在概率极端的地方要多付一倍以上的税。打包能摊薄它，但码表指数增长——真正的出路是不再给符号分配比特。
下一章是这本书里第一个「看上去不像编码」的编码方法。算术编码不给任何符号分配比特，它做的事是：把 [0, 1) 这条线段反复切窄，最后报出落在里面的一个数。这个想法把取整损失从「每符号一次」变成「整条消息一次」——在真语料上，它比理论地板只多了 1 个比特。不是每字符多 1 比特，是整整两千多个字符一共多 1 比特。