让我们从头开始构建压缩器

# 从零开始构建一个压缩器 来源：https://ochagavia.nl/blog/lets-build-a-compressor-from-scratch/ 压缩是我们在计算机世界中习以为常的奇妙事物之一。你挥动一下魔法棒——噗！——文件瞬间缩小到原来的一小部分。再挥一次——啵！——原始文件就分毫不差地恢复了。这究竟是如何做到的呢？让我们一探究竟！ ## 压缩基础 从高层次来看，压缩是通过重写数据，以更少的字节传达相同的信息。用一个例子最好说明这一点。假设你需要在文件中存储一个包含8个布尔值的数组。有两种可行的方案： 1. 将它们序列化为JSON格式：`[true, false, false, true, false, true, true, false]`。这种编码需要52个字节。 2. 将它们序列化为比特流，其中`true`用`1`表示，`false`用`0`表示：`10010110`。这种编码仅需一个字节。 这两种格式表达的信息等价，但第二种在空间上效率高得多（效率提升52倍）。既然格式等价，我们可以编写一个专门的*压缩器*程序，将JSON格式转换为二进制格式。同样，我们也可以编写一个*解压缩器*来进行反向转换。 ## 通用压缩算法 上述压缩机制是针对布尔数组的。这听起来不太实用，对吧？因此我们还有支持任意数据的压缩算法。例如，`gzip`工具可以压缩文本文件、软件二进制文件以及几乎所有你能想到的东西。 考虑以下例子： - 这本书 (http://www.gutenberg.org/cache/epub/48320/pg48320.txt) 使用`gzip`压缩后，大小从622 KB缩减到234 KB。效果不错！ - 我目前在做的一个Rust程序的编译后二进制文件从90 MB缩减到30 MB。同样效果不错！ - 我手头的一个MP3录音从54 MB缩减到……54 MB。这看起来很糟糕，但实际上在意料之中，因为MP3文件本身已经是压缩过的。 通用压缩器是如何工作的？`gzip`使用的算法称为DEFLATE (https://en.wikipedia.org/wiki/Deflate)。大致来说，它应用两种技术来缩减字节序列的大小： 1. 识别重复的字节序列，并用更高效的表示替换它们。如果你知道某个字节序列之前出现过，你可以用一个标记替换它，表示“嘿，这里你应该填充从位置2397取出的15个字节”。如果标记比重复序列短，你就成功削减了一些字节！ 2. 统计每个单独字节的出现次数，并基于这些计数改变每个字节的编码方式。出现频率高的字节编码为较短的比特序列（比一个字节短），出现频率低的字节编码为较长的序列，最终结果通常是更小的文件。顺便说一句，这项技术的正式名称是霍夫曼编码 (https://en.wikipedia.org/wiki/Huffman_coding)，我们稍后将会实际操作它。 ## 霍夫曼编码演示场 在上面提到的DEFLATE的两个组成部分中，我认为霍夫曼编码是那个“神奇”且有趣的部分。它也是我们将要在自定义压缩器中使用的技术。 为了更好地理解霍夫曼编码在实践中的含义，我在下方包含了一个嵌入式演示场。你可以输入文本，看看算法如何响应：每个字节的频率、分配给它的比特序列以及该消息的预期压缩大小。尽管试试看吧！ 正在加载演示场（需要JavaScript）... ## 我们自己的（解）压缩器 到了这一步，压缩步骤看起来应该相当直观： - 统计源数据中每个字节的频率。 - 根据这些频率，推导出从每个字节到一个比特序列的映射（使用霍夫曼编码）。 - 使用该映射处理源数据，并写入一个压缩流，其中每个输入字节被替换为对应的比特序列。 - 在输出流的开头编码该映射，以便解压缩器知道如何解释数据。 解压缩器则是上述过程的镜像版本： - 加载压缩器使用的映射。 - 使用该映射处理压缩数据，识别比特序列并将每个序列替换为其对应的字节。 ## 效果如何？ 我刚才描述的压缩器实际上已经存在。我几周前编写了它，并称之为Adolfo's Basic Compressor（简称ABC）。你可以在这里找到源代码 (https://github.com/aochagavia/abc)。 压缩效果不如`gzip`，但这是意料之中的，因为我们的压缩方法简单得多。我之前提到的那本书从622 KB压缩到366 KB（出乎意料地好），而Rust二进制文件从90 MB压缩到73 MB（效果一般）。但所有这些仅用了580行无依赖的Rust代码就实现了。对我来说，这仍然感觉像魔法一样。 ## 尾声：向David MacKay致敬 每隔一段时间，互联网上一些友好的朋友就会提醒我信息论的存在。每隔一段时间，我都会兴奋起来，尝试钻研它，但在意识到这不是一个下午就能学会的东西后就放弃了。 这篇博文证明，这一次，我打破了那个循环。我的向导是伟大的David MacKay，通过这个精彩的系列讲座 (https://www.youtube.com/playlist?app=desktop&list=PLruBu5BI5n4aFpG32iMbdWoRVAA-Vcso6)。他对这门学科的热情富有感染力，教学时展现出的愉悦让讲座成为一种享受。愿我们这个世界有更多像他一样的人。安息。