不久前，我写过一篇关于不用神经网络的语言建模的文章，用无界 n-gram 模型生成莎士比亚文本：没有权重、没有训练，只有计数。碰巧，我读到了论文 Language Modeling is Compression，其中提到了压缩-预测等价性：
每一个预测模型本质上都是一个压缩器，而所有压缩算法都是预测模型。
这引出了一个自然的问题：gzip 能做语言建模吗？1
没有神经网络，没有学习到的参数，什么都没有，只有操作系统自带的压缩器。你先用一个语料库“预热”它，再给它一个普通的文本提示，它就会通过搜索压缩效果最好的字节序列来续写提示。下面是它在 tiny Shakespeare 语料上预热后输出的真实、未编辑的结果：
gzipt --corpus data/tinyshakespeare.txt --prompt $'MENENIUS:\n' --length 200
MENENIUS:
'Though all at once canq
MARCIUS:
Pray now, nocamest thou to a morsel .
LARTIUS:
Hence, and
I' the end admire, where G
again; and after it ag .
结果显示：某种意义上可以？文本并不算连贯，但它显然对文本有所“了解”，远超我对 gzip 的预期。2 那么，一个压缩器是如何做到这一点的？
压缩即预测#
想一想压缩器在做什么：它对“预期中”的数据花费很少的字节，对意外的数据花费很多字节。如果我给你一个由字母 A 重复一百万次组成的文件，你可以用一句话描述它。而一百万个随机字节没有任何结构可利用，几乎无法压缩。
这并非巧合，而是信息论的核心。编码一个符号所需的比特数是 $-\log_2 p$，其中 $p$ 是模型赋予它的概率。概率高意味着比特少。因此，任何压缩器内部都隐藏着一个概率模型，无论有没有人把它明确写出来。
gzip 使用 DEFLATE 算法，通过在 32 KiB 滑动窗口中查找与近期文本的匹配来压缩后续字节。如果一段续写内容与窗口中已有的内容重复，DEFLATE 会把它编码为廉价的回引用，而不是逐字节的字面量。所以：
gzip “预期”的续写——即与窗口中已有文本重复的内容——几乎可以压缩到几乎没有大小。
这就给了我们一个评分。如果我有某段上下文，想知道一个候选续写有多“好”，只需测量： $$\text{score}(\text{candidate}) = \texttt{len(gzip(context + candidate))}$$ 压缩后的长度越小，说明这个候选越“被预测到”。为了预热模型，我把语料库放进 gzip 的窗口中。任何看起来像语料库的续写都会压缩得很小，不像的则压缩得很大。
用束搜索生成#
评分是一回事，生成是另一回事。朴素的做法——每次挑选压缩效果最好的单个字节——效果很差，原因很微妙：gzip 只给出整数字节长度（没有小数）。增加一个字节往往完全不会改变压缩后长度，于是许多候选并列，信号被淹没在量化噪声中。
解决办法是在提交之前向前看一整段。gzipt 在字节序列上运行束搜索。每一步中，当前上下文为：
corpus window + recent tail of (prompt + generated bytes)
然后 gzipt 尝试可能的下一个字节。每个候选续写通过压缩 context + candidate 并检查压缩结果占多少字节来评分。
整个循环如下：
- 提示。 以用户提示作为要续写的初始文本。没有起始 token，提示字节只是 gzip 所见上下文的一部分。
- 上下文。 向 gzip 展示语料库窗口加上提示/生成文本的最近尾部。
- 搜索。 保留压缩效果最好的 beam_width 个部分续写。将每个续写用语料库中出现的每个字节进行扩展，按压缩后长度对所有候选评分，再裁剪回最好的 beam_width 个。重复此过程直到生成 horizon 个字节。
- 提交。 取压缩效果最好的完整片段（若温度为正，则在最终候选中采样），将其追加到输出，然后开始新一轮循环。
一个重要的细节是：评分上下文中只保留生成输出的最后 tail 个字节。 DEFLATE 对近距离匹配的编码比远距离匹配更便宜，因此如果 gzip 能看到全部历史，最省事的做法往往是陷入逐字循环，反复复制它刚刚输出的文本。
你可以在上面的动画中看到解码和评分过程，也就是文首展示的那段回放。整个项目只是一个纯标准库 Python 文件（仅用到 zlib）。代码已发布在 GitHub，欢迎上手把玩。