*如何高效查找比對串？
前文我們提到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=)