gzip,zlib,以及圖形格式png，使用的是同一個壓縮算法deflate。我們通過對gzip源碼的分析來對deflate壓縮算法做一個詳細的說明。我閱讀的gzip版本為
gzip-1.2.4。我們對算法做三種程度的說明。第一種程度，對gzip所使用壓縮算法基本原理的說明。第二種程度，對gzip壓縮算法實現方法的說明。第三種程度，對gzip實現源碼級的說明。
如果你有時間的話，我建議你先不要看下面的內容，自己嘗試通過讀gzip源碼，來了解它的壓縮解壓縮是如何實現的，這將會是一個非常有趣的智力游戲，千萬不要錯過。當一個又一個的謎被解開時，那感覺就像唐伯虎同志所說的，“慷慨然諾杯酒中”。（小唐的詩，除了另一個倒霉蛋曹雪芹外，好像不太被人提。）
1 gzip所使用壓縮算法的基本原理
gzip 對於要壓縮的文件，首先使用lz77算法進行壓縮，對得到的結果再使用huffman編碼的方法進行壓縮。所以我們分別對lz77和huffman編碼的原理進行說明。
1.1 ... 1.2 ...
2 gzip壓縮算法實現方法
2.1 LZ77算法的gzip實現
首先，gzip 從要壓縮的文件中讀入64KB的內容到一個叫window的緩沖區中。為了簡單起見，我們以32KB以下文件的壓縮為例做說明。對於我們這裡使用32KB以下文件，gzip將整個文件讀入到window緩沖區中。然後使用一個叫strstart的變量在window數組中，從0開始一直向後移動。strstart在每一個位置上，都在它之前的區域中，尋找和當前strstart開始的串的頭3個字節匹配的串，並試圖從這些匹配串中找到最長的匹配串。
如果當前的strstart開始的串，可以找到最少為3個字節的匹配串的話，當前的strstart開始的匹配長度那麼長的串，將會被一個<匹配長度,到匹配串開頭的距離>對替換。
如果當前的strstart開始的串，找不到任何的最少為3個字節的匹配串的話，那麼當前strstart的所在字節將不作改動。
為了區分是一個<匹配長度,到匹配串開頭的距離>對，還是一個沒有被改動的字節，還需要為每一個沒有被改動的字節或者<匹配長度,到匹配串開頭的距離>對，另外再占用一
位，來進行區分。這位如果為1，表示是一個<匹配長度,到匹配串開頭的距離>對，這位如果為0，表示是一個沒有被改動的字節。
現在來說明一下，為什麼最小匹配為3個字節。這是由於，gzip 中，<匹配長度,到匹配串開頭的距離>對中，"匹配長度"的范圍為3-258，也就是256種可能值，需要8bit來保存。"到匹配串開頭的距離"的范圍為0-32K，需要15bit來保存。所以一個<匹配長度,到匹配串開頭的距離>對需要23位，差一位3個字節。如果匹配串小於3個字節的話，使用<匹配長度,到匹配串開頭的距離>對進行替換，不但沒有壓縮，反而還會增大。所以保存<匹配長度,到匹配串開頭的距離>對所需要的位數，決定了最小匹配長度至少要為3個字節。
下面我們就來介紹gzip如何實現尋找當前strstart開始的串的最長匹配串。
如果每次為當前串尋找匹配串時，都要和之前的每個串的至少3個字節進行比較的話，那麼比較量將是非常非常大的。為了提高比較速度，gzip使用了哈希表。這是gzip實現LZ77的關鍵。這個哈希表是一個叫head的數組（後面我們將看到為什麼這個緩沖區叫head）。gzip對windows中的每個串，使用串的頭三個字節，也就是strstart,strstart+1,strstart+2，用一個設計好的哈希函數來進行計算，得到一個插入位置ins_h。也就是用串的頭三個字節來確定一個插入位置。然後把串的位置，也就是
strstart的值，保存在head數組的第ins_h項中。我們馬上就可以看到為什麼要這樣做。head數組在沒有插入任何值時，全部為0。
當某處的當前串的三個字節確定了一個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串進行匹配，然後看哪種
匹配效果好。
例子 ...
從這個例子中我們就看到了做另外一次嘗試的原因。如果碰到的一個匹配就使用了的話，可能錯過更長匹配的機會。現在做兩次會有所改善。
...
2.2 問題討論
我在這裡對gzip壓縮算法做出了一些說明，是希望可以和對gzip或者壓縮解壓縮感興趣的朋友進行交流。
我對gzip的了解要比這裡說的更多一些，也有更多的例子。如果哪位朋友願意對下面的問題進行研究，以及其他壓縮解壓縮的問題進行研究，來這裡http://jiurl.cosoft.org.cn/forum/
和我交流的話，我也願意就我知道的內容進行更多的說明。
下面是幾個問題
這種匹配算法，即用3個字節(最小匹配)來計算一個整數，是否比用串比較來得高效，高效到什麼程度。
哈希函數的討論。不同的三個字節，是否可能得到同一個ins_h。ins_h和計算它的三個字節的關系。
幾次延遲嘗試比較好？
用延遲，兩次嘗試是否對壓縮率的改善是非常有限的？
影響lz77壓縮率的因素。
壓縮的極限。
2.3 ...
3 gzip源碼分析
main() 中調用函數 treat_file() 。
treat_file() 中打開文件，調用函數 zip()。注意這裡的 work 的用法，這是一個函數指針。
zip() 中輸出gzip文件格式的頭，調用 bi_init，ct_init，lm_init，
其中在lm_init中將 head 初始化清0。初始化strstart為0。從文件中讀入64KB的內容到window緩沖區中。
由於計算strstart=0時的ins_h，需要0,1,2這三個字節和哈希函數發生關系，所以在lm_init中，預讀0,1兩個字節，並和哈希函數發生關系。
然後lm_init調用 deflate()。
deflate() gzip的LZ77的實現主要deflate()中。
...
