GZIP壓縮原理分析（22）——第五章 Deflate算法詳解（五13） 動态哈夫曼編碼分析（02） LZ77過程（01）

按照之前所述的LZ77規則将這句話壓縮（回顧，這裡使用的LZ77和原始LZ77有一定差别，隻用“長度+距離”二進制組，我們稱其為“長度距離對兒”）。比對串的查找是在查找緩沖區中進行的，如下圖所示，我們分析比對串查找過程，

目前先行緩沖區第一個位元組就是字元“r”，要做的就是找到以“r”為起始字元，在先行緩沖區中由連續字元組成的字元串在查找緩沖區中的最長比對。更通俗的說就是，上圖中藍色部分從最左到右的連續的字元能夠組成的所有字元串（必須以最左面的“r”打頭），要在上圖中的綠色部分找到完全相同的字元串，而且這個字元串必須是在綠色部分中能夠找到的最長的字元串。例如，“re”在綠色部分中有，“re （這裡有個空格）”在綠色部分中也有，但是後者比前者多一個字元，是以就選後者；目前先行緩沖區第一個位元組是“r”，是以就不能用藍色部分的字元串“many kinds”來找綠色部分的比對。

現在擺在我們面前的問題有四個：第一，從“r”開始，先行緩沖區中的字元串由幾個字元構成？有什麼規定嗎？還是說隻要能找到比對，不管幾個字元都行？第二，如何高效的在查找緩沖區中找到比對串？第三，如何找到最長比對？第四，找不到比對怎麼辦？