我們對(duì)算法做三種程度的說(shuō)明。第一種程度，對(duì)gzip所使用壓縮算法基本原理的說(shuō)明。第二種程度，對(duì)gzip壓縮算法實(shí)現(xiàn)方法的說(shuō) 明。第三種程度，對(duì)gzip實(shí)現(xiàn)源碼級(jí)的說(shuō)明。
　
　　1 gzip所使用壓縮算法的基本原理
　　
　　gzip 對(duì)于要壓縮的文件，首先使用lz77算法進(jìn)行壓縮，對(duì)得到的結(jié)果再使用huffman編碼的方法進(jìn)行壓縮。所以我們分別對(duì)lz77和huffman編碼的原理進(jìn)行說(shuō)明。
　　

　　
　　2 gzip壓縮算法實(shí)現(xiàn)方法
　　
　　2.1 LZ77算法的gzip實(shí)現(xiàn)
　　
　　首先，gzip 從要壓縮的文件中讀入64KB的內(nèi)容到一個(gè)叫window的緩沖區(qū)中。為了簡(jiǎn)單起見(jiàn)，我們以32KB以下文件的壓縮為例做說(shuō)明。對(duì)于我們這里使用32KB 以下文件，gzip將整個(gè)文件讀入到window緩沖區(qū)中。然后使用一個(gè)叫strstart的變量在window數(shù)組中，從0開始一直向后移動(dòng)。 strstart在每一個(gè)位置上，都在它之前的區(qū)域中，尋找和當(dāng)前strstart開始的串的頭3個(gè)字節(jié)匹配的串，并試圖從這些匹配串中找到最長(zhǎng)的匹配 串。
　　
　　如果當(dāng)前的strstart開始的串，可以找到最少為3個(gè)字節(jié)的匹配串的話，當(dāng)前的strstart開始的匹配長(zhǎng)度那么長(zhǎng)的串，將會(huì)被一個(gè)<匹配長(zhǎng)度,到匹配串開頭的距離>對(duì)替換。
　　
　　如果當(dāng)前的strstart開始的串，找不到任何的最少為3個(gè)字節(jié)的匹配串的話，那么當(dāng)前strstart的所在字節(jié)將不作改動(dòng)。
　　
　　為了區(qū)分是一個(gè)<匹配長(zhǎng)度,到匹配串開頭的距離>對(duì)，還是一個(gè)沒(méi)有被改動(dòng)的字節(jié)，還需要為每一個(gè)沒(méi)有被改動(dòng)的字節(jié)或者<匹配長(zhǎng)度,到匹配串開頭的距離>對(duì)，另外再占用一
　　位，來(lái)進(jìn)行區(qū)分。這位如果為1，表示是一個(gè)<匹配長(zhǎng)度,到匹配串開頭的距離>對(duì)，這位如果為0，表示是一個(gè)沒(méi)有被改動(dòng)的字節(jié)。
　　
　　現(xiàn)在來(lái)說(shuō)明一下，為什么最小匹配為3個(gè)字節(jié)。這是由于，gzip 中，<匹配長(zhǎng)度,到匹配串開頭的距離>對(duì)中，"匹配長(zhǎng)度"的范圍為3-258，也就是256種可能值，需要8bit來(lái)保存。"到匹配串開頭的 距離"的范圍為0-32K，需要15bit來(lái)保存。所以一個(gè)<匹配長(zhǎng)度,到匹配串開頭的距離>對(duì)需要23位，差一位3個(gè)字節(jié)。如果匹配串小于 3個(gè)字節(jié)的話，使用<匹配長(zhǎng)度,到匹配串開頭的距離>對(duì)進(jìn)行替換，不但沒(méi)有壓縮，反而還會(huì)增大。所以保存<匹配長(zhǎng)度,到匹配串開頭的距 離>對(duì)所需要的位數(shù)，決定了最小匹配長(zhǎng)度至少要為3個(gè)字節(jié)。
　　
　　下面我們就來(lái)介紹gzip如何實(shí)現(xiàn)尋找當(dāng)前strstart開始的串的最長(zhǎng)匹配串。
　　
　　如果每次為當(dāng)前串尋找匹配串時(shí)，都要和之前的每個(gè)串的至少3個(gè)字節(jié)進(jìn)行比較的話，那么比較量將是非常非常大的。為了提高比較速度，gzip使用了哈希 表。這是gzip實(shí)現(xiàn)LZ77的關(guān)鍵。這個(gè)哈希表是一個(gè)叫head的數(shù)組（后面我們將看到為什么這個(gè)緩沖區(qū)叫head）。gzip對(duì)windows中的每 個(gè)串，使用串的頭三個(gè)字節(jié)，也就是strstart,strstart+1,strstart+2，用一個(gè)設(shè)計(jì)好的哈希函數(shù)來(lái)進(jìn)行計(jì)算，得到一個(gè)插入位置 ins_h。也就是用串的頭三個(gè)字節(jié)來(lái)確定一個(gè)插入位置。然后把串的位置，也就是 strstart的值，保存在head數(shù)組的第ins_h項(xiàng)中。我們馬上就可以看到為什么要這樣做。head數(shù)組在沒(méi)有插入任何值時(shí)，全部為0。

當(dāng)某處的當(dāng)前串的三個(gè)字節(jié)確定了一個(gè)ins_h，并把當(dāng)時(shí)當(dāng)前串的位置也就是當(dāng)時(shí)的strstart保存在了head[ins_h]中。之后另一處，當(dāng)另 一處的當(dāng)前串的頭三個(gè)字節(jié)，再為那三個(gè)字節(jié)時(shí)，再使用那個(gè)哈希函數(shù)來(lái)計(jì)算，由于是同樣的三個(gè)字節(jié)，同樣的哈希函數(shù)，得到的ins_h必然和前面得到的 ins_h是相同的。于是就會(huì)發(fā)現(xiàn)head[ins_h]不為0。這就說(shuō)明了，有一個(gè)頭三個(gè)字節(jié)和自己相同的串把自己的位置保存在了這里，現(xiàn)在head [ins_h]中保存的值，也就是那個(gè)串的開始位置，我們就可以找到那個(gè)串，那個(gè)串至少前3個(gè)字節(jié)和當(dāng)前串的前3個(gè)字節(jié)相同（稍后我們就可以看到這種說(shuō)法 不準(zhǔn)確，這里是為了說(shuō)明方便），我們可以找到那個(gè)串，做進(jìn)一步比較，看到底能有多長(zhǎng)的匹配。
　　
　　我們現(xiàn)在來(lái)說(shuō)明一下，相同的三個(gè)字節(jié)，通過(guò)哈希函數(shù)得到的ins_h必然是相同的。而不同的三個(gè)字節(jié)，通過(guò)哈希函數(shù)有沒(méi)有可能得到同一個(gè)ins_h， 我沒(méi)有對(duì)這個(gè)哈希函數(shù)做研究，并不清楚，不過(guò)一般的哈希函數(shù)都是這樣的，所以極大可能這里的也會(huì)是這種情況，即不同的三個(gè)字節(jié)，通過(guò)哈希函數(shù)有可能得到同 一個(gè)ins_h，不過(guò)這并不要緊，我們發(fā)現(xiàn)有可能是匹配串之后，還會(huì)進(jìn)行串的比較。
　　
　　一個(gè)文件中，可能有很多個(gè)串的頭三個(gè)字節(jié)都是相同的，也就是說(shuō)他們計(jì)算得到的ins_h都是相同的，如何能保證找到他們中的每一個(gè)串呢？gzip使用 一個(gè)鏈把他們鏈在一起。gzip每次把當(dāng)前串的位置插入head的當(dāng)前串頭三個(gè)字節(jié)算出的ins_h處時(shí)，都會(huì)首先把原來(lái)的head[ins_h]的值， 保存到一個(gè)叫prev的數(shù)組中，保存的位置就在現(xiàn)在的strstart處。這樣當(dāng)以后某處的當(dāng)前串計(jì)算出ins_h，發(fā)現(xiàn)head[ins_h]不空時(shí)， 就可以到prev[ head[ins_h] ]中找到更前一個(gè)的頭三個(gè)字節(jié)相同的串的位置。對(duì)此我們舉例說(shuō)明。
　　
　　例，串
　　0abcdabceabcfabcg
　　^^^^^^^^^^^^^^^^^
　　01234567890123456
　　
　　整個(gè)串被壓縮程序處理之后。
　　
　　由abc算出ins_h。
　　這時(shí)的head[ins_h]中為 13,即"abcg"的開始位置。
　　這時(shí)prev[13]中為 9，即"abcfabcg"的開始位置。
　　這時(shí)prev[9]中為 5，即"abceabcfabcg"的開始位置。
　　這時(shí)prev[5]中為 1，即"abcdabceabcfabcg"的開始位置。
　　這時(shí)prev[1]中為 0。
　　
　　我們看到所有頭三個(gè)字母為abc的串，被鏈在了一起，從head可以一直找下去，直到找到0。
　　
　　現(xiàn)在我們也就知道了，三個(gè)字節(jié)通過(guò)哈希函數(shù)計(jì)算得到同一ins_h的所有的串被鏈在了一起，head[ins_h]為鏈頭，prev數(shù)組中放著的更早的串。這也就是head和prev名稱的由
　　來(lái)。
　　
　　gzip尋找匹配串的另外一個(gè)值得注意的實(shí)現(xiàn)是，延遲匹配。會(huì)進(jìn)行兩次嘗試。比如當(dāng)前串為str,那么str發(fā)生匹配以后，并不發(fā)生壓縮，還會(huì)對(duì)str+1串進(jìn)行匹配，然后看哪種
　　匹配效果好。
　　
　　例子 ...
　從這個(gè)例子中我們就看到了做另外一次嘗試的原因。如果碰到的一個(gè)匹配就使用了的話，可能錯(cuò)過(guò)更長(zhǎng)匹配的機(jī)會(huì)。現(xiàn)在做兩次會(huì)有所改善。
　　
　　...
　　
　　2.2 問(wèn)題討論
　　
　　我在這里對(duì)gzip壓縮算法做出了一些說(shuō)明，是希望可以和對(duì)gzip或者壓縮解壓縮感興趣的朋友進(jìn)行交流。
　　我對(duì)gzip的了解要比這里說(shuō)的更多一些，也有更多的例子。如果哪位朋友愿意對(duì)下面的問(wèn)題進(jìn)行研究，以及其他壓縮解壓縮的問(wèn)題進(jìn)行研究，來(lái)這里 http://jiurl.cosoft.org.cn/forum/ 和我交流的話，我也愿意就我知道的內(nèi)容進(jìn)行更多的說(shuō)明。
　　
　　下面是幾個(gè)問(wèn)題
　　
　　這種匹配算法，即用3個(gè)字節(jié)(最小匹配)來(lái)計(jì)算一個(gè)整數(shù)，是否比用串比較來(lái)得高效，高效到什么程度。
　　
　　哈希函數(shù)的討論。不同的三個(gè)字節(jié)，是否可能得到同一個(gè)ins_h。ins_h和計(jì)算它的三個(gè)字節(jié)的關(guān)系。
　　
　　幾次延遲嘗試比較好？
　　
　　用延遲，兩次嘗試是否對(duì)壓縮率的改善是非常有限的？
　　
　　影響lz77壓縮率的因素。
　　
　　壓縮的極限。
　　　　
　　2.3 ...
　　
　　3 gzip源碼分析
　　
　　main() 中調(diào)用函數(shù) treat_file() 。
　　treat_file() 中打開文件，調(diào)用函數(shù) zip()。注意這里的 work 的用法，這是一個(gè)函數(shù)指針。
　　zip() 中輸出gzip文件格式的頭，調(diào)用 bi_init，ct_init，lm_init，
　　其中在lm_init中將 head 初始化清0。初始化strstart為0。從文件中讀入64KB的內(nèi)容到window緩沖區(qū)中。
　　由于計(jì)算strstart=0時(shí)的ins_h，需要0,1,2這三個(gè)字節(jié)和哈希函數(shù)發(fā)生關(guān)系，所以在lm_init中，預(yù)讀0,1兩個(gè)字節(jié)，并和哈希函數(shù)發(fā)生關(guān)系。
　　
　　然后lm_init調(diào)用 deflate()。
　　deflate() gzip的LZ77的實(shí)現(xiàn)主要deflate()中。
　　...