Can gzip be a language model?

gzip 能成为语言模型吗？

A while back I wrote about language modeling without neural networks, where I generated Shakespeare with an unbounded n-gram model: no weights, no training, just counting. Fortuitously, I came across the paper Language Modeling is Compression, which mentioned the compression–prediction equivalence: every prediction model is inherently a compressor, and all compression algorithms are prediction models. 前段时间我写过关于无需神经网络的语言建模，当时我用一个无界 n-gram 模型生成了莎士比亚风格的文本：没有权重，没有训练，仅仅是计数。机缘巧合下，我读到了《语言建模即压缩》（Language Modeling is Compression）这篇论文，其中提到了压缩与预测的等价性：每一个预测模型本质上都是一个压缩器，而所有的压缩算法也都是预测模型。

This led to the natural question: can gzip do language modeling? No neural network, no learned parameters, nothing. Just the compressor that ships with your operating system. You prime it with a corpus, give it a normal text prompt, and it continues that prompt by searching for the byte sequences that compress best. Here’s some real, unedited output after priming it on tiny Shakespeare: 这引出了一个自然而然的问题：gzip 能做语言建模吗？没有神经网络，没有学习参数，什么都没有。仅仅使用你操作系统自带的压缩工具。你用一个语料库对其进行预填充（prime），给它一个普通的文本提示，它就会通过搜索压缩效果最好的字节序列来续写该提示。以下是在“微型莎士比亚”语料库上预填充后，得到的一些未经编辑的真实输出：

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 .

It turns out, kind of? It’s not exactly coherent text, but it clearly knows something about the text. Much more than I expected gzip to know. So how can a compressor generate this? 结果发现，算是吧？虽然生成的文本并不完全连贯，但它显然对文本有所了解。这比我预期的 gzip 的能力要强得多。那么，压缩器是如何生成这些内容的呢？

Compression is prediction

压缩即预测

Think about what a compressor does. It spends few bytes on data it “expects” and many bytes on data it doesn’t. If I hand you a file that’s the letter A repeated a million times, you can describe it in one sentence. A million random bytes, on the other hand, have no structure to exploit and barely compress at all. 思考一下压缩器的工作原理。对于它“预期”内的数据，它花费的字节很少；而对于它不预期的数据，它花费的字节则很多。如果我给你一个包含一百万个字母 A 的文件，你只需一句话就能描述它。反之，一百万个随机字节没有任何可利用的结构，几乎无法压缩。

This is not a coincidence; it’s the core of information theory. The number of bits needed to encode a symbol is $-\log_2 p$, where $p$ is the probability the model assigns to it. High probability means few bits. So any compressor has a probability model hiding inside it, whether or not anyone wrote one down. 这并非巧合，而是信息论的核心。编码一个符号所需的比特数是 $-\log_2 p$，其中 $p$ 是模型赋予该符号的概率。高概率意味着低比特数。因此，任何压缩器内部都隐藏着一个概率模型，无论是否有人显式地编写过它。

gzip uses DEFLATE, which compresses the next bytes by finding matches against the recent text in a 32 KiB sliding window. If a continuation echoes something already in the window, DEFLATE encodes it as a cheap back-reference instead of literal bytes. So: gzip 使用 DEFLATE 算法，它通过在 32 KiB 的滑动窗口中查找与近期文本的匹配项来压缩后续字节。如果续写内容与窗口中已有的内容相呼应，DEFLATE 会将其编码为一个低成本的“回溯引用”（back-reference），而不是字面字节。因此：

A continuation that gzip “expected”, because it echoes text already in its window, compresses to almost nothing.
一段 gzip “预期”内的续写，因为它呼应了窗口中已有的文本，所以压缩后几乎不占空间。

That gives us a score. If I have some context and I want to know how good a candidate continuation is, I just measure: 这给了我们一个评分标准。如果我有一些上下文，并且想知道候选续写的好坏，我只需测量：

$$\text{score}(\text{candidate}) = \texttt{len(gzip(context + candidate))}$$

The smaller the compressed length, the more “predicted” the candidate is. To prime the model, I include a corpus in gzip’s window. Any continuation that looks like the corpus compresses small, and any continuation that doesn’t compresses large. 压缩后的长度越小，说明该候选内容越被“预测”到。为了预填充模型，我将语料库包含在 gzip 的窗口中。任何看起来像语料库的续写都会被压缩得很小，而任何不像的则会被压缩得很大。

Generating by beam search

通过束搜索（Beam Search）生成

Scoring is one thing; generating is another. The naive approach of picking the single next byte that compresses best fails badly, and for a subtle reason: gzip only gives an integer byte length (no fractions). Adding one byte often doesn’t change the compressed length at all, so many candidates tie and the signal is buried in quantization noise. 评分是一回事，生成则是另一回事。那种选择压缩效果最好的下一个字节的简单方法效果很差，原因很微妙：gzip 只给出整数的字节长度（没有小数）。增加一个字节通常不会改变压缩后的长度，因此许多候选者会打平，信号被量化噪声淹没了。

The fix is to look ahead a whole span before committing. gzipt runs a beam search over byte sequences. At each step, the current context is: 解决方法是在提交之前先向前看一段完整的跨度。gzipt 对字节序列运行束搜索。在每一步中，当前的上下文是：

corpus window + recent tail of (prompt + generated bytes) 语料库窗口 + (提示词 + 已生成字节) 的近期尾部

Then gzipt tries possible next bytes. Each candidate continuation is scored by compressing context + candidate and checking how many bytes the compressed result takes. 然后 gzipt 尝试可能的下一个字节。每个候选续写通过压缩“上下文 + 候选内容”并检查压缩结果占用的字节数来评分。

The loop is: 循环如下：

Prompt. Start with the user’s prompt as the initial text to continue. There is no start token; the prompt bytes are just part of the context gzip sees.
Context. Show gzip the corpus window plus the recent tail of the prompt/generated text.
Search. Keep the beam_width most-compressible partial continuations. Extend each by every byte that occurs in the corpus, score all of them by compressed length, and prune back down to the best beam_width. Repeat for horizon bytes.
Commit. Take the most-compressible full span (or sample among the finalists if temperature is positive), append it, and start the loop over.
提示词：以用户的提示词作为初始文本开始续写。没有起始标记；提示词字节只是 gzip 所见上下文的一部分。
上下文：向 gzip 展示语料库窗口加上提示词/已生成文本的近期尾部。
搜索：保留 beam_width 个压缩效果最好的部分续写。用语料库中出现的每个字节扩展它们，根据压缩长度对所有候选者评分，并修剪回最佳的 beam_width 个。重复 horizon 次字节长度。
提交：选取压缩效果最好的完整跨度（如果温度参数为正，则在最终候选者中进行采样），将其附加，然后重新开始循环。

One detail that matters is that only the last tail bytes of generated output stay in the scoring context. DEFLATE codes nearby matches more cheaply than far ones, so if gzip could see its entire history, the cheapest thing to do is often to fall into verbatim loops, repeatedly copying text it just emitted. 一个重要的细节是，只有生成输出的最后尾部字节会保留在评分上下文中。DEFLATE 对近处的匹配编码成本比远处的更低，因此如果 gzip 能看到它的全部历史记录，它最“廉价”的做法往往是陷入逐字循环，反复复制它刚刚输出的文本。

You can see the decoding and scoring process in the animation above, which is the same replay shown at the top. The whole thing is one file of pure standard-library Python (just zlib). Code’s on GitHub if you want to play with it. 你可以在上面的动画中看到解码和评分过程，这与顶部展示的重放相同。整个程序是一个纯标准库 Python 文件（仅使用 zlib）。如果你想尝试一下，代码在 GitHub 上。