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

*比對串由幾個字元構成？

對于字元串

“As mentioned above,there are many kinds of wireless systems other than cellular.”，

先來看第一個問題。Deflate壓縮中有規定，先行緩沖區中的字元串最少要由3個連續的字元構成。放到這個例子裡，字元串“re”是不行的，至少得是“re （這裡有空格）”。也就是說，當先行緩沖區中的字元串至少由3個連續的字元組成并且在查找緩沖區中找到了比對，此時先行緩沖區中的這個字元串才能用“長度+距離”對兒替換。長度距離對兒是個二進制組，要由兩個數組成。如果對單個字元用長度距離對兒替換，那還不如不替換；如果對兩個連續字元用長度距離對兒替換，那是否替換又有什麼關系，反正替換前後都要用兩個數（字元其實也是個數）。是以，能夠替換的前提就是字元串至少要由3個位于先行緩沖區中的連續字元組成，而且還必須以先行緩沖區中第一個位元組為開始。

壓縮過程是逐位元組依次進行的，字元串的組成過程舉例如下，有字元串“abcdefghijklm”。當先行緩沖區第一個字元為“a”時，以它為起始，由連續的三個字元組成的字元串就是“abc”；接着當先行緩沖區第一個字元為“b”時，對應的字元串是“bcd”；接着當先行緩沖區第一個字元為“c”時，對應的字元串就是“cde”……當先行緩沖區的第一個字元是“k”時，對應的字元串就是“klm”；以上這些字元串都有資格在查找緩沖區中尋找比對串。當先行緩沖區第一個位元組走到“l”的位置時，由于連續字元數不夠三個，是以沒資格在查找緩沖區中尋找比對串，“m”就更别提了。當然，有的字元可能沒有機會當先行緩沖區的第一個字元，因為它所在的字元串很可能已經被長度距離對兒替換掉了。