Hellishly Slow Level 13 Deflate Compression：极致压缩的代价与权衡

背景

尽管现代压缩算法层出不穷，DEFLATE 依然是当今互联网和软件生态中最广泛使用的压缩标准。其核心优势在于解码器的无处不在：HTTP 内容编码、ZIP 归档文件、PNG 图像格式内部、软件分发、备份工具以及许多嵌入式格式，依然沿用着相同的 LZ77 结合 Huffman 编码的设计。

DEFLATE 的解码契约（Decoder Contract）是固定且标准化的，这意味着任何符合标准的编码器生成的数据都能被任何标准的解码器正确读取。然而，编码器本身在匹配查找、块边界划分以及 Huffman 表生成上仍有巨大的优化空间。更好的编码选择可以在不牺牲兼容性的前提下，进一步减小数据体积。

本文讨论的 libdeflate 是一个高性能的 DEFLATE 实现库。其 Level 12 已经是目前实践中最强的编码器之一。而 Level 13 则是一个被故意设计为“不切实际”的实验性级别，旨在探索压缩率与计算成本之间的极限边界。

核心内容

Level 13 的核心设计理念是：在保持输出为标准 DEFLATE 格式的前提下，通过大幅增加编码器在解析、Huffman 编码和块分割选择上的搜索成本，来换取微小的压缩率提升。

1. 机制详解

Level 13 保留了 libdeflate 近乎最优的解析器基础，但使其决策过程变得极其昂贵。具体机制包括：

• 全窗口搜索与多轮优化：编码器会在完整的 32 KiB DEFLATE 窗口内进行搜索，并允许执行多达 15 轮优化迭代。
• 静态 Huffman 优化：对于输入字节数不超过 50,000 的块，应用静态 Huffman 优化。
• 无格式扩展：整个过程不涉及任何 DEFLATE 格式的非标准扩展，确保兼容性。

2. 文本数据的自适应策略

针对文本类数据，Level 13 引入了延迟块大小承诺（delayed block size commitment）的策略：

• 它从当前块的起始位置采样最多 64 KiB 的数据。
• 如果采样数据中不包含 NULL 字节，且包含的不同字节值不超过 97 种，则认为数据分布稳定。
• 在此假设下，软块大小（soft block size）从默认的 300,000 字节提升至 1,000,000 字节。
• 逻辑依据：稳定的字节分布意味着一个单一的 Huffman 表可以覆盖更多的数据，从而减少表头开销并提高编码效率。

3. 解析器与成本估算

解析器的最小成本搜索范围被大幅拓宽：

• 匹配长度优化：为每个匹配长度选择最便宜的偏移量。
• Huffman 成本估算：基于字面量（literal）和匹配长度的统计信息，估算初始 Huffman 成本。
• 偏移槽频率估算：基于缓存的匹配结果估算偏移槽频率。
• 多模式对比：将测量得到的动态 Huffman 成本与静态 Huffman 编码以及仅字面量编码进行对比，选择最优解。

4. 块分割（Block Splitting）的延迟与评分

块分割策略也被推迟执行，以寻求全局最优：

• 压缩器会存储多达 9 个分割候选项及其解析状态。
• 随后对完整块进行评分，并在候选区间内计算有界最短路径。
• 获胜条件：单次分割若能在成本上胜出即可采用；多重分割路径的成本必须比完整块至少低 512 位才能被选中。
• 最终选定的解析方案会被缓存，用于最后的刷新输出。

5. 性能边界控制

尽管 Level 13 极其缓慢，但其复杂度是受控的。搜索迭代次数、分割候选项数量和块大小均有上限。因此，Level 13 不会像 turtledeflate 或更广泛的文件优化工具 ECT 那样陷入无限制的优化循环。

6. 回归测试策略

开发过程中采用了严格的“零压缩回归”政策，基于 Silesia 语料库进行测试：

• 许多优化尝试被排除，只有那些严格减少至少一个压缩文件体积，且绝不增加任何其他文件体积的更改，才会被纳入最终的 Level 13 配置中。
• Silesia 语料库虽然体积小，适合重复开发测试，但其内容混合了文本、二进制、数据库、图像和结构化数据，足以惩罚针对单一文件的过度调优。

关键要点

• 极致的性价比失衡：在 Silesia 语料库上，Level 13 相比 Level 12 仅节省了 86,990 字节（压缩率提升 0.134%），但运行速度慢了 56.4 倍。
• 适用场景极其有限：这种成本收益比仅在“数据仅压缩一次，但被分发和读取多次”的场景下才具有合理性（例如软件分发、长期归档）。
• 兼容性保持：Level 13 生成的输出完全符合标准 DEFLATE 规范，无需修改解码器即可使用。
• 算法复杂性增加：通过增加优化轮次（15轮）、扩大搜索窗口（32 KiB）、延迟块分割决策以及更复杂的成本估算模型，换取微小的空间节省。
• 数据敏感性：不同文件类型的优化效果差异巨大。例如，nci 文件相对压缩率提升达 0.296%，而 sao 文件仅变化 0.004%。
• 开发纪律：采用“零回归”策略，确保优化不会导致任何现有文件的压缩体积增加，体现了对压缩算法稳定性的极致追求。

意义与影响

Level 13 的存在并非为了日常生产环境的通用压缩，而是作为一种技术探索，揭示了 DEFLATE 算法在理论上的压缩极限。

1. 验证了 DEFLATE 的优化潜力：即使在一个已经非常成熟的算法上，通过穷举搜索和复杂的启发式算法，仍然可以挤出微小的压缩率提升。这证明了 LZ77 + Huffman 架构在理论上的可优化空间。
2. 明确了“边际效应”的边界：0.134% 的压缩率提升伴随着 56.4 倍的性能损耗，清晰地展示了在工程实践中，当优化带来的收益低于某个阈值时，计算资源的投入将变得不再经济。这为其他压缩算法的性能权衡提供了参考基准。
3. 推动了编码器设计的精细化：Level 13 中采用的延迟块分割、多轮成本估算和自适应采样策略，虽然在此级别下过于沉重，但其思想可能被提炼并应用于更平衡的压缩级别中，或者用于指导未来更智能的自适应编码器。
4. 对存储与带宽成本的重新思考：该实验提醒我们，在云存储和带宽成本日益高昂的今天，对于长期归档或高频访问的数据，极致的压缩率可能值得付出巨大的计算成本，但这需要精确的业务场景评估，而非盲目追求最高压缩级别。

总之，Hellishly Slow Level 13 是一个关于“极致”的实验，它展示了在固定格式约束下，通过计算换空间的极限在哪里，同时也警示了过度优化的工程风险。