09 另一条路：不数概率，找重复

▷ 先猜一下

一段 2000 个碱基的随机 DNA（ACGT 各占四分之一）。哪种方法压得最小？

A LZ77（找重复）B gzip（LZ77 + 霍夫曼）C 算术编码（数概率）D 都一样，压不动

概率表的盲区

看这两行日志：

2026-08-09T07:23:11Z INFO request_id=418322 path=/api/v1/orders status=200 duration_ms=87
2026-08-09T07:23:14Z INFO request_id=418323 path=/api/v1/orders status=200 duration_ms=91

一个字符频率表看到的是什么？它看到 0 很多、2 很多、= 有几个。它会算出一个熵，大概比均匀分布低一点。

它完全看不见「第二行几乎就是第一行」。

因为「重复」这个结构不在单字符的频率里，它在字符之间的位置关系里。而第 2 章那个零阶熵，按定义就是把所有位置关系都扔掉之后剩下的东西。

◆ 两种完全不同的赌注

赌注一（数概率）：「某些符号比另一些更常出现。」→ 霍夫曼、算术编码。

赌注二（找重复）：「刚才出现过的一段，等会儿还会再出现。」→ LZ 家族。

这两件事没有包含关系。一段数据可以频率极其均匀（赌注一无从下手）却充满长重复（赌注二大获全胜），反之亦然。

LZ77：往回指

1977 年，以色列的两位研究者 Abraham Lempel 和 Jacob Ziv 提出了一个想法，简单到你会怀疑它为什么要等到 1977 年：

◆ LZ77（就这一句）

编码到某个位置时，往回看有没有出现过同样的一段。有的话，就不写内容，写一个「往回多少个字符、抄几个」的指针。

要编码：  abcabcabcabc

位置 0：a  往回没东西      → 字面量 'a'
位置 1：b  往回没有 b      → 字面量 'b'
位置 2：c  往回没有 c      → 字面量 'c'
位置 3：abcabcabc
        往回 3 个字符处开始，能匹配【9 个】字符
                            → 指针 ⟨往回 3, 抄 9⟩

结果：a  b  c  ⟨3,9⟩

# 注意最后那个指针：往回只有 3 个字符，却要抄 9 个。
# 这不是 bug，是 LZ77 最漂亮的地方——【匹配可以和自己重叠】。
# 解码时一个字符一个字符地抄，抄出来的字符立刻成为后面可抄的内容。
# 于是 ⟨3,9⟩ 自动展开成 abcabcabc。
#
# 这个特性让 LZ77 顺手拥有了游程编码的能力：
# 一万个连续的 0，写成 '0' + ⟨1, 9999⟩。

下面这台是真的，切换语料看它的 token 流（绿色的每一个 ⟨往回，抄几个⟩ 都是一次真匹配，鼠标停上去能看抄的是什么）：

三种语料，三种命运

把上面那个 demo 依次点一遍，你会看到 LZ77 的三张脸。

一、结构化日志：主场

40 行日志（3545 字符）	字节	压缩比
原文	3545	1.00
LZ77	907	3.9 : 1
算术编码（只看字频）	2235	1.6 : 1

LZ77 大胜。因为日志里重复的不是单个字符，是整段字符串：时间戳前缀、request_id=、路径、status=200。这些东西在频率表里完全不可见。

二、自然语言：两边都不占优

英文语料上，LZ77 只压到 1218 字节，反而比霍夫曼（1046 字节）还差。因为自然语言里长重复不多——你不会一整句话说两遍。

但字符分布也不算极端，所以数概率也省得有限。这就是为什么 gzip 是两台机器串起来的。

三、随机 DNA：一败涂地

2000 个随机碱基	字节	为什么
原文（每碱基 1 字节）	2000	浪费得很
LZ77	985	只找到一堆三四字符的短匹配，省下的不够付指针钱
gzip	667	LZ77 之后又做了一遍霍夫曼，捞回来一些
算术编码	500	恰好等于地板
2 比特直接打包	500	2000 × 2 / 8

算术编码正正好好踩在 500 字节上——因为随机 DNA 的熵就是每碱基 2 比特，2000 × 2 ÷ 8 = 500。

而 gzip，那个「什么都能压」的通用压缩器，在这里比一个两行的位打包差了 33%。

✗ 这个直觉是错的

gzip 是通用压缩器，所以它在任何数据上都不会太差。 gzip 押的是特定的两注：短程重复 + 字节频率倾斜。数据只要不吃这两注，它就毫无办法。

基因组数据是最经典的例子。所以生物信息学有一整套专用格式：

2bit / .nib：直接 2 比特一个碱基，不做任何「压缩」，就是不浪费。
CRAM：测序数据的标准格式，做的是「只记录和参考基因组的差异」——这本质上是把参考基因组当成一台预测模型，第 12 章那套思路。

同样的道理适用于任何数据：在扔给通用压缩器之前，先问一句「这份数据的结构是什么」。一个知道结构的十行程序，经常能打败一个不知道结构的通用算法几倍。

gzip 到底是什么

既然两条路各有盲区，最自然的做法就是串起来：

原文
  ↓
【LZ77】  找重复，输出：字面量 + ⟨距离, 长度⟩ 指针
  ↓
【霍夫曼】对「字面量和长度」建一棵树，对「距离」再建一棵树
  ↓
压缩结果

# 这个组合叫 DEFLATE，1996 年成为 RFC 1951。
# 你的每一个 .zip、.gz、每一张 PNG、每一次 Content-Encoding: gzip，
# 走的都是这两步。

为什么这个组合有效？因为两台机器互相补盲区：LZ77 把长重复吃掉，剩下的字面量和指针里还有频率倾斜（比如短距离的指针比长距离的常见得多），霍夫曼把这部分再吃一遍。

▸ 在现实里：LZ 这一族的家谱

LZ77（1977）：滑动窗口 + 往回指。→ DEFLATE / zip / gzip / PNG。
LZ78（1978）：建一本字典，指的是字典条目号。→ LZW（1984）→ GIF、早期 TIFF、Unix compress。LZW 的专利在 1990 年代引发了著名的 GIF 专利风波，PNG 就是那次风波的直接产物。
LZMA（7-Zip）：更大的窗口（可达 1 GB）+ 算术编码 + 上下文建模。慢，但压得狠。
zstd（Facebook，2016）：LZ77 + ANS（第 8 章那个）。它的意义是把「压得好」和「解得快」同时做到了，现在正在大规模取代 gzip。
Brotli（Google，2015）：LZ77 + 霍夫曼 + 一本内置的 120 KB 静态字典，里面是从网页语料里挑出来的常见片段（</div>、function、http:// 之类）。

Brotli 那本内置字典特别值得琢磨：它是把「先验知识」直接烧进压缩器里。压第一个字节之前，它就已经「见过」几万个常见网页片段了。这和第 12 章那台模型做的事，本质上是同一件——只是一个是查表，一个是概率。

∑ LZ77 的一个惊人性质：它不需要知道概率

霍夫曼和算术编码都需要一张概率表。LZ77 什么都不需要知道——它只是往回看。

而 Ziv 和 Lempel 证明了一件很强的事：对任何平稳遍历信源，LZ77 的压缩率在数据足够长时会收敛到该信源的熵率。

也就是说，它在不知道分布的情况下，渐近达到了知道分布才能达到的最优。这类算法叫通用压缩（universal compression），是信息论里一个很深的方向。

代价是「足够长」这三个字很贵。demo 里 3545 字符的日志，LZ77 离真正的地板还差得远；要逼近渐近性能，可能需要几百 MB。渐近最优和实用最优之间的距离，是压缩工程的大部分内容。

◇ 结账

C：算术编码，500 字节，正好等于地板

而 gzip 用了 667 字节，LZ77 单独用了 985 字节。

如果你选了 B，那是很自然的——「gzip 是最强的通用压缩器」这个印象在多数场合都对，但它对的原因是「多数场合的数据符合它的赌注」，不是「它在任何数据上都最优」。

选 D 也有一半道理：随机 DNA 确实「压不动」——如果你的基准是它已经存成了 2 比特一个碱基的话。但如果它存成了一个字节一个碱基（FASTA 格式就是这样），那就有 4 倍的水可以挤。「压不动」这个判断，取决于你从什么格式出发。

这一章的一句话

压缩有两条路：数概率，和找重复。它们的盲区正好互补，所以你每天用的 gzip 是两台机器串起来的——而选对赌注，比选对算法重要得多。

卷 II 结束。你现在有三台真机器（霍夫曼、算术编码、LZ77），和一条谁也过不去的地板。

但注意一件事：到目前为止，所有的「概率」都是我从文本里数出来的字符频率。那是最笨的一种模型——它假设每个字符和前面的字符完全无关。

卷 III 要做的就是换掉这个假设。而换掉之后会发生一件很大的事：「压缩」这门手艺会变成「预测」这门手艺，而「预测」这门手艺现在有个更流行的名字，叫机器学习。下一章从一个具体的问题开始：如果你的概率表本来就估错了，你要为此多付多少比特？那个数字有名字，而且你大概每天都在优化它。