通过穷举搜索实现无损GIF压缩

# 无损GIF重新压缩：通过穷举搜索 来源：https://blog.arusekk.pl/posts/lossless-gif-recompression/ ## 一点历史 GIF 是最早广泛使用的压缩图像格式。如今，它主要以支持图像文件中的动画而闻名，但让我感兴趣的并非这个用途。实际上，GIF 是 NCSA Mosaic 唯一支持的图像格式。如果你的网站希望真正兼容旧浏览器，那么所有关键图像都必须提供 GIF 后备方案。我说的“旧”可不是指旧版 Chromium，而是真正的 Mosaic、Netscape、IE、Netsurf、Dillo、Konqueror——就像你在 oldweb.today (https://oldweb.today/) 上能尝试的那些。（你可能对支持它们不感兴趣，但这算是个有趣的练习。） 我真的很想让 1-Click Linux (https://1clicklinux.org/) 网站在最古老的浏览器上也能看起来过得去，所以我决定使用 `<picture>` 并以降级到 GIF 作为后备。我认为，每个现代 Web 特性如果要在生产环境中使用，本身就应该具备相当广泛的兼容性，然后只提供一个后备方案，而那个后备方案必须拥有绝对的 1000% 兼容性。 ## 问题 问题是，GIF 的压缩效果并不出色。坦诚地说，到了 2026 年，你很可能应该只使用 SVG 和 WebP（照片用有损，小调色板绘图/Logo 用无损）。而不是 PNG、JPEG，更别提 AI、DWG 或其他任何专有格式（尤其看你的了，DICOM）。好吧，至少在网络上是这样（正如其名，WebP）。 一个部分解决方案是使用小尺寸图像。真正的旧设备屏幕尺寸非常小，比如诺基亚 240x320 手机。因此，作为后备的图标或 Logo 安全地设为 128x128 即可，因为 256x256 甚至可能塞不进屏幕。 我们能做得更好吗？是的。整个图像优化领域都有所涉及，首先便是剥离元数据。然后我们可以从调色板中移除未使用的颜色，再移除很少使用的颜色，以此类推。但上述步骤中没有一个真正涉及压缩本身！ ## ZopfliPNG 我听说过 zopflipng。PNG 使用 DEFLATE，也就是 ZIP 和 GZIP 中那种压缩格式。它是 LZ77 与哈夫曼编码的一种变体。在这种格式中（以及其他常见的压缩格式里），有很多不同的方式来表示完全相同的未压缩数据。DEFLATE 也是一种算法的名称，该算法生成一个压缩得还算不错的输入，并且可以通过调整参数花更多时间进行压缩，以期获得更好的压缩效果（针对相同数据，记得吗？）。但存在许多语法上有效的 DEFLATE 流，却从未被 DEFLATE 算法本身产生过，这有点好笑，因为你可以制作一个包含自身的 ZIP (https://research.swtch.com/zip)，但不管怎样，其中一些流甚至比最大的“压缩级别”还要好。 Zopfli 就是这样一个软件，它会对所有语法上有效的流进行穷举搜索，从而找到用最少比特数表示给定未压缩输入的实际方案。然后 ZopfliPNG 是其变体，专门针对 PNG 并进一步探索 PNG 的像素编码方式。这里需要小心，因为为任意格式找到真正的最佳压缩可能等同于解决停机问题。但我们今天讨论的压缩格式有一些有用的不变性，能保证搜索总会停止。 ## ZopfliGIF？ 没有 ZopfliGIF，但有一个几乎完全做到这一点的 flexiGIF。这显然是个很棒的工具，你应该用它来处理所有 GIF。但问题是，GIF 使用了一种非常不同的压缩方案——LZW。而且我在其 README 中发现了一个令人困扰的说法：它可能产生比原始算法更大的文件。这非常可疑。于是我开始了探索。“它是由一个人创造的——所以我也能理解它。”——我这么想。 ## LZW 然后我发现理解起来有点困难，因为像那个时代的许多论文一样，原始描述坚持围绕算法构建数据格式。但我们，几十年后的今天，已经知道这是一个错误：对于我们这些注重互操作性的人来说，数据格式当然比算法更有趣。改变格式需要修改解码器软件。保留格式，改变编码器软件，然后继续使用相同的解码器。这就是兼容性。 为了节省你的时间，让我这样描述：压缩流由一些动作组成，每个动作要么是“输出这个字节”，要么是命名一个之前的动作并说“重新执行这个动作的所有操作，然后再加上紧随其后的动作的第一个字节”。（选择最后那个动作的边界情况也完全可行，论文中称之为 KwKwK。）（GIF 还有一个“数据结束”动作和一个“重置状态”动作，但这不相关。） 简单吧？至少对我来说听起来简单多了。比通过阅读 9 行压缩伪代码和对应的 9 行解压伪代码开始理解要简单得多。 那么算法可以简单地表达为贪心方法：查看所有之前的动作，取能与后续数据匹配的最长那一个。这双重合理，因为 (a) 局部最优至少有机会成为全局最优，(b) 它总能为“词汇表”添加一个新“词”。 为了节省你的时间，这里给出一个待压缩的示例流： ``` a b a b a b a a b a a b a a a b ``` 其中一种可能的方式（贪心方式）将其拆分为： ``` a b a-b a-b-a a-b-a-a b-a a a-b 1. 输出 a。（无法输出 ab；重放此动作将输出 ab） 2. 输出 b。（无法输出 ba；重放此动作将输出 ba） 3. 重放动作 1。（输出 ab，无法输出 aba；重放此动作将输出 aba） 4. 重放动作 3。（输出 aba，无法输出 abaa；重放此动作将输出 abaa） 5. 重放动作 4。（输出 abaa，无法输出 abaab；重放此动作将输出 abaab） 6. 重放动作 2。（输出 ba，无法输出 baa；重放此动作将输出 baa） 7. 输出 a。（无法输出 aa；重放此动作将输出 aa） 8. 重放动作 1。（输出 ab。无法输出 abEOF；最后一个永远不会被重放，但取决于 9 的第一个字母，它会是 aba 或 abb） ``` 但这并非唯一方式。我们再看看： ``` a b a-b a-b-a a-b-a a-b-a-a a-b 1. 输出 a。（无法输出 ab；重放此动作将输出 ab） 2. 输出 b。（无法输出 ba；重放此动作将输出 ba） 3. 重放动作 1。（输出 ab，无法输出 aba；重放此动作将输出 aba） 4. 重放动作 3。（输出 aba，无法输出 abaa；重放此动作将输出 abaa） 5. 重放动作 3。（输出 aba，尽管动作 4 会输出 abaa；重放此动作将输出 abaa——与重放 4 的结果相同！浪费了一个字典槽！） 6. 重放动作 4。（输出 abaa，无法输出 abaab；重放此动作将输出 abaab） 7. 重放动作 1。（输出 ab。无法输出 abEOF；最后一个永远不会被重放，但取决于 8 的第一个字母，它会是 aba 或 abb） ``` 少了一个动作！不过，请注意第 5 步的注释。 好了，回到 flexiGIF。它所做的事情是*灵活解析*。这意味着程序不会立即决定最远可达的动作，而是推迟决策，直到它知道两个动作的最远可达组合为止。然后它发出第一个动作，但仍保留第二个动作以便重新评估。这称为单步前瞻。所以基本上还是贪心，但现在使用了两个动作。理论上它应该好得多，甚至是最优的，但第 5 步的情况意味着现在浪费了一个字典槽，并且它永远丢失了（至少在重置之前）。所以这就是 flexiGIF 可能产生更差结果的原因。它完全放弃了贪心压缩，而是坚持“对于每个（子）贪心匹配，找到贪心的下一个匹配；发出前者”。 ## ZGIF 这就是我需要编写自己工具的地方。我在想，“实际检查所有可能性会有多慢？”于是我尝试了，结果发现了什么？慢如冰川！（这里我该指出，Python 并不是 CPU 密集型软件的最佳选择。我想借此机会学习 Zig。）在我的笔记本上，完全压缩一个 16x16 的图像需要 4 分钟。那只是 256 字节的未压缩数据。而且耗时好几分钟。哇。我一定是在重复计算相同的东西，对吗？（不，只是有些探索并不能带来改进。第一个版本花了 30 分钟。） 于是我决定应该提供一个选项，使其仅快一点，方法是跳过所有那些无法立即扩展到超过当前最佳值的探索（嗯，将搜索限制为单步前瞻）。这会使结果变差（找不到真正的最佳解），但从 4 分钟降到 4 秒，同时仍能击败当前最先进水平，这是一个值得考虑的胜利。你可以看一下 SourceHut 上的 ZGIF 仓库 (https://git.sr.ht/~arusekk/zgif/)。代码一点也不整洁，但你可以在 Git 历史中看到我的思考过程——从 A* 到动态规划，再到带有剪枝的混合搜索。希望对你有用！