gzip压缩算法

1 gzip所使用压缩算法的基本原理

　　 gzip 对于要压缩的文件，首先使用lz77算法进行压缩，对得到的结果再使用huffman编码的方法进行压缩。所以我们分别对lz77和huffman编码的原理进行说明。

　　 1.1 ... 1.2 ...

　　 2 gzip压缩算法实现方法

　　 2.1 LZ77算法的gzip实现

　　首先，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，不过这并不要紧，我们发现有可能是匹配串之后，还会进行串的比较。