极其缓慢的 Level 13 Deflate 压缩

# 地狱般缓慢的 DEFLATE 压缩级别 13 来源：https://kirill.korins.ky/articles/hellishly-slow-level-13-deflate-compression/ ## 摘要 DEFLATE 级别 13 是 `libdeflate` 中一个刻意追求不实用性的压缩级别：输出仍然是标准 DEFLATE，但编码器花费更多时间来搜索解析、霍夫曼和块拆分选择。在 Silesia 语料库上，它比级别 12 节省了 86,990 字节（0.134%），但速度慢 56.4 倍；这种成本仅在数据压缩一次并多次分发时才能接受。 ## 为什么是 DEFLATE DEFLATE 仍然值得优化，因为它的解码器已经无处不在：HTTP 内容编码、ZIP 归档、PNG 内部结构、软件分发、备份工具和嵌入式格式仍在使用相同的 LZ77 加霍夫曼设计。解码器协议是固定的，但编码器仍然可以选择匹配、块边界和霍夫曼表；更好的选择可以在不改变兼容性的情况下减小体积。 基线是 `libdeflate`（https://github.com/ebiggers/libdeflate）级别 12，这是最强大的实用 DEFLATE 编码器之一。级别 13 的实现作为拉取请求（https://github.com/ebiggers/libdeflate/pull/452）贡献到上游。 ## 级别 13 的机制 级别 13 保留了 `libdeflate` 的近似最优解析器，但使其选择更加费时。它搜索完整的 32 KiB DEFLATE 窗口，允许 15 次优化遍历，并对最多 50,000 个输入字节的块应用静态霍夫曼优化。不涉及任何格式扩展。 对于类似文本的数据，级别 13 延迟块大小的确定。它从当前块起始位置采样最多 64 KiB；如果样本不包含 `NULL` 字节且至多有 97 个不同的字节值，则软块大小从 300,000 字节增加到 1,000,000 字节。假设很简单：稳定的字节分布让一个霍夫曼表能覆盖更多数据。 解析器扩展了最小成本搜索的范围。它可以为每个匹配长度选择最便宜的偏移量，根据字面量和匹配长度统计估计初始霍夫曼成本，根据缓存的匹配估计偏移槽频率，并将测量的动态霍夫曼成本与静态霍夫曼和纯字面量编码进行比较。 块拆分也被延迟。压缩器存储最多九个带有解析器状态的拆分候选，然后对整个块和候选区间上的有界最短路径进行评分。单个拆分可以通过成本获胜；多拆分路径必须比整个块至少节省 512 位。所选解析会被缓存以用于最终刷新。 慢速度是有边界的。搜索遍历、拆分候选和块大小都受到限制，因此级别 13 不会像 `turtledeflate`（https://github.com/rwillenbacher/turtledeflate）或更广泛的文件优化器如 `ECT`（https://github.com/fhanau/Efficient-Compression-Tool）那样进入无界优化循环。 ## 回归策略 开发过程中针对 Silesia 语料库（https://sun.aei.polsl.pl/~sdeor/index.php?page=silesia）采用了零压缩回归策略：尝试了许多方法，但只有那些严格减少至少一个压缩文件且不增加任何其他压缩文件的更改，才被纳入最终的级别 13 配置。 Silesia 语料库规模足够小，适合重复开发，但内容足够多样，能惩罚单一文件的调优：它包含文本、二进制文件、数据库、图像和结构化数据。 ## Silesia 结果 `libdeflate` 级别 12 与级别 13 在 Silesia 上的对比 | 文件 | 级别 12 大小 / 时间 | 级别 13 大小 / 时间 | 体积差异 | 时间差异 | | --- | --- | --- | --- | --- | | dickens | 3,688,552 / 1,289 ms | 3,684,671 / 83,512 ms | -3,881 (-0.105%) | +82,223 (+6378.8%) | | mozilla | 18,267,490 / 4,959 ms | 18,235,120 / 110,754 ms | -32,370 (-0.177%) | +105,795 (+2133.4%) | | mr | 3,448,571 / 1,627 ms | 3,443,723 / 16,260 ms | -4,848 (-0.141%) | +14,633 (+899.4%) | | nci | 2,766,224 / 7,935 ms | 2,758,044 / 673,648 ms | -8,180 (-0.296%) | +665,713 (+8389.6%) | | ooffice | 2,998,130 / 424 ms | 2,995,604 / 8,676 ms | -2,526 (-0.084%) | +8,252 (+1946.2%) | | osdb | 3,642,347 / 798 ms | 3,641,341 / 4,942 ms | -1,006 (-0.028%) | +4,144 (+519.3%) | | reymont | 1,702,796 / 1,005 ms | 1,699,494 / 81,839 ms | -3,302 (-0.194%) | +80,834 (+8043.2%) | | samba | 5,135,662 / 2,889 ms | 5,122,812 / 141,227 ms | -12,850 (-0.250%) | +138,338 (+4788.4%) | | sao | 5,255,575 / 333 ms | 5,255,358 / 1,687 ms | -217 (-0.004%) | +1,354 (+406.6%) | | webster | 11,565,754 / 6,452 ms | 11,555,293 / 475,196 ms | -10,461 (-0.090%) | +468,744 (+7265.1%) | | x-ray | 5,754,248 / 305 ms | 5,748,141 / 3,276 ms | -6,107 (-0.106%) | +2,971 (+974.1%) | | xml | 633,760 / 1,104 ms | 632,518 / 69,504 ms | -1,242 (-0.196%) | +68,400 (+6195.7%) | | **总计** | **64,859,109 / 29,120 ms** | **64,772,119 / 1,670,521 ms** | **-86,990 (-0.134%)** | **+1,641,401 (+5636.7%)** | 级别 13 在整个语料库上节省了 86,990 字节，减少了 0.134%，同时增加了 1,641,401 毫秒的运行时间。最显著的相对结果是 `nci`，减少了 0.296%；而 `sao` 仅变化了 0.004%。