Let’s build a compressor from scratch

让我们从零开始构建一个压缩器

02 Sep, 2026 2026年9月2日

Compression is one of those wonderful things we have grown accustomed to in the computer world. You wave a magic wand and —poof!— a file suddenly shrinks to a fraction of its size! You wave the wand again and —pop!— the original file is restored down to the last bit. How can this possibly work? Let’s find out! 压缩是我们在计算机世界中习以为常的神奇事物之一。你挥动魔杖，“砰”的一声，文件瞬间缩小到原来的一小部分！你再次挥动魔杖，“啪”的一声，原始文件便恢复得丝毫不差。这究竟是如何做到的呢？让我们一探究竟！

Compression 101

压缩基础知识

At a high level, compression is about rewriting data so that it conveys the same information in fewer bytes. This is best illustrated with an example. Imagine you have an array of 8 booleans you need to store in a file. Two possible approaches are: 从宏观层面来看，压缩就是重写数据，使其以更少的字节传达相同的信息。用一个例子可以最好地说明这一点。想象一下，你有一个包含 8 个布尔值的数组需要存储在文件中。有两种可能的方法：

• Serialize them as JSON: [true, false, false, true, false, true, true, false]. This encoding requires 52 bytes.
• Serialize them as a stream of bits, where true is represented by 1 and false by 0: 10010110. This encoding requires a single byte.
• 将其序列化为 JSON：[true, false, false, true, false, true, true, false]。这种编码需要 52 个字节。
• 将其序列化为位流（bit stream），其中 true 表示为 1，false 表示为 0：10010110。这种编码仅需 1 个字节。

The two formats are equivalent, yet the second one is significantly more efficient in terms of space (by a factor of 52). Since the formats are equivalent, we can write a specialized compressor program that transforms the JSON format into the binary one. Similarly, we can write a decompressor that goes in the opposite direction. 这两种格式是等价的，但第二种格式在空间效率上要高得多（高出 52 倍）。由于格式等价，我们可以编写一个专门的压缩程序，将 JSON 格式转换为二进制格式。同样，我们也可以编写一个反向操作的解压程序。

Generic compression algorithms

通用压缩算法

The compression mechanism described above is specific to boolean arrays. That doesn’t sound too useful, does it? That’s why we also have compression algorithms that support arbitrary data. For instance, the gzip tool can compress text files, software binaries, and pretty much anything else you throw at it. Consider the following examples: 上述压缩机制仅适用于布尔数组。这听起来不太实用，对吧？这就是为什么我们还有支持任意数据的压缩算法。例如，gzip 工具可以压缩文本文件、软件二进制文件以及你扔给它的几乎任何其他内容。考虑以下示例：

• This book goes down from 622 KB to 234 KB when compressed with gzip. Not bad!
• The compiled binary of a Rust program I’m currently working on goes from 90 MB to 30 MB. Not bad either!
• An MP3 recording I have lying around goes from 54 MB to… 54 MB. This looks pretty bad, but it is actually expected because MP3 files are already compressed.
• 这本书用 gzip 压缩后从 622 KB 缩小到 234 KB。还不错！
• 我目前正在编写的一个 Rust 程序的编译二进制文件从 90 MB 缩小到 30 MB。也不错！
• 我手头的一段 MP3 录音从 54 MB 变成了……54 MB。这看起来很糟糕，但实际上是预料之中的，因为 MP3 文件本身已经是压缩过的了。

How does a generic compressor work? The algorithm used by gzip is called DEFLATE. Roughly speaking, it applies two techniques to shrink a sequence of bytes: 通用压缩器是如何工作的？gzip 使用的算法称为 DEFLATE。粗略地说，它应用了两种技术来缩小字节序列：

1. Identify repeated byte sequences and replace them with a more efficient representation. If you know a byte sequence has already appeared before, you can replace it by a marker that says “hey, here you should fill in 15 bytes taken from position 2397”. If the marker is shorter than the repeated sequence, you have successfully shaved off some bytes!
2. Count the occurrences of each individual byte and, based on those counts, change the way each byte is encoded. Bytes that appear often are encoded as short bit sequences (shorter than a byte), bytes that appear rarely are encoded as longer sequences, and the end result is usually a smaller file. The fancy name for this technique is Huffman coding, by the way, and we will get to play with it below.
3. 识别重复的字节序列并用更高效的表示方式替换它们。如果你知道某个字节序列之前已经出现过，你可以用一个标记来替换它，该标记的意思是“嘿，这里你应该填入从位置 2397 开始的 15 个字节”。如果标记比重复的序列短，你就成功地节省了一些字节！
4. 统计每个字节出现的频率，并根据这些计数改变每个字节的编码方式。出现频率高的字节被编码为短位序列（短于一个字节），出现频率低的字节被编码为较长的序列，最终结果通常是一个更小的文件。顺便提一下，这种技术的高级名称是霍夫曼编码（Huffman coding），我们将在下面尝试使用它。

Huffman playground

霍夫曼编码演练场

Of the two components of DEFLATE mentioned above, I’d say Huffman coding is the “magical” and interesting one. It is also the technique we’ll use in our custom compressor. To get a better grasp of what Huffman encoding means in practice, I have included an embedded playground below. You can enter text and see how the algorithm reacts: the frequency of each byte, the bit sequence assigned to it, and the expected compressed size for the message. Go ahead and try it out! 在上述提到的 DEFLATE 的两个组成部分中，我认为霍夫曼编码是“神奇”且有趣的部分。这也是我们将要在自定义压缩器中使用的技术。为了更好地理解霍夫曼编码在实践中的意义，我在下面嵌入了一个演练场。你可以输入文本，看看算法是如何反应的：每个字节的频率、分配给它的位序列，以及消息的预期压缩大小。去试试吧！

Our very own (de)compressor

我们自己的（解）压缩器

Having come to this point, the compression steps should seem reasonably straightforward: 走到这一步，压缩步骤看起来应该相当直观了：

1. Count the frequency of each byte in the source data.
2. From those frequencies, derive a mapping from each byte to a bit sequence (using Huffman coding).
3. Using that mapping, process the source data and write a compressed stream where each input byte is replaced by its corresponding bit sequence.
4. Encode the mapping at the beginning of the output stream, so the decompressor knows how to interpret the data.
5. 统计源数据中每个字节的频率。
6. 根据这些频率，推导出从每个字节到位序列的映射（使用霍夫曼编码）。
7. 使用该映射处理源数据，并写入一个压缩流，其中每个输入字节都被其对应的位序列替换。
8. 在输出流的开头编码该映射，以便解压器知道如何解释数据。

The decompressor would be a mirrored version of the above: 解压器将是上述过程的镜像版本：

1. Load the mapping used by the compressor.
2. Use that mapping to process the compressed data, recognizing bit sequences and replacing each one with its corresponding byte.
3. 加载压缩器使用的映射。
4. 使用该映射处理压缩数据，识别位序列并将每个序列替换为其对应的字节。

Is it any good?

它好用吗？

The compressor I just described actually exists. I wrote it a few weeks ago and I’m calling it Adolfo’s Basic Compressor (or ABC for friends). You can find the source code here. Compression is less effective than gzip, but that is to be expected because our compression method is way simpler. The book I mentioned before shrinks from 622 KB to 366 KB (surprisingly good) and the Rust binary goes from 90 MB to 73 MB (meh). But it all works with just 580 lines of dependency-free Rust code. To me, it still feels like magic. 我刚才描述的压缩器确实存在。我几周前写了它，并将其命名为 Adolfo 的基础压缩器（朋友们简称它为 ABC）。你可以在这里找到源代码。它的压缩效果不如 gzip，但这在预料之中，因为我们的压缩方法简单得多。我之前提到的那本书从 622 KB 缩小到 366 KB（出奇地好），而 Rust 二进制文件从 90 MB 缩小到 73 MB（一般般）。但这一切仅用了 580 行无依赖的 Rust 代码就实现了。对我来说，这仍然感觉像魔法一样。

Epilogue: a tribute to David MacKay

结语：向 David MacKay 致敬

Every once in a while some friendly person on the internet will remind me of the existence of information theory. Every once in a while I’ll get hyped up, attempt to sink my teeth into it, and give up after realizing that it’s not something you can learn in an afternoon. This blog post is a testament to the fact that, this time, I managed to break that cycle. My guide was the great David MacKay, through this excellent lecture series. His enthusiasm for the subject was contagious, and the delight he displayed while teaching made the lectures a joy to watch. May we have more people like him in this world. RIP. 每隔一段时间，互联网上总会有友善的人提醒我信息论的存在。每隔一段时间，我就会兴奋起来，试图钻研它，但在意识到这不是一个下午就能学会的东西后又放弃。这篇博文证明了这一次我成功打破了这个循环。我的导师是伟大的 David MacKay，通过他那系列精彩的讲座。他对这门学科的热情具有感染力，他在教学中展现出的愉悦使这些讲座看起来非常享受。愿这个世界上有更多像他这样的人。安息。