|
当某处的当前串的三个字节确定了一个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串进行匹配，然后看哪种
匹配效果好。
例子 ...
|
正在阅读：Gzip Zlib PNG 压缩算法,源码详解Gzip Zlib PNG 压缩算法,源码详解
2004-03-03 10:03
出处：CSDN
责任编辑：linjixiong
键盘也能翻页，试试“← →”键
