本文翻译自 An ode to bzip，原载于 Hacker News。

故事是这样的。ComputerCraft 是一个给 Minecraft 添加编程功能的模组。你需要编写 Lua 代码，由一个定制化的解释器执行，可以访问游戏世界的各种 API——然后你就在写代码而不是玩游戏了。游戏里的计算机磁盘空间有限，而我的 /nix 文件夹正在失控地增长，所以我需要压缩代码。

最偷懒的选择是用 LibDeflate，但它的解码器比压缩带来的收益还要大，而且也超出了我个人能接受的复制代码的边界。所以问题变成了：什么是最短、最简单、压缩比最高的压缩算法？

我起初以为这是一个充满权衡的复杂问题，但结果出人意料地清晰。我的答案是 bzip——尽管这个算法已经被多次批评，并且随着 xz 和 zstd 的流行而逐渐被遗忘。

压缩比测试

我正在压缩一个 327 KB 的文件，包含 Lua 代码和少量英文注释和文档。这很重要：bzip 擅长的是类文本数据而不是二进制数据。不过，我的结果在其他代码库上应该也是可复现的，因为在这个类别内百分比似乎是相对恒定的。

来看看多种知名编码器在这个数据上的表现：

bzip 家族以明显优势胜出！它甚至击败了 lzip——而 lzip 的文档声称”lzip -9 压缩大多数文件比 bzip2 更好”（看来代码不算”大多数文件”）。

bzip 为什么这么强？

它是如何做到的？原来，bzip 和其他算法有着根本的不同。

你看，所有其他流行的压缩算法在核心上其实是同一种东西。它们都基于 LZ77，这是一种压缩方案，本质上是把重复的文本替换为指向前一次出现的短链接。

主要区别在于如何将字面量字符串和回引用编码为比特流，这确实非常不简单。由于链接的位置、长度和频率在不同位置可能差异巨大，一个好的算法需要预测并简洁地编码这些参数。

但 bzip 不使用 LZ77。bzip 使用的是 BWT（Burrows-Wheeler Transform），它会重新排列文本中的字符，按上下文分组——所以你不需要根据之前类似的出现来预测 token，只需要看最后几个符号就可以了。而且，令人惊讶的是，在 BWT 顺序下，你甚至不需要存储每个符号来自哪里！

举个例子，如果单词 hello 在文本中多次出现，用 LZ77 你需要在每次出现时找到并插入新的引用。但用 BWT，所有 hell 的后续字符都被分组在一起，所以你可能只是有一连串的 o，其他字符同理——简单的游程编码（RLE）就能处理。

BWT 的局限性

BWT 也有一些缺点。例如，如果你连接两篇不同英式英语的文本（比如一个用 color，一个用 colour），BWT 会以不可预测的顺序混合 colo 的后续字符，你需要编码一个奇怪的 r 和 u 序列，而 LZ77 会优先考虑最近的历史。你可以通过按格式分离输入来解决这个问题，但对于代码这样一致的数据，它本身就工作得很好。

bzip2 和 bzip3 都基于 BWT，主要区别在于如何压缩 BWT 输出。bzip2 使用 RLE 的变体，而 bzip3 尝试更聪明的方法。出于性能原因，我会专注于 bzip2，但大多数结论也适用于 bzip3。

无需调参的优势

关于 BWT 还有一个有趣的事情。你可能注意到我调用 bzip3 时没有传递任何像 -9 这样的参数。那是因为 bzip3 根本不接受这些参数。事实上，即使给 bzip2 传 -9 也没什么大用。

基于 LZ77 的方法支持不同的压缩级别，因为搜索之前的出现是耗时的，有时使用字面量字符串比难以编码的引用更好，所以需要一些暴力搜索。而 BWT 是完全确定性的，没有启发式算法。

此外，在如何高效编码回引用的长度和偏移量方面，也没有自由度——因为根本没有回引用。有游程长度，但也就那样了——它只是一个数字，而且比典型的偏移量更小。

这意味着：如果你知道 bzip2 流水线是什么样的，你可以快速实现类似的压缩比，而不需要调优和担心边缘情况。我未经优化的临时 bzip2 类编码器将相同输入压缩到约 67 KB——比 lzip 更好，而且还有明确的改进空间。

解码器大小对比

这涵盖了压缩格式，但解码器的大小呢？当目标是 Lua 时，测量 ELF 文件是无用的，而像 LibDeflate 这样的 Lua 库并没有为自解压档案优化代码大小。所以，我会对除 bzip2 以外的所有算法进行粗略估计。

自解压可执行文件不需要解码每个档案——只需要解码一个。我们可以跳过完整性检查、头部，将元数据内联到代码中，并调整格式以便于解码。因此，我只看核心解压循环。

gzip、zstd、xz、brotli 和 lzip 都从 LZ77 开始。评估”复制” token 是一个简单的循环，不会占用太多代码。它们的区别在于这些 token 如何编码为比特：

• gzip：做一些轻量预处理，然后应用霍夫曼编码。霍夫曼码可以在约 250 字节内解析，比特树可能需要约 700 字节，胶水代码约 500 字节。总计约 1.5 KB。

• xz：逐位编码 token 而不是作为原子处理，这允许编码器动态调整概率，在不编码任何表的情况下获得好的压缩比，代价是性能。逐位解析会比通常占用更多空间，但避免表是巨大的胜利，所以估计约 1 KB。

• lzip：与 xz 非常相似，只是稍微改变了 token 编码，所以也估计约 1 KB。

• zstd：使预处理步骤复杂化，使用有限状态熵（FSE）代替霍夫曼编码，这实际上允许 token 以分数比特长度编码。FSE 简单但需要大表，存储和解析约 2000 字节。加上胶水代码，约 3 KB。

• brotli：保留霍夫曼编码，但根据上下文在多个静态霍夫曼表之间动态切换。我在我的输入上得到 7 个表。这是很多数据——我们需要编码和解析它们。估计约 500 字节用于解析器，每表约 100 字节。加上其余代码，约 2.2 KB。

对于 bzip 解码器，BWT 可以在约 250 字节内处理。至于独特部分：

• bzip2：用 MTF + RLE + 霍夫曼压缩 BWT 输出。使用默认的 6 个霍夫曼表，所有霍夫曼相关代码和数据约 1.5 KB，MTF、RLE 和胶水代码约 400 字节。

• bzip3：使用类似 XZ 的逐位编码加上下文混合。前者约 1 KB，后者约 500 字节。

重点是：通过放弃与标准文件格式的兼容性，解码器可以变得非常小。我可能在这些数字上有误，但最有可能不会显著改变局面。

bzip 风格的方法处于中游，但这有些误导。虽然 bzip2 通常使用 6 个霍夫曼表，但我只用一个表就获得了不错的压缩结果。使用单一表，我的 bzip 风格解码器只需 1.5 KB——比除 xz 和 lzip 以外的所有算法都小，而且更快、更紧凑。

关于性能的迷思

众所周知 bzip 很慢，但这里有细微差别。

当压缩被用来绕过硬性限制时，bzip 和 gzip 之间的区别不是启动慢还是启动快，而是能启动还是根本不能启动。如果解压 initrd 需要 0.5 秒而不是 0.3 秒，与无法启动相比不是什么大问题。

从这个角度看，说 bzip 比 gzip 慢是在回避问题。gzip 不能像 bzip 那样容易产生最优输出，所以它用可配置的时间-比率权衡来启发式地搜索之前的出现。gzip 更快不是因为设计不同，而是因为 gzip 决定速度比输出质量更重要，即使在 -9 级别。如果你想要好的压缩比，必须用 zopfli，它尝试更优地编码 gzip，比 bzip 慢一个数量级，却产生更差的输出。

在解码方面，解码 bzip 慢是因为逆 BWT 需要随机访问。在 Lua 这样的高级语言中，这没那么大的问题，因为所有操作都很慢。在这种情况下，大多数典型的压缩技术更加昂贵。你可以比 bzip2 更快地解码 gzip，但 zstd 和 brotli 在速度上可能更接近 bzip2。

为什么不自创算法？

所以这就是我的答案：不是自定义压缩算法，只是带点花样的 bzip。

如果你了解我，不发明新东西可能听起来令人惊讶。嗯，我试过，成功程度不一。

这里有个练习。文本压缩的核心思想是文本是重复的，所以我们可以编码（希望更短的）对早期重复的引用，而不是每次都重复单词 repeat。例如，字符串：

Rust is an iron oxide, a usually reddish-brown oxide formed by the reaction of iron and oxygen in the catalytic presence of water or air moisture.

…可以编码为：

• 写入 Rust is an iron oxide, a usually reddish-brow
• 从 31 字节前复制 7 字节（n oxide）
• 写入 formed by the
• 从 24 字节前复制 3 字节（re）
• 写入 acti
• 从 60 字节前复制 4 字节（on o）
• …以此类推

既然我们在压缩文本，你可能期望重复的部分是单词。但在这个例子中，往往是音节或随机字母。基于代码结构压缩代码的尝试在这方面很吃力，因为它们只能压缩单个 token。

虽然我们可以预处理代码然后应用 bzip 来获取其余好处，但这会使解码器复杂化而不能显著改善压缩比。例如，Luz 用 gzip 这样做，对压缩比没有任何影响，尽管在解码上浪费了许多 KB。

这似乎是数据压缩中的常见经验。现实世界的数据以人类不容易猜测但计算机可以即时识别的方式结构化。改进不是来自复杂化算法，而是来自重构数据和应用更强大的通用方法。

如果这听起来可疑地像机器学习，你说对了。2009 年的文章《Large Text Compression Benchmark 的理由》更详细地描述了这种联系。今天看起来天真，但它是对的：Large Text Compression Benchmark 的顶级竞争者是 nncp，你肯定能猜到”NN”代表什么（神经网络）。

总结

bzip 作为通用压缩格式可能不是最优的，但它在文本和代码方面非常出色。你甚至可以说 bzip 中的 b 代表”best”（最好）。

关键要点：

1. BWT vs LZ77：bzip 使用 Burrows-Wheeler 变换而非 LZ77，通过按上下文分组字符实现高效压缩，特别适合文本和代码。

2. 压缩比优势：在代码压缩测试中，bzip2 和 bzip3 明显优于 gzip、zstd、xz、brotli 和 lzip。

3. 无需调参：BWT 是完全确定性的，没有启发式算法，不像 LZ77 系算法需要调整压缩级别。

4. 解码器紧凑：通过简化格式，bzip 风格的解码器可以做到非常小（约 1.5 KB），比大多数现代算法更紧凑。

5. 性能权衡：虽然 bzip 解码较慢，但当压缩是硬性限制时，能压缩比速度更重要——”能启动 vs 不能启动”的区别。

bzip 编码器比基于 LZ77 的编码器更少受启发式和道听途说的设计决策困扰，给影响压缩比的微妙错误留下了更少空间。在高级语言中实现时，bzip 解码相当快速。

注：本文原作者从 ComputerCraft/Minecraft 模组的实际需求出发，通过严谨的测试和分析，重新发现了 bzip 在特定场景下的价值。对于我们日常的代码压缩、文本存档等场景，bzip 仍然是一个值得考虑的选择。