EEPW论坛

DEFLATE算法简介   gzip 对于要压缩的文件，首先使用lz77算法进行压缩，对得到的结果再使用huffman编码的方法进行压缩。所以我们分别对lz77和huffman编码的原理进行说明。
1、gzip压缩算法实现方法 1．1          算法的gzip实现LZ77 首先，gzip 从要压缩的文件中读入64KB的内容到一个叫window的缓冲区中。为了简单起见，我们以32KB以下文件的压缩为例做说明。对于我们这里使用32KB以下文件，gzip将整个文件读入到window缓冲区中。然后使用一个叫strstart的变量在window数组中，从0开始一直向后移动。strstart在每一个位置上，都在它之前的区域中，寻找和当前strstart开始的串的头3个字节匹配的串，并试图从这些匹配串中找到最长的匹配串。 如果当前的strstart开始的串，可以找到最少为3个字节的匹配串的话，当前的strstart开始的匹配长度那么长的串，将会被一个<匹配长度,到匹配串开头的距离>对替换。 如果当前的strstart开始的串，找不到任何的最少为3个字节的匹配串的话，那么当前strstart的所在字节将不作改动。 为了区分是一个<匹配长度,到匹配串开头的距离>对，还是一个没有被改动的字节，还需要为每一个没有被改动的字节或者<匹配长度,到匹配串开头的距离>对，另外再占用一位，来进行区分。这位如果为1，表示是一个<匹配长度,到匹配串开头的距离>对，这位如果为0，表示是一个没有被改动的字节。 现在来说明一下，为什么最小匹配为3个字节。这是由于，gzip 中，<匹配长度,到匹配串开头的距离>对中，"匹配长度"的范围为3-258，也就是256种可能值，需要8bit来保存。"到匹配串开头的距离"的范围为0-32K，需要15bit来保存。所以一个<匹配长度,到匹配串开头的距离>对需要23位，差一位3个字节。如果匹配串小于3个字节的话，使用<匹配长度,到匹配串开头的距离>对进行替换，不但没有压缩，反而还会增大。所以保存<匹配长度,到匹配串开头的距离>对所需要的位数，决定了最小匹配长度至少要为3个字节。 下面我们就来介绍gzip如何实现寻找当前strstart开始的串的最长匹配串。 如果每次为当前串寻找匹配串时，都要和之前的每个串的至少3个字节进行比较的话，那么比较量将是非常非常大的。为了提高比较速度，gzip使用了哈希表。这是gzip实现LZ77的关键。这个哈希表是一个叫head的数组（后面我们将看到为什么这个缓冲区叫head）。gzip对windows中的每个串，使用串的头三个字节，也就是strstart,strstart 1,strstart 2，用一个设计好的哈希函数来进行计算，得到一个插入位置ins_h。也就是用串的头三个字节来确定一个插入位置。然后把串的位置，也就是 strstart的值，保存在head数组的第ins_h项中。我们马上就可以看到为什么要这样做。head数组在没有插入任何值时，全部为0。当某处的当前串的三个字节确定了一个ins_h，并把当时当前串的位置也就是当时的strstart保存在了head[ins_h]中。之后另一处，当另一处的当前串的头三个字节，再为那三个字节时，再使用那个哈希函数来计算，由于是同样的三个字节，同样的哈希函数，得到的ins_h必然和前面得到的ins_h是相同的。于是就会发现head[ins_h]不为0。这就说明了，有一个头三个字节和自己相同的串把自己的位置保存在了这里，现在head[ins_h]中保存的值，也就是那个串的开始位置，我们就可以找到那个串，那个串至少前3个字节和当前串的前3个字节相同（稍后我们就可以看到这种说法不准确，这里是为了说明方便），我们可以找到那个串，做进一步比较，看到底能有多长的匹配。 我们现在来说明一下，相同的三个字节，通过哈希函数得到的ins_h必然是相同的。而不同的三个字节，通过哈希函数有没有可能得到同一个ins_h，我没有对这个哈希函数做研究，并不清楚，不过一般的哈希函数都是这样的，所以极大可能这里的也会是这种情况，即不同的三个字节，通过哈希函数有可能得到同一个ins_h，不过这并不要紧，我们发现有可能是匹配串之后，还会进行串的比较。 一个文件中，可能有很多个串的头三个字节都是相同的，也就是说他们计算得到的ins_h都是相同的，如何能保证找到他们中的每一个串呢？gzip使用一个链把他们链在一起。gzip每次把当前串的位置插入head的当前串头三个字节算出的ins_h处时，都会首先把原来的head[ins_h]的值，保存到一个叫prev的数组中，保存的位置就在现在的strstart处。这样当以后某处的当前串计算出ins_h，发现head[ins_h]不空时，就可以到prev[ head[ins_h] ]中找到更前一个的头三个字节相同的串的位置。对此我们举例说明。  例，串
　　 0abcdabceabcfabcg
　　 ^^^^^^^^^^^^^^^^^
　　 01234567890123456

　　整个串被压缩程序处理之后。

　　由abc算出ins_h。
　　这时的head[ins_h]中为 13,即"abcg"的开始位置。
　　这时prev[13]中为 9，即"abcfabcg"的开始位置。
　　这时prev[9]中为 5，即"abceabcfabcg"的开始位置。
　　这时prev[5]中为 1，即"abcdabceabcfabcg"的开始位置。
　　这时prev[1]中为 0。

　　我们看到所有头三个字母为abc的串，被链在了一起，从head可以一直找下去，直到找到0。 现在我们也就知道了，三个字节通过哈希函数计算得到同一ins_h的所有的串被链在了一起，head[ins_h]为链头，prev数组中放着的更早的串。这也就是head和prev名称的由来。 gzip寻找匹配串的另外一个值得注意的实现是，延迟匹配。会进行两次尝试。比如当前串为str,那么str发生匹配以后，并不发生压缩，还会对str 1串进行匹配，然后看哪种匹配效果好。如果碰到的一个匹配就使用了的话，可能错过更长匹配的机会。 1．2          问题讨论 这种匹配算法，即用3个字节(最小匹配)来计算一个整数，是否比用串比较来得高效，高效到什么程度。 哈希函数的讨论。不同的三个字节，是否可能得到同一个ins_h。ins_h和计算它的三个字节的关系。 几次延迟尝试比较好？ 用延迟，两次尝试是否对压缩率的改善是非常有限的？ 影响lz77压缩率的因素。 压缩的极限。 1．3          gzip源码分析 main() 中调用函数 treat_file() 。 treat_file() 中打开文件，调用函数 zip()。注意这里的 work 的用法，这是一个函数指针。 zip() 中输出gzip文件格式的头，调用 bi_init，ct_init，lm_init，　　 其中在lm_init中将 head 初始化清0。初始化strstart为0。从文件中读入64KB的内容到window缓冲区中。由于计算strstart=0时的ins_h，需要0,1,2这三个字节和哈希函数发生关系，所以在lm_init中，预读0,1两个字节，并和哈希函数发生关系。然后lm_init调用 deflate()。deflate() gzip的LZ77的实现主要deflate()中。 1．4          代码说明      deflate不依赖于CPU类型，操作系统类型，文件系统类型，字符集。因此可以被用来进行交换。  能够被生成或是去除，甚至是使用一个预先确定的中间存贮器的边界长度，对一个任意长的连续输入数据流进行操作。因此可以被用在数据通信及相似的结构中，如UNIX过滤器。  其压缩效率可与目前的可用的，最普遍的压缩方法相比拟。而且在一些方面还要好于压缩程序。      一个压缩的数据集包含一系列的块，与输入数据的块相对应。块的大小是任意的，但是非压缩的块要在65535字节之内。 每一块的压缩都使用了LZ77法则和Huffman编码方法。每块的Huffman树都和它的前一块及后一块无关。LZ77法则可以参考所复制的前一个串中的前32K内容。 每个块包含了两部分：1)一对Huffman编码树，它描述了压缩内容的表示方法。2)还有就是压缩数据的部分。（其中的Huffman树也是经过了Huffman编码的）压缩后的数据包括了两种类型。1）文字字节（是字符串的一部分，这个字符串不是所复制的前32K的内容。2）指向复制的字符串的指针，这个指针的形式是一个<长度，向后的距离>对。这个使用在"deflate"格式中的形式限定了距离为32K及长度为258字节。但是没有限制块的大小(除了没有压缩的数据以外)。 压缩数据中的每种类型值(文字，距离及长度)都使用Huffman编码方法，使用一个编码树编码文字和长度，使用另一个独立的编码树来编码距离。每一块的编码树都以压缩的方式存在于那一块中压缩的数据之前的位置。