创作原因

不久前,我发现需要一台PNG装载机用于我的一个小项目。作为一个完整的工具,我当然决定自己写一个 - 毕竟,为什么在还有车轮等待重新发明时为自己省力?如果你愿意的话,可以在这里查看inflater代码的来源 - 它写得非常干净。事实上,我专门写它是为了易于阅读,而不是最快的实现。

我当时对Deflate了解不多。我知道它基于LZ系列算法(LZ77 / L7SS等)。我听说有人说它只是“只是”LZSS,除了他们在匹配向量上应用霍夫曼编码。嗯,事实证明这是真的。均田。但是当我更深入地阅读规范时,它让我觉得这里发生了一些非常聪明的事情,我之前没有看到过任何明确提出过的事情。所以我想为什么不试着在这里解释Deflate的本质。我不打算在严格的细节上涵盖整个工作;如果你想要那就去阅读规范。

Deflate是由Phil Katz于1993年发明的,它构成了ZIP文件格式,zlib库,gzip,PNG以及其他一些东西的基础。当时它非常前沿。当时的主要竞争对手通常是LZW,或者也许是LZSS。在许多人的眼中,压缩仍然是游程编码的同义词,因此当Deflate出现时它肯定会变成一些头脑。现在这已经超过了20年,所以后来像LZMA这样的编解码器(我可能有一天会写一下)可以定期击败它。它仍然没有死。

勘误表

因此,LHA归档程序也使用了此处描述的基本原理,它早于PKZIP 2.0。也许我可以说这篇文章是“LHA的优雅”?好吧,我不会,所以那里。历史是由胜利者和具有更好的首字母缩略词的人写的。

压缩

压缩有两种基本方法。好吧不,那不是真的,但不管怎样,让我们​​继续吧,然后按下。

老实说,如果你对压缩有所了解,你很可能会对此大部分都有所了解,但这里无论如何。

  • 基于熵的压缩

  • 基于字典的压缩

基于熵的压缩是一个非常古老的想法。计算机通常将字母存储为8位;每个字母一个字节。

“多么浪费,”有人想。像E和T这样的字母很常见,而像Q和Z这样的字母很少出现。有意义的是,你想要更少的位用于更常见的字母。

独立宣言的频率计数。小写占主导地位,资本几乎不存在。

这个想法甚至早于计算机。去看摩尔斯代码 - 英语中最常见的两个字母(E和T)只是一个点和短划线。

霍夫曼编码是一种非常古老而简单的应用方法。您从“字母表”开始 - 您要编码的所有符号的集合。在学校的英语,我们被告知我们的字母表是26个字母。然而,在计算机中,我们还需要更多。我们需要存储大写字母,小写字母,数字,标点符号,我们需要一个“空间”符号和一些其他小东西。获得完整的字母后,您需要分配概率。我们知道一些字母(e / t / a / i / etc)比其他字母(q / x / y / z / etc)更常见,但我们还必须考虑这个扩展字母表的其余部分。数字在英国散文中很少见,首都也是如此。本段有五百六十一个小写字母,但只有十个大写字母。

一旦你的概率全部整理出来,你就构建了一个霍夫曼树。这为每个字母分配了一个唯一的代码,除了“自我终止”的方式。即,您不需要存储任何其他信息来说明每个字母的开始和停止位置。如果你看一下摩尔斯电码的例子,就不会那样。虽然莫尔斯有点和短划线,但它也有间隙,需要间隙来分割字母。霍夫曼编码不需要间隙。

所以这是熵编码 - 你决定使用字母表,你使用较少的位来存储常见的东西,使用更多的位来处理稀有事物。你可以用它来压缩像英语这样的东西,虽然它工作得很好,但它还有很大的改进空间。当然,这是比霍夫曼编码更好的方法,比如算术编码,但霍夫曼是最容易理解的。这也是Deflate使用的东西,所以我们会把它留在那里。

LZ77

LZ77构成了基于字典的算法的基础。字典压缩的想法很简单,某些事情在文档中出现不止一次。

例如,如果您在此页面中搜索“压缩”一词,则会多次出现。因此,不要每次都再次存储它,让我们尝试参考之前的用法。

LZ77非常简单。您存储匹配向量(由长度和距离组成的一对),并在匹配后存储结束匹配的字母(“文字”)。

因此,例如,如果我想存储短语sense和sensibility,我们会看到sens部分被使用了两次。所以我们可能会将第二种用法存储为返回10,复制4,字母i,因为我们需要复制“sens”的4个字母,然后在最后添加新的i。

看起来很好,对吗?不,LZ77很糟糕。虽然它可以通过参考之前的短语来节省空间,但这就是它所能做到的。模式是固定的 - 它存储了一个匹配,然后是一个字母。但如果 没有匹配怎么办?要使用相同的示例,以下是LZ77实际存储整个报价的方式:

输入:感觉和感性
输出:[返回0,复制0] s [返回0,复制0] e [返回0,复制0] n [返回0,复制0] s [返回0,复制0] e [返回0,复制0] [返回0,复制0] a [返回0,复制0] n [返回0,复制0] d ...

真是一团糟。你明白了。它必须存储一个匹配,即使没有匹配。并且存储该空匹配信息需要空间。典型的矢量可能是16位(距离返回为12位,长度为4位)。所以以前每个字母8位的东西现在最终可以达到每个字母24位!这就是没有人使用原始LZ77的原因。

因此他们发明了LZSS,这是许多早期档案馆使用的。 LZSS存储一个比特来说明下一个出现的是匹配向量还是文字符号。这是一个非常明显的想法,我不知道为什么不早点想到它。所以现在我们的额外标记位允许我们标记匹配向量是否为空,并简单地跳过所有浪费的开销。

无论如何,这是字典压缩。当它能够获得很多好的比赛时,它的效果非常好。不过,这是多余的一点。我们用来表示我们是否匹配的那个讨厌的“文字”位。如果没有匹配会怎么样?在那种情况下,我们已经从最初每个字母存储8位到存储9位!如果没有匹配发生,LZSS将存储1位以指示字母,然后再存储8位以存储该字母!

LZ77,LZSS和家族中的其他人都遭遇同样的问题,不得不切换模式的开销 - 当他们发现不适合基于字典的匹配类的东西时,他们需要写出某种类型的标记切换到文字模式。这一切都占用了流中的宝贵空间。 (如果你不小心,有时你会浪费这么多开头做这种切换,你实际上根本不压缩文件,你会放大它!)

所以我们有两种压缩算法。 LZSS依赖于找到以前匹配的数据,而Huffman编码依赖于某些字母比其他字母更常见。我们能比选择其中一个更好吗?我们可以把它们编织在一起吗?

我们可以。

Deflate

如果我们想要将这两种算法结合在一起,那么想象我们如何做到这一点并不是一个很大的飞跃。我们从LZSS开始吧?匹配部分似乎没问题,只是文字会让我们陷入困境,因为它们完全没有压缩。那怎么样 - 我们可以只用霍夫曼编码呢?我们存储一点,如果它是匹配或文字,如果它是匹配,那么我们写一个16位匹配向量,如果它是一个文字,那么我们写一个可变长度的霍夫曼编码符号。

我觉得这样做很好,但这并不是Deflate如何做到的。放气比这更进一步。您仍然需要支付该标记位的成本来切换模式。为了理解Deflate,我们需要扩展我们对字母表的概念。

你看,当我们听到“字母表”这个词时,我们回想起我们学到的孩子–A,B,C等等。但是当我们开始参与压缩时,我们知道事实并非如此。我们已经不得不扩展我们的字母表以包括大写字母和数字等。即使是甚至不可见的空间,我们也必须对它们进行编码。 Deflate只是将这个概念向前推进了一步。

Deflate基于统一字母表的概念。如果字母表只是一组选择,为什么不把所有选择放在一个伞下呢? Deflate的字母表由286个符号组成。前256个是每个字母的ASCII码,包括所有ASCII控制码和其他类似的ASCII码。其余30个符号用于表示长度。没错,我们在这里存储实际的匹配长度。这是使用的实际表格:

0-255	Regular input byte
256	End of data block
257	Match of length 3 (distance follows after)
258	Match of length 4 (distance follows after)
259	Match of length 5 (distance follows after)
260	Match of length 6 (distance follows after)
261	Match of length 7 (distance follows after)
262	Match of length 8 (distance follows after)
263	Match of length 9 (distance follows after)
...	etc

除此之外还有更多内容,为了清楚起见,我在这里省略了,但希望这可以解释原理。 我们现在有286个符号,每个符号都有自己的概率,因此也有自己的霍夫曼代码。 我们知道有些字母仍然会更常见(E,T等)。 但比赛怎么样? 他们有多常见?

还记得我们之前如何获得英文文本的频率图吗? 那么这就是我们扩展字母表的外观:

elegance-of-deflate/alphabet.png

您可以看到小写的“e”很受欢迎,其他一些小写的“e”也很流行,比如“a / i / t / etc”。

资本几乎不存在,在这种情况下根本没有数字。然而有些东西像拇指一样伸出 - 字典匹配主导概率域。同样有趣的是,小写字母的概率已经改变,因为字典匹配晚上它。

当我们一次压缩一个符号的数据时,我们在每个压缩阶段都会面临一个选择。如果我们可以找到前一个匹配,那么我们可以将该匹配向量写出来,如果我们不这样做,那么我们就写出文字符号。但是Deflate的独特之处在于它与前辈的区别在于,无论我们选择何种选项,我们都只会写出一个单独的霍夫曼编码符号。

如果我们想要连续存储两个匹配项,或者连续存储两个文字,我们可以这样做。一个字母表存储两个不同的想法。指定模式之间切换不需要位标记。我们存储根据频率压缩的文字字母,我们也根据它们的频率存储匹配长度,但不止于我们在一个统一的方案下做这两件事。

它不是一种算法而是两种算法,它们和谐共舞。您可以选择字典匹配或熵编码,您可以在每个字节的基础上选择它们,而无需开销。这就是我发现它如此聪明 - 不是它可以做一件事或另一件事,而是它可以选择任何一种,但用同一种语言代表它们。没有额外的标记,没什么可说的“哦,现在我们正在切换到熵模式”,没有什么可以阻碍。

它是一个RLE编码器,它是一个字典匹配器,它是一个频率表,它是所有这些东西,中间没有障碍,没有切换模式也没有单独的传递来运行。

Deflate仍然是两个算法如何结合在一起并相互发挥作用的一个很好的例子,而不是与自己作斗争。

我得承认,我印象深刻。

zip 算法

无意间看到一篇非常好的文档。

ZIP压缩算法详细分析及解压实例解释

压缩和归档的作用

  1. mq 传输的时候,数据较大,就需要压缩。(一般网络传输)

  2. 数据存储,数据量很大的时候。比如数据库,日志就需要归档。

  3. 这个技术为后期框架提供基础。

个人总结

  1. 基于信息熵的编码。比如 Huffman 树,数字概率编码。

  2. 基于字典的编码。游程编码。多元游程编码。

比如:

00001111000

我们约定二进制以0开始,则记为:

443

然后将其转换为二进制:

100 100 011                                                                                                                              
  1. 综合使用

实际使用,当然可以把二者结合起来使用。比如 Defalte 算法。

参考资料

The Elegance of Deflate