gzip压缩算法

　　一个文件中，可能有很多个串的头三个字节都是相同的，也就是说他们计算得到的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串进行匹配，然后看哪种
　　匹配效果好。

　　例子 ...
从这个例子中我们就看到了做另外一次尝试的原因。如果碰到的一个匹配就使用了的话，可能错过更长匹配的机会。现在做两次会有所改善。

　　 ...

　　 2.2 问题讨论

　　我在这里对gzip压缩算法做出了一些说明，是希望可以和对gzip或者压缩解压缩感兴趣的朋友进行交流。
　　我对gzip的了解要比这里说的更多一些，也有更多的例子。如果哪位朋友愿意对下面的问题进行研究，以及其他压缩解压缩的问题进行研究，来这里http://jiurl.cosoft.org.cn/forum/ 和我交流的话，我也愿意就我知道的内容进行更多的说明。

　　下面是几个问题

　　这种匹配算法，即用3个字节(最小匹配)来计算一个整数，是否比用串比较来得高效，高效到什么程度。

　　哈希函数的讨论。不同的三个字节，是否可能得到同一个ins_h。ins_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为0。从文件中读入64KB的内容到window缓冲区中。
　　由于计算strstart=0时的ins_h，需要0,1,2这三个字节和哈希函数发生关系，所以在lm_init中，预读0,1两个字节，并和哈希函数发生关系。

　　然后lm_init调用 deflate()。
　　 deflate() gzip的LZ77的实现主要deflate()中。