*如何高效查找匹配串？
前文我们提到LZ77是一种字典算法，其实这里的查找匹配串过程就是查字典的过程，只不过这个字典是动态构建的。Deflate算法中LZ77过程包括构建字典和查字典两道工序，这两道工序是同时进行的，边构建字典边查字典。所以，要搞清查字典的过程，就必须将构建字典的过程搞清。所谓构建字典，就是将不同的字符串插入到这个字典中。那么查字典就是从该字典的已有字符串中查找匹配串而已。
在压缩中，“字典”是一个实实在在的东西，其实体由一整块连续的内存构成。该内存大小为64KB，分成两部分，每部分大小为一个WSIZE，如下图所示，
这两个部分分别由两个不同的指针指向，prev和head，两块内存连续，但是互不干扰。指针head = prev + WSIZE，prev指向该字典整个内存的起始位置。既然内存是连续的，所以prev和head可以看作两个数组，即prev[]和head[]。
prev[]和head[]的大小都是一个WSIZE（这个大小不是指占用多大内存，而是指有多少个数组元素），这不是偶然。一个字符串必须至少由三个连续字符组成，此时该字符串才有资格在查找缓冲区中寻找匹配串。压缩使用哈希表来提高查找速度！压缩就是利用这三个（就三个，多一个不多，少一个不少）连续字符来计算哈希值，具体的哈希函数我们在源码中会看到。这个哈希值就是head[]数组的索引。这三个字符不同，以及它们的排列顺序不同，则计算出的的哈希值就不同，但是，这三个字符（每个字符为1BYTE，三个字符正好24bits，其实这个不用解释吧）组成的字符串共有2^24种，而哈希值的范围是[0, 32767]（注意，这是闭区间，根据源码中的哈希函数得到该区间），共有32768即一个WSIZE个哈希值（正好满足head[]的全部索引），所以不能做到每个哈希值对应一种字符串的情况，势必出现冲突。数组prev[]就是用来解决冲突的，而且该数组还用来得到最长匹配。
有了相应的内存作为字典的实体，现在我们来分析构建字典的过程。所谓构建字典，其实就是把字符串插到字典中而已。压缩中有资格在查找缓冲区搜寻匹配串的字符串至少要由三个连续字符构成，上文提到head[]数组的索引是个哈希值，而这个哈希值就是由这三个连续字符计算出来的。压缩过程（更准确是说是LZ77过程）逐字节进行，每处理一个字节，查找缓冲区扩大一个字节（如果已经达到32KB，那就沿着先行缓冲区的方向滑动一个字节，或者说是吞噬先行缓冲区的一个字节）而先行缓冲区减小一个字节，这个过程中先行缓冲区的第一个字节也会跟着改变。每次先行缓冲区的第一个字节改变的时候（也就是说之前的先行缓冲区第一个字节此时已经被查找缓冲区吞噬），就要用“由当前的先行缓冲区第一个字节开始，在先行缓冲区中连续的三个字节（字符）”组成的字符串来计算哈希值。该哈希值其实就标明了这个由三个连续字符组成的字符串。我们用ins_h变量来表示计算出来的哈希值，而该哈希值是数组head[]的索引，所以，我们用head[ins_h]来记录该字符串的出现位置，这就是把字符串插入字典的过程。这个字符串就是那个“由当前的先行缓冲区第一个字节开始，在先行缓冲区中连续的三个字节（字符）”组成的字符串，该字符串的出现位置就是这个字符串第一个字符（也就是当前先行缓冲区第一个字节）在当前window中的位置（i.e.window中第几个字节）。例如，有字符串
“abcdefg”，
假设当前先行缓冲区第一个字符是c，那么哈希值就要用字符串“cde”来计算，计算结果记为ins_h1，字符c在“abcdefg”中的位置是2（从0开始，a的位置是0），所以将字符串“cde”插入字典的过程就是伪代码“head[ins_h1] = 2”；处理完字符c（除了插入字典的过程，当然还有其他过程，但是这里用不着，就不提了），查找缓冲区将c吞噬，先行缓冲区减小一个字节，先行缓冲区第一个字节现在就是d。此时由d组成的字符串就是“def”，用这三个字节计算哈希值，记为ins_h2，字符d在“abcdefg”中的位置是3，所以将字符串“def”插入字典的过程就是伪代码“head[ins_h2] = 3”。此时有个问题，如果ins_h1和ins_h2恰好相等，也就是哈希冲突了，怎么办？别着急，这个问题在“如何找到最长匹配”中会给出答案。
上面我们给出了将字符串插入字典的过程，没错，字典中的这个字符串有且只有三个字符，多一个不多，少一个不少！那问题来了，不是说找最长匹配吗，把这么短的字符串插到字典里，还怎么找最长匹配？上面我们已经了解了将字符串插入字典的过程，那我们现在就来分析从字典中查字符串的过程。
明白了插入过程，查字典的过程就简单了不少。还是上面的例子，还是上面的流程，字符串规则也都完全相同（从先行缓冲区第一个字符开始，连续的三个字符组成），只不过在计算完哈希值之后，不是插入字典，而是查字典。将计算完的哈希值记为ins_h，ins_h是数组head[]的索引，同时也标示了这个由三个连续字符组成的字符串，相同的字符串计算出来的哈希值就是相同的（冲突也不怕，在“如何找到最长匹配”中会详细分析各种情况）。所以，既然这次计算出来的哈希值是ins_h，那么如果head[ins_h]不是空的，就说明找到了匹配串，而这个匹配串的出现位置就是head[ins_h]；如果head[ins_h]是空的，就说明没有匹配串，而且连冲突都没有，这就是查字典的过程。例如，有字符串
“mnoabcabcdefgh”，
假设第一个“abc”字符串已经插入到字典中，哈希值为ins_h1，位置为head[ins_h1]（该值为3），并且现在先行缓冲区第一个字节是第二个“abc”的“a”，那么现在计算第二个“abc”的哈希值，记为ins_h2。显然这两个字符串是完全相同的，因此ins_h1与ins_h2相等，那么head[ins_h2]的值就是head[ins_h1]的值，即3，head[ins_h2]不为空，所以找到了匹配串，而且把匹配串的出现位置也找到了，这等于知道了LZ77长度距离对儿之中的“距离”！！！
再来看这个例子，有字符串
“mnoabczxyuvabczxydefgh”
假设第一个“abc”字符串已经插入到字典中，哈希值为ins_h1，位置为head[ins_h1]（该值为3），并且现在先行缓冲区第一个字节是第二个“abc”的“a”，那么现在计算第二个“abc”的哈希值，记为ins_h2。从上面那个例子可知，此时第二个字符串“abc”可以找到匹配，就是第一个“abc”，而且连出现位置也可以知道。但是，此时针对第二个“abc”字符串的查找过程并没有结束，压缩算法会继续进行“尝试匹配”。第二个“abc”字符串沿着先行缓冲区方向的第一个字节，也就是该字符串的右面第一个字节，是字符“z”，而第一个“abc”右面第一个字节也是字符“z”，继续往这两个字符串的右面看，发现从这两个字符串开始往右，一口气有三个连续字符都是一样的（这里必须提一句，再往右，就发现不同了，一个是d而另一个是u，所以只能截止到y，不能再往右了），都是字符串“zxy”！所以，第二个字符串“abc”所找到的匹配串不仅仅是“abc”，更是字符串“abczxy”，因此这次的匹配结果就是“abczxy”而不是“abc”！这次的匹配长度就是6（因为匹配了六个字符）。第一个“abc”中a的位置是3，通过head[ins_h1 or ins_h2]可以得到，第二个“abc”中a的位置是已知的（为什么已知，因为逐字节处理的时候会一直记着这是window中第几个字符，对应源码中的变量strstart），即11，这两个位置的差值，即（8 = 11 – 3），8就是这两个字符串之间的距离。此时，LZ77的长度距离对儿就获得了，匹配长度是6，距离是8，将字符串“abczxy”用长度距离对儿替换后，整个字符串就是
“mnoabczxyuv(6,8)defgh”,
这就是LZ77之后的结果。这个例子比上一个例子更详细，而且更加“接近”实际的LZ77过程，随着分析的深入，我们最终会看到实际的LZ77过程。
前面我们提到为什么只把仅有三个字符的字符串插入字典的问题，现在通过上面两个例子，我想大家应该有所体会。与其说将字符串插入字典，不如将其理解为将字符串的起始位置插入到字典中，哈希只是得到一次初步匹配，用于找到符合这种初步匹配的位置，利用这个位置找到更长的匹配才是目的。
到此，字典的构建以及基本查找过程就分析完了，我们已经看到了LZ77原理的骨架，下面的分析，会为LZ77添上肉和血。
![Android 关于图片的压缩[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)