卷 II · 省CH 08深度 8/24

算术编码：把整条消息编成一个小数

这是全书第一台真正踩到地板上的机器。它的想法和霍夫曼完全不同——它不做码表，不分配码字，它只做一件事：把一条线段反复切窄。

★★ 真算术编码区间条母题只多 1 比特
▷ 先猜一下

用算术编码压一段 2053 个字符的英文（零阶模型，熵地板 8287 比特）。真编出来的比特串，比理论地板多多少？

A 每个字符多约 0.1 比特（总共多两百多）B 总共多几十比特C 总共多几比特D 总共多 1 比特

换一个完全不同的想法

忘掉码表，忘掉树。看这条线段：

A　0.7 B　0.2 C　0.1
[0, 1) 按概率切成三段。宽度就是概率，格下的数字是 −log₂(宽度)。

现在，编码一条消息的规则只有一句：

◆ 算术编码（就这一句）

读到一个符号，就把当前区间按同样的比例再切一遍，然后只保留那个符号对应的那一段。

读完整条消息，你手上剩下一个很窄的区间。报出落在这个区间里的任意一个数，编码就完成了。

手跟一遍，消息是 AAB：

起始区间             [0.0000, 1.0000)   宽 1.0000

读到 A → 取前 70%    [0.0000, 0.7000)   宽 0.7000
读到 A → 再取前 70%  [0.0000, 0.4900)   宽 0.4900
读到 B → 取 70%~90%  [0.3430, 0.4410)   宽 0.0980

# 最终区间宽度 = 0.7 × 0.7 × 0.2 = 0.098
# 而 0.098 正是【这条消息的概率】。

# 要报出一个落在 [0.3430, 0.4410) 里的数，需要多少比特？
   −log₂(0.098) = 3.351 比特

# 而这三个符号的自信息之和：
   0.515 + 0.515 + 2.322 = 3.351 比特      ← 一模一样
◆ 为什么它必然踩在地板上

最终区间的宽度 = 每一步概率的乘积 = 整条消息的概率 P(消息)。

而要指定一个落在宽度 w 的区间里的数，需要约 −log₂ w 比特。

于是：比特数 = −log₂ P(消息) = Σ(−log₂ p(每个符号))。

这正好是每个符号的自信息之和，也正好是熵乘以长度。取整只在最后报数的时候发生一次，不是每个符号发生一次。第 7 章那笔税，就这么被摊到了整条消息上。

下面这台是真的：它一步步给你看区间怎么缩，最后跑一个真的 30 位整数区间编码器，编完再解回来：

三个必须解决的工程问题

上面的想法很漂亮，但直接照着写会立刻死。三个问题，每一个都有一个漂亮的解法。

问题一：小数会耗尽精度

编到第 50 个符号时，区间宽度大概是 2⁻¹⁵⁰。双精度浮点在 2⁻⁵³ 就废了。

解法：区间一旦确定了最高位，就把那一位吐出来，然后把区间放大一倍。

# 如果整个区间都落在 [0, 0.5) 里
#   → 那这个数的二进制第一位一定是 0
#   → 吐出 0，然后把区间 ×2 拉回 [0,1)

# 如果整个区间都落在 [0.5, 1) 里
#   → 第一位一定是 1
#   → 吐出 1，减掉 0.5，再 ×2

# 于是区间永远不会窄到超过精度，
# 比特是【边编边流出来】的，不是最后一次性算出来的。

问题二：区间骑在中点上，卡住不动

如果区间是 [0.4999, 0.5001)——它既不完全在左半边，也不完全在右半边，最高位还没定下来，但区间已经很窄了。

这个情况叫下溢（underflow），是算术编码实现里最容易写错的地方。

# 解法：如果区间落在中间那一半 [0.25, 0.75) 里，
#   → 我们不知道第一位是 0 还是 1，
#   → 但我们知道：【第一位和第二位一定相反】
#     （0.4999 → 0.0111…    0.5001 → 0.1000…）
#   → 于是记一笔「欠一个反转位」，把区间围绕中点放大，继续。
#   → 等到第一位终于确定了，就把欠着的反转位一次性补上。

# 这就是代码里那个 pending / underflow 计数器。
# 这本书的引擎里那几行就是干这个的。

问题三：整数运算

真实实现里不用浮点，用整数——因为编码器和解码器必须逐位一致，而浮点在不同平台上可能有微小差异，一位不同整条消息就全废了。

这本书的引擎用 30 位整数区间。精度账要自己算清楚：区间最大 2³⁰，频率总和最大 2¹⁸，乘积 2⁴⁸，还在双精度整数（2⁵³）的安全范围内。这类边界如果没算，程序会在跑了几千个符号之后毫无征兆地解出乱码。

拿真语料跑一次

在上面那个 demo 里点「压缩 2053 字符的英文语料」。结果是：

方式比特字节说明
原文 ASCII1642420538 比特一个字符
定长 5 比特码10265128427 种符号，2⁵ 够用
霍夫曼83611046比地板多 74 比特
算术编码82881036比地板多 1 比特
熵的地板 H×n828710364.0365 × 2053

整整两千零五十三个字符，一共只多花了 1 个比特。

而且解码验证一字不差——那不是「理论上应该」，是 demo 里真的编了又解了一遍再逐字符比对的结果。

◆ 这一步比它看起来重要得多

算术编码解决的不只是「省那点取整损失」。它解锁了一件霍夫曼结构上做不到的事：

每个符号可以用不同的概率分布来编。

霍夫曼必须先建一棵树，然后整篇文章用同一棵。而算术编码每一步只需要「当前这一步的概率表」——这张表可以每一步都不一样，只要解码方能算出同一张表。

而解码方看到的历史和编码方完全相同（它已经解出前面所有符号了），所以任何「基于已解码内容」的模型都可以用。

这一句话就是第三卷的全部前提。它意味着你可以把任意一台预测模型——n-gram、神经网络、大语言模型——直接插到算术编码器上，得到一台压缩器。第 12 章会真的这么干。

▸ 在现实里：为什么你没听说过它

算术编码明明更好，为什么 zip 用的还是霍夫曼？

  1. 专利。1980–2000 年代，IBM 等公司持有大量算术编码相关专利。JPEG 标准里其实定义了算术编码模式，但因为专利问题，几乎没有实现支持它——所以你手上每一张 JPEG 都在为专利多付 5%–10% 的体积。这些专利现在都过期了。
  2. 速度。霍夫曼解码可以用查表，一次出好几位；算术编码每个符号都要做乘除法。在 CPU 慢的年代这个差距很要命。
  3. 它其实无处不在，只是名字不叫这个。H.264/H.265 的 CABAC、JPEG 2000 的 MQ 编码器、CABAC 之前的 QM 编码器、以及现代的 zstd/Brotli 用的 ANS（非对称数系，2013 年提出）——全都是算术编码这一族。

ANS 值得单独提一句：它用一个整数状态代替区间，做到了「算术编码的精度 + 查表的速度」。这是压缩领域近十几年最重要的实用进展，而它出自一位波兰物理学家 Jarosław Duda 之手。一个看起来早就做完了的领域，基础层在十几年前还出了新东西。

✗ 这个直觉是错的
算术编码把消息变成一个小数，所以它需要无限精度的浮点数，实际上不可行。 它从来不真的算那个小数。它只维护一个整数区间的上下界，一旦最高位确定就吐出来并放大。任何时刻用到的都是固定位宽的整数。

这个误解很常见，因为几乎所有教科书都用 [0,1) 的小数来讲解——那是为了直观，不是实现方式。「概念上的模型」和「工程上的实现」在这里差得很远，而理解这个差距本身很有价值：很多算法都是这样，讲解版本和落地版本长得完全不一样。

◇ 结账
D：总共多 1 个比特

不是每字符 1 比特，是整条消息一共 1 比特。

选 A 的人还停在霍夫曼的思维里（损失是按符号累积的）；选 B、C 的人方向对了，只是低估了它有多干净。

那 1 个比特是收尾时为了「把区间钉死」多吐的位——它是一个常数，不随消息长度增长。所以消息越长，平摊的损失越接近零。

这一章的一句话

算术编码不给符号分配比特，它把区间反复切窄，最后报一个数。于是取整只发生一次，而且每一步都可以换一张概率表——后面这一点，比省下来的比特重要得多。

下一章是卷 II 的最后一章，也是一次换轨。前面四章走的都是「数概率」这条路。还有一条完全不同的路：不数概率，找重复。LZ77 看见的东西是概率表看不见的——它能抓到「request_id= 这七个字符刚才出现过」，而字符频率表对此一无所知。两条路各有主场，而 gzip 的做法是两条一起走。