|
最近 Google 出了一个新的开源项目 Zopfli。Zopfli是什么呢？简单说是一个 Deflate 压缩算法的另一种实现。推出之后国内国外媒体纷纷报道转载。昨天看到国内媒体的报道 （搜狐IT）中说道：“据悉，Zopfli的压缩率比现有的Zlib高3-8倍。”当时看到了就吓了一大跳，3-8倍这是要逆天啊！赶紧去Zopfli主页看一眼，原来只是3%-8%的提升。国内IT编辑真是吓死人不偿命。
Zopfli到底表现怎么样呢？先看看 Zopfli 自己提供的数据：
大概是比标准的gzip -9要小 3.7%-8.3% 的样子。但是压缩所需要的时间非常的惊人：
可以说如果用 gzip 压缩要喝口水的时间的话，用 Zopfli 就可以出去吃个便饭了。 我们再看看这些算法的出生年份：Deflate最早诞生于1994年。7-zip最早诞生于1999年，也是一个开源项目，虽然7-zip自己默认用的格式是LZMA和LZMA2算法，但是也支持对Deflate算法的更好的压缩。KZip 是 Pngout 作者写的一个小工具，诞生于2006年，是一个把现有Zip再压缩的工具。 这里不得不提几个Zopfli文档里没有提到的其它 Deflate 兼容的压缩工具：DeflOpt，是2007年诞生的一个Zip再压缩工具。AdvZip，是一个利用7-zip Deflate的一个Zip再压缩工具。 可以从表中看出，Zopfli比1994年原版Deflate确实有3%-8%的提升，但是对比比较新的Deflate实现，提升实在是很有限，比如比KZip只提升了大概1%不到。压缩时间对比KZip也增加了相当多。 发布没多久，就有人发现，利用 KZip+DeflOpt，压缩的结果可以比Zopfli压缩的更小，甚至Zopfli的几个样本的压缩结果，依然可以用 DeflOpt 再压缩一点(1%左右)。所以说Zopfli其实并不是他在文档里所说的，“所有已知Deflate算法实现里压缩比最高的”。 当然，Zopfli的意义在于它是开源算法，而KZip+DeflOpt这俩都不开源。关于KZip，DeflOpt是如何实现的，之前还有很多人在猜测。Zopfli的出现给大家提供了很好的解答。 另一点值得探讨的是，在今天研究Deflate算法更好实现是否还有价值。Zlib的作者本人Mark Adler在听说Zopfli之后说：“这很酷，不过看上去是一个付出了很多努力，但只取得了很小提升的一个糟糕结果。也许到了给HTTP的accept-encoding加上更好算法的时候了”。是的，诞生于1994年的Deflate确实太老了。现有的解压更快、压缩比更高的开源算法有很多很多，比如 bzip2, LZMA/XZ等等。LZMA/XZ在解压速度上，以及压缩比上，都完胜Deflate。Deflate对于很多 UTF-8 3 bytes的网页压缩效果也很不理想。直到今天，支持bzip2, LZMA的浏览器还寥寥无几。也许更有前途值得关注的是HTTP/2.0协议(一部分基于Google的SPDY协议)。 重新回到Deflate算法。为何Deflate有如此多的压缩实现呢？我们得详细的看看Deflate算法的具体内容。Deflate算法其实就是LZ77算法加Huffman算法。先经过LZ77的字典找重，然后用Huffman树进行降比特。不同的Deflate压缩的实现其关键在于LZ77的搜索重复单词，以及选择分块来进行Huffman。早期算法例如7-zip对分块都不是很重视，更多的考虑的是LZ77算法的优化。而KZip另辟蹊径对分块也进行了优化，使得最终比特流长度变得更短。 LZ77算法优化是一个有向图上的最短路径的搜索问题。对于字节流每个字节建立单边节点，重复单词序列建立更短的边，形成一个有向图。LZ77算法的目的就是如何找到有向图从起点到终点的最短路径。对于边的长度确定的情况下，用动态规划找最优解是很简单的。然而LZ77在搜索时，如果要考虑下一步Huffman过滤之后的长度，则边长度就是不固定的。Zopfli采用迭代的办法，先用一次贪心法拿到第一个次好的结果，然后通过使用结果字节的熵值（就是出现频率的N-log2n）来给出下一次迭代的每条边的边长，也就是每个字母的比特长度。通过反复迭代，来逐步逼近最好结果。当然，理论上也可能跌入一个次好结果的低谷。
然后是最关键的分块问题。分块为何会影响Huffman的压缩结果？其主要问题还是因为动态Huffman算法的随机性。如果都采用对字节使用频率统计完毕之后的静态Huffman，那么不管如何分块都不会对结果有影响，反而因为分块产生额外的比特，使得结果变大。动态Huffman的树是在字节流的处理过程中动态创建的，因此其字节流的开始片段不规律性往往使得结果不优。如何分块才能更优？因为随机性太大，也很难进行判断。所以KZip和Zopfli采用的都是尽可能的穷举。KZip就号称用了“重复单词的穷举(LZ77)”和“更高效率的分块(Huffman)”来实现，可以增加分块的个数进行进一步优化。而Zopfli，是不停的在一个最大块内找9个点，穷举判断哪一个最优，然后进行反复切割的办法。 Deflate压缩算法有没有最优解？这其实是个NP问题。对于短短32字节大小的数据，都有2**31 = 2147483648 种不同的分块方案。当然绝大多数分块都没有意义而产生更差结果。分块之后依然还有需要进行迭代的边长会变化的最短路径问题需要解决。 最后，尽管 Zopfli 的结果不是很令人满意，不过确实给众多不开源的 Deflate 压缩工具树立了标杆。那些想靠着 Deflate 算法做收费 PNG 压缩的软件可以洗洗睡了。 我定期会更新博客在这里，有事儿没事儿可以来瞅瞅http:/// |
|
|
