压缩算法deflate

1、压缩算法 deflategzip,zlib,以及图形格式 png,使用的是同一个压缩算法 deflate。我们通过对 gzip 源码的分析来对 deflate 压缩算法做一个详细的说明。 我阅读的 gzip 版本为 gzip-1.2.4。 我们对算法做三种程度的说明。第一种程度，对 gzip 所使用压缩算法基本原理的说明。第二种程度，对 gzip 压缩算法实现方法的说明。第三种程度，对 gzip 实现源码级的说明。如果你有时间的话，我建议你先不要看下面的内容，自己尝试通过读 gzip源码，来了解它的压缩解压缩是如何实现的，这将会是一个非常有趣的智力游戏，千万不要错过。当一个又一个的谜被解开时，

2、那感觉就像唐伯虎同志所说的，“慷慨然诺杯酒中”。（小唐的诗，除了另一个倒霉蛋曹雪芹外，好像不太被人提。）1 gzip 所使用压缩算法的基本原理gzip 对于要压缩的文件，首先使用 lz77 算法进行压缩，对得到的结果再使用huffman 编码的方法进行压缩。所以我们分别对 lz77 和 huffman 编码的原理进行说明。1.1 .1.2.2 gzip 压缩算法实现方法2.1 LZ77 算法的 gzip 实现首先，gzip 从要压缩的文件中读入 64KB 的内容到一个叫 window 的缓冲区中。为了简单起见，我们以 32KB 以下文件的压缩为例做说明。对于我们这里使用 32KB 以下文件，g

3、zip 将整个文件读入到 window 缓冲区中。然后使用一个叫 strstart 的变量在window 数组中，从 0 开始一直向后移动。strstart 在每一个位置上，都在它之前的区域中，寻找和当前 strstart 开始的用的头 3 个字节匹配的用，并试图从这些匹配用中找到最长的匹配用。如果当前的 strstart 开始的用，可以找到最少为 3 个字节的匹配用的话，当前的strstart 开始的匹配长度那么长的申，将会被一个匹配长度，到匹配用开头的距离对替换。如果当前的 strstart 开始的用，找不到任何的最少为 3 个字节的匹配用的话，那么当前 strstart 的所在字节将不作

4、改动。为了区分是一个匹配长度，到匹配用开头的距离对，还是一个没有被改动的字节，还需要为每一个没有被改动的字节或者匹配长度，到匹配用开头的距离对，另外再占用一位，来进行区分。这位如果为 1,表示是一个匹配长度，到匹配用开头的距离对，这位如果为 0,表示是一个没有被改动的字节。现在来说明一下，为什么最小匹配为 3 个字节。这是由于，gzip 中，匹配长度，到匹配用开头的距离对中，匹配长度”的范围为 3-258,也就是 256 种可能值，需要8bit 来保存。到匹配用开头的距离的范围为 0-32K,需要 15bit 来保存。所以一个匹配长度，到匹配用开头的距离对需要 23 位，差一位 3 个字节。如

5、果匹配用小于 3 个字节的话，使用匹配长度，到匹配用开头的距离对进行替换，不但没有压缩，反而还会增大。所以彳存匹配长度，到匹配用开头的距离对所需要的位数，决定了最小匹配长度至少要为 3 个字节。卜面我们就来介绍 gzip 如何实现寻找当前 strstart 开始的用的最长匹配用如果每次为当前用寻找匹配用时， 都要和之前的每个用的至少 3 个字节进行比较的话，那么比较量将是非常非常大的。为了提高比较速度，gzip 使用了哈希表。这是 gzip 实现 LZ77 的关键。这个哈希表是一个叫 head 的数组（后面我们将看到为什么这个缓冲区叫 head）。gzip 对 windows 中的每个用，使用

6、用的头三个字节，也就是 strstart,strstart+1,strstart+2,用一个设计好的哈希函数来进行计算，得到一个插入位置 ins_h。也就是用用的头三个字节来确定一个插入位置。然后把用的位置，也就是 strstart 的值，保存在 head 数组的第 ins_h 项中。我们马上就可以看到为什么要这样做。head 数组在没有插入任何值时，全部为00当某处的当前用的三个字节确定了一个 ins_h,并把当时当前用的位置也就是当时的strstart 保存在了 headins_h中。之后另一处，当另一处的当前用的头三个字节，再为那三个字节时，心使用那个哈希函数来计算，由于是同样的三个字节

7、，同样的哈希函数，得到的 ins_h 必然和前面得到的 ins_h 是相同的。于是就会发现headins_h不为 0。这就说明了，有一个头三个字节和自己相同的用把自己的位置保存不了这里，现在 headins_h中保存的值，也就是那个用的开始位置，我们就可以找到那个用，那个用至少前 3 个字节和当前用的前 3 个字节相同（稍后我们就可以看到这种说法不准确，这里是为了说明方便），我们可以找到那个用，做进一步比较，看到底能有多长的匹配。我们现在来说明一下， 相同的三个字节， 通过哈希函数得到的 ins_h 必然是相同的。而不同的三个字节，通过哈希函数有没有可能得到同一个 ins_h,我没有对这个哈希

8、函数做研究，并不清楚，不过一般的哈希函数都是这样而，所以极大可能这里的也会是这种情况，即不同的三个字节，通过哈希函数有可能得到同一个 ins_h,不过这并不要紧，我们发现有可能是匹配用之后，还会进行申的比较。一个文件中，可能有很多个用的头三个字节都是相同的，也就是说他们计算得到的 ins_h 都是相同的，如何能保证找到他们中的每一个用呢？gzip 使用个链把他们链在一起。gzip 每次把当前用的位置插入 head 的当前用头三个字节算出的ins_h 处时，都会首先把原来的 headins_h的值，保存到一个叫 prev 的数组中，杀存的位置就在现在的 strstart 处。这样当以后某处的当前

9、审计算出 ins_h,发现 headins_h不空时，就可以到 prevheadins_h中找到更前一本的头三个字节相同而用的位置。对此我们举例说明。一例，用0abcdabceabcfabcgAAAAAAAAAAAAAAAAA01234567890123456整个用被压缩程序处理之后。由 abc 算出 ins_h。这时的 headins_h中为 13,即abcg的开始位置。这时 prev13中为 9,即abcfabcg的开始位置。这时 prev9中为 5,即abceabcfabcg”的开始位置。这时 prev5中为 1,即abcdabceabcfabcg”的开始位置。这时 prev1中为 0。

10、我们看到所有头三个字母为 abc 的用，被链在了一起，从 head 可以一直找下去，直到找到00现在我们也就知道了，三个字节通过哈希函数计算得到同一 ins_h 的所有的用被链在了一起，headins_h为链头，prev 数组中放着的更早的用。这也就是 head 和prev 名称的由来。gzip 寻找匹配用的另外一个值得注意的实现是，延迟匹配。会进行两次尝试。比如当前用为 str,那么 str 发生匹配以后，并不发生压缩，还会对 str+1 用进行匹配，然后看哪种匹配效果好。例子从这个例子中我们就看到了做另外一次尝试的原因。如果碰到的一个匹配就使用了的话，可能错过更长匹配的机会。现在做两次会有

11、所改善。2.2 问题讨论我在这里对 gzip 压缩算法做出了一些说明，是希望可以和对 gzip 或者压缩解压缩感兴趣的朋友进行交流。我对 gzip 的了解要比这里说的更多一些，也有更多的例子。如果哪位朋友愿意对下面的问题进行研究，以及其他压缩解压缩的问题进行研究，来这里http:/ 3 个字节(最小匹配)来计算一个整数，是否比用用比较来得高效，高效到什么程度。哈希函数的讨论。不同的三个字节，是否可能得到同一个 ins_hoins_h 和计算它的三个字节的关系。一一几次延迟尝试比较好？用延迟，两次尝试是否对压缩率的改善是非常有限的？影响 lz77 压缩率的因素。压缩的极限。2.3 .3 gzip 源码分析main()中调用函数 treat_file()。treat_file()中打开文件，调用函数 zip()。注意这里的 work 的用法，这是一个亩数指针。zip()中输出 gzip 文件格式的头，调用 bi_init,ct_init,lm_init,其中在 lm_init 中将 head 初始化清 0。初始化 strstart