gzip壓縮算法

gzip,zlib,以及圖形格式png，使用的是同一個壓縮算法deflate。我們通過對gzip源碼的分析來對deflate壓縮算法做一個詳細的說明：

第一，gzip壓縮算法基本原理的說明。

第二，gzip壓縮算法實現方法的說明。

第三，gzip實現源碼級的說明。

1. Gzip壓縮算法的原理

         gzip 對于要壓縮的文件，首先使用LZ77算法的一個變種進行壓縮，對得到的結果再使用Huffman編碼的方法（實際上gzip根據情況，選擇使用靜態Huffman編碼或者動態Huffman編碼，詳細內容在實現中說明）進行壓縮。所以明白了LZ77算法和Huffman編碼的壓縮原理，也就明白了gzip的壓縮原理。我們來對LZ77算法和Huffman編碼做一個簡單介紹。
1.1 LZ77算法簡介
        這一算法是由Jacob Ziv 和 Abraham Lempel 于 1977 年提出，所以命名為 LZ77。

1.1.1 LZ77算法的壓縮原理

        如果文件中有兩塊內容相同的話，那么只要知道前一塊的位置和大小，我們就可以確定后一塊的內容。所以我們可以用（兩者之間的距離，相同內容的長度）這樣一對信息，來替換后一塊內容。由于（兩者之間的距離，相同內容的長度）這一對信息的大小，小于被替換內容的大小，所以文件得到了壓縮。
下面我們來舉一個例子。
有一個文件的內容如下：
http://jiurl.yeah.net
http://jiurl.nease.net
其中有些部分的內容，前面已經出現過了，下面用()括起來的部分就是相同的部分。
http://jiurl.yeah.net
(http://jiurl.)nease(.net)
我們使用 (兩者之間的距離，相同內容的長度) 這樣一對信息，來替換后一塊內容。
http://jiurl.yeah.net
(22,13)nease(23,4)

其中：
(22,13)中，22為相同內容塊與當前位置之間的距離，13為相同內容的長度。
(23,4)中，23為相同內容塊與當前位置之間的距離，4為相同內容的長度。
由于（兩者之間的距離，相同內容的長度）這一對信息的大小，小于被替換內容的大小，所以文件得到了壓縮。

1.1.2 LZ77使用滑動窗口尋找匹配串
       LZ77算法使用"滑動窗口"的方法，來尋找文件中的相同部分，也就是匹配串。我們先對這里的串做一個說明，它是指一個任意字節的序列，而不僅僅是可以在文本文件中顯示出來的那些字節的序列。這里的串強調的是它在文件中的位置，它的長度隨著匹配的情況而變化。
       LZ77從文件的開始處開始，一個字節一個字節的向后進行處理。一個固定大小的窗口（在當前處理字節之前，并且緊挨著當前處理字節），隨著處理的字節不斷的向后滑動，就象在陽光下，飛機的影子滑過大地一樣。對于文件中的每個字節，用當前處理字節開始的串，和窗口中的每個串進行匹配，尋找最長的匹配串。窗口中的每個串指，窗口中每個字節開始的串。如果當前處理字節開始的串在窗口中有匹配串，就用(之間的距離，匹配長度) 這樣一對信息，來替換當前串，然后從剛才處理完的串之后的下一個字節，繼續處理。如果當前處理字節開始的串在窗口中沒有匹配串，就不做改動的輸出當前處理字節。
      處理文件中第一個字節的時候，窗口在當前處理字節之前，也就是還沒有滑到文件上，這時窗口中沒有任何內容，被處理的字節就會不做改動的輸出。隨著處理的不斷向后，窗口越來越多的滑入文件，最后整個窗口滑入文件，然后整個窗口在文件上向后滑動，直到整個文件結束。

1.1.3 使用LZ77算法進行壓縮和解壓縮
       為了在解壓縮時，可以區分“沒有匹配的字節”和“（之間的距離，匹配長度）對”，我們還需要在每個“沒有匹配的字節”或者“（之間的距離，匹配長度）對”之前，放上一位，來指明是“沒有匹配的字節”，還是“（之間的距離，匹配長度）對”。我們用0表示“沒有匹配的字節”，用1表示“（之間的距離，匹配長度）對”。
       實際中，我們將固定（之間的距離，匹配長度）對中的，“之間的距離”和“匹配長度”所使用的位數。由于我們要固定“之間的距離”所使用的位數，所以我們才使用了固定大小的窗口，比如窗口的大小為32KB，那么用15位（2^15=32K）就可以保存0-32K范圍的任何一個值。實際中，我們還將限定最大的匹配長度，這樣一來，“匹配長度”所使用的位數也就固定了。
       實際中，我們還將設定一個最小匹配長度，只有當兩個串的匹配長度大于最小匹配長度時，我們才認為是一個匹配。我們舉一個例子來說明這樣做的原因。比如，“距離”使用15位，“長度”使用8位，那么“（之間的距離，匹配長度）對”將使用23位，也就是差1位3個字節。如果匹配長度小于3個字節的話，那么用“（之間的距離，匹配長度）對”進行替換的話，不但沒有壓縮，反而會增大，所以需要一個最小匹配長度。
壓縮：
       從文件的開始到文件結束，一個字節一個字節的向后進行處理。用當前處理字節開始的串，和滑動窗口中的每個串進行匹配，尋找最長的匹配串。如果當前處理字節開始的串在窗口中有匹配串，就先輸出一個標志位，表明下面是一個(之間的距離，匹配長度) 對，然后輸出(之間的距離，匹配長度) 對，然后從剛才處理完的串之后的下一個字節，繼續處理。如果當前處理字節開始的串在窗口中沒有匹配串，就先輸出一個標志位，表明下面是一個沒有改動的字節，然后不做改動的輸出當前處理字節，然后繼續處理當前處理字節的下一個字節。
解壓縮：
        從文件開始到文件結束，每次先讀一位標志位，通過這個標志位來判斷下面是一個(之間的距離，匹配長度) 對，還是一個沒有改動的字節。如果是一個（之間的距離，匹配長度）對，就讀出固定位數的（之間的距離，匹配長度）對，然后根據對中的信息，將匹配串輸出到當前位置。如果是一個沒有改動的字節，就讀出一個字節，然后輸出這個字節。
我們可以看到，LZ77壓縮時需要做大量的匹配工作，而解壓縮時需要做的工作很少，也就是說解壓縮相對于壓縮將快的多。這對于需要進行一次壓縮，多次解壓縮的情況，是一個巨大的優點。

1.2 Huffman編碼簡介

1.2.1 Huffman編碼的壓縮原理
       我們把文件中一定位長的值看作是符號，比如把8位長的256種值，也就是字節的256種值看作是符號。我們根據這些符號在文件中出現的頻率，對這些符號重新編碼。對于出現次數非常多的，我們用較少的位來表示，對于出現次數非常少的，我們用較多的位來表示。這樣一來，文件的一些部分位數變少了，一些部分位數變多了，由于變小的部分比變大的部分多，所以整個文件的大小還是會減小，所以文件得到了壓縮。

1.2.2 Huffman編碼使用Huffman樹來產生編碼
       要進行Huffman編碼，首先要把整個文件讀一遍，在讀的過程中，統計每個符號（我們把字節的256種值看作是256種符號）的出現次數。然后根據符號的出現次數，建立Huffman樹，通過Huffman樹得到每個符號的新的編碼。對于文件中出現次數較多的符號，它的Huffman編碼的位數比較少。對于文件中出現次數較少的符號，它的Huffman編碼的位數比較多。然后把文件中的每個字節替換成他們新的編碼。
建立Huffman樹：
        把所有符號看成是一個結點，并且該結點的值為它的出現次數。進一步把這些結點看成是只有一個結點的樹。
每次從所有樹中找出值最小的兩個樹，為這兩個樹建立一個父結點，然后這兩個樹和它們的父結點組成一個新的樹，這個新的樹的值為它的兩個子樹的值的和。如此往復，直到最后所有的樹變成了一棵樹。我們就得到了一棵Huffman樹。

通過Huffman樹得到Huffman編碼：
        這棵Huffman樹，是一棵二叉樹，它的所有葉子結點就是所有的符號，它的中間結點是在產生Huffman樹的過程中不斷建立的。
我們在Huffman樹的所有父結點到它的左子結點的路徑上標上0，右子結點的路徑上標上1。
現在我們從根節點開始，到所有葉子結點的路徑，就是一個0和1的序列。我們用根結點到一個葉子結點路徑上的0和1的序列，作為這個葉子結點的Huffman編碼。 
       我們可以看到，Huffman樹的建立方法就保證了，出現次數多的符號，得到的Huffman編碼位數少，出現次數少的符號，得到的Huffman編碼位數多。
各個符號的Huffman編碼的長度不一，也就是變長編碼。對于變長編碼，可能會遇到一個問題，就是重新編碼的文件中可能會無法如區分這些編碼。
比如，a的編碼為000，b的編碼為0001，c的編碼為1，那么當遇到0001時，就不知道0001代表ac，還是代表b。出現這種問題的原因是a的編碼是b的編碼的前綴。
由于Huffman編碼為根結點到葉子結點路徑上的0和1的序列，而一個葉子結點的路徑不可能是另一個葉子結點路徑的前綴，所以一個Huffman編碼不可能為另一個Huffman編碼的前綴，這就保證了Huffman編碼是可以區分的。

1.2.3 使用Huffman編碼進行壓縮和解壓縮
     為了在解壓縮的時候，得到壓縮時所使用的Huffman樹，我們需要在壓縮文件中，保存樹的信息，也就是保存每個符號的出現次數的信息。
壓縮：
      讀文件，統計每個符號的出現次數。根據每個符號的出現次數，建立Huffman樹，得到每個符號的Huffman編碼。將每個符號的出現次數的信息保存在壓縮文件中，將文件中的每個符號替換成它的Huffman編碼，并輸出。
解壓縮：
      得到保存在壓縮文件中的，每個符號的出現次數的信息。根據每個符號的出現次數，建立Huffman樹，得到每個符號的Huffman編碼。將壓縮文件中的每個Huffman編碼替換成它對應的符號，并輸出。

2. Gzip壓縮算法的實現

2.1 尋找匹配串的實現
     為一個串尋找匹配串需要進行大量的匹配工作，而且我們還需要為很多很多個串尋找匹配串。所以 gzip 在尋找匹配串的實現中使用哈希表來提高速度。
     要達到的目標是，對于當前串，我們要在它之前的窗口中，尋找每一個匹配長度達到最小匹配的串，并找出匹配長度最長的串。
     在gzip 中，最小匹配長度為3，也就是說，兩個串，最少要前3個字節相同，才能算作匹配。為什么最小匹配長度為3，將在后面說明。
     gzip 對遇到的每一個串，首先會把它插入到一個“字典”中。這樣當以后有和它匹配的串，可以直接從“字典”中查出這個串。
     插入不是亂插，查也不是亂查。插入的時候，使用這個插入串的前三個字節，計算出插入的“字典”位置，然后把插入串的開始位置保存在這個“字典”位置中。查出的時候，使用查出串的前三個字節，計算出“字典”位置，由于插入和查出使用的是同一種計算方法，所以如果兩個串的前三個字節相同的話，計算出的“字典”位置肯定是相同的，所以就可以直接在該“字典”位置中，取出以前插入時，保存進去的那個串的開始位置。于是查出串，就找到了一個串，而這個串的前三個字節和自己的一樣（其實只是有極大的可能是一樣的，原因后面說明），所以就找到了一個匹配串。
      如果有多個串，他們的前三個字節都相同，那么他們的“字典”位置，也都是相同的，他們將被鏈成一條鏈，放在那個“字典”位置上。所以，如果一個串，查到了一個“字典”位置，也就查到了一個鏈，所有和它前三個字節相同的串，都在這個鏈上。
      也就是說，當前串之前的所有匹配串被鏈在了一個鏈上，放在某個“字典”位置上。而當前串使用它的前三個字節，進行某種計算，就可以得到這個“字典”位置（得到了“字典”位置之后，它首先也把自己鏈入到這個鏈上），也就找到了鏈有它的所有匹配串的鏈，所以要找最長的匹配，也就是遍歷這個鏈上的每一個串，看和哪個串的匹配長度最大。
尋找匹配串的實現具體的說明
我們前面所說的“字典”，是一個數組，叫做head[]（為什么叫head,后面進行說明）。
我們前面所說的“字典”位置，放在一個叫做ins_h的變量中。
我們前面所說的鏈，是在一個叫做prev[]的數組中。
插入head[ins_h]：
當前字節為第 strstart 個字節。通過第strstart,strstart+1,strstart+2,這三個字節，使用一個設計好的哈希函數算出ins_h，也就是插入的位置。然后將當前字節的位置，即strstart，保存在head[ins_h]中。
注意由 strstart,strstart+1,strstart+2,這三個字節（也就是strstart開始處的串的頭三個字節，也就是當前字節和之后的兩個字節）確定了ins_h。head[ins_h]中保存的又是strstart，也就是這個串開始的位置。

判斷是否有匹配：
當前串的前三個字節，使用哈希函數算出ins_h，這時如果head[ins_h]的值不為空的話，那么head[ins_h]中的值，便是之前保存在這里的另一個串的位置，并且這個串的前三個字節算出的ins_h，和當前串的前三個字節算出的ins_h相同。也就是說有可能有匹配。如果head[ins_h]的值為空的話，那么肯定沒有匹配。
gzip所使用的哈希函數：
gzip 所使用的哈希函數，用三個字節來計算一個ins_h，這是由于最小匹配為三個字節。
對于相同的三個字節，通過哈希函數得到的ins_h必然是相同的。
而不同的三個字節，通過哈希函數有可能得到同一個ins_h，不過這并不要緊，
當gzip發現head[ins_h]不空后，也就是說有可能有匹配串的話，會對鏈上的每一個串進行真正的串的比較。
所以一個鏈上的串，只是前三個字節用哈希函數算出的值相同，而并不一定前三個字節都是相同的。但是這樣已經很大的縮小了需要進行串比較的范圍。
我們來強調一下，前三個字節相同的串，必然在同一個鏈上。在同一個鏈上的，不一定前三個字節都相同。
不同的三個字節有可能得到同一個結果的原因是，三個字節，一共24位，有2^24種可能值。而三個字節的哈希函數的計算結果為15位，有2^15種可能值。也就是說2^24種值，與2^15種值進行對應，必然是多對一的，也就是說，必然是有多種三個字節的值，用這個哈希函數計算出的值都是相同的。
而我們使用哈希函數的理由是，實際上，我們只是在一個窗口大小的范圍內（后面將會看到）尋找匹配串，一個窗口的大小范圍是很有限的，能出現的三個字節的值組合情況也是很有限的，將遠遠小于2^24，使用合適的哈希函數是高效的。
prev[]鏈的作用，前三個字節相同的所有的串所在的鏈：
head[ins_h] 中的值，有兩個作用。一個作用，是一個前三個字節計算結果為ins_h的串的位置。另一個作用，是一個在prev[]數組中的索引，用這個索引在prev[]中，將找到前一個前三個字節計算結果為ins_h的串的位置。即prev[head[ins_h]]的值（不為空的話）為前一個前三個字節計算結果為ins_h的串的位置。
prev[]的值，也有兩個作用。一個作用，是一個前三個字節計算結果為ins_h的串的位置。另一個作用，是一個在prev[]數組中的索引，用這個索引在prev[]中，將找到前一個前三個字節計算結果為ins_h的串的位子哈。即prev[]的值（不為空的話）為前一個三個字節計算結果為ins_h的串的位置。
直到prev[]為空，表示鏈結束。
我們來舉一個例子，串，
0abcd abce,abcf_abcg
當處理到abcg的a時，由abcg的abc算出ins_h。
這時的head[ins_h]中為 11，即串"abcf abcg"的開始位置。
這時的prev[11]中為 6，即串"abce abcf abcg"的開始位置。
這時的prev[6]中為 1，即串"abcd abce abcf abcg"的開始位置。
這時的prev[1]中為 0。表示鏈結束了。
我們看到所有頭三個字母為abc的串，被鏈在了一起，從head可以一直找下去，直到找到0。
prev[]鏈的建立：
gzip在每次處理當前串的時候，首先用當前串的前三個字節計算出ins_h，然后，就要把當前的串也插入到相應的鏈中，也就是把當前的串的位置，保存到 head[ins_h] 中，而此時，head[ins_h] 中（不空的話）為前一個串的開始位置。所以這時候需要把前一個串的位置，也就是原來的head[ins_h]放入鏈中。于是把現在的head[ins_h]的值，用當前串的位置做索引，保存到 prev[] 中。然后再把 head[ins_h] 賦值為當前串的位置。
如果當前串的位置為strstart的話，那么也就是
prev[strstart] = head[ins_h];
head[ins_h] = strstart;
就這樣，每次把一個串的位置加入到鏈中，鏈就形成了。
現在我們也就知道了，前三個字節計算得到同一ins_h的所有的串被鏈在了一起，head[ins_h]為鏈頭，prev[]數組中放著的更早的串的位置。head數組和prev數組的名字，也正反應了他們的作用。
prev[]鏈的特點：
越向前（prev）與當前處理位置之間的距離越大。比如，當前處理串，算出了ins_h，而且head[ins_h]中的值不空，那么head[ins_h]就是離當前處理串距離最近的一個可能的匹配串，并且順著prev[]向前所找到的串，越來距離越遠。
匹配串中的字節開始的串的插入：
我們說過了，所有字節開始的串，都將被插入“字典”。對于確定了的匹配串，匹配串中的每個字節開始的串，仍要被插入“字典”，以便后面串可以和他們進行匹配。
注意：
對于文件中的第0字節，情況很特殊，它開始的串的位置為0。所以第0串的前三個字節計算出ins_h之后，在head[ins_h]中保存的位置為0。而對是否有可能有匹配的判斷，就是通過head[ins_h]不為0，并且head[ins_h]的值為一個串的開始位置。所以第0字節開始的串，由于其特殊性，將不會被用來匹配，不過這種情況只會出現在第0個字節，所以通常不會造成影響，即使影響，也會極小。
例如，文件內容為
jiurl jiurl
找到的匹配情況如下，[]所括部分。
jiurl j[iurl]

2.2 懶惰啊匹配（lazy match）
       對于當前字節開始的串，尋找到了最長匹配之后，gzip并不立即決定使用這個串進行替換。而是看看這個匹配長度是否滿意，如果匹配長度不滿意，而下一個字節開始的串也有匹配串的話，那么gzip就找到下一個字節開始的串的最長匹配，看看是不是比現在這個長。這叫懶惰啊匹配。如果比現在這個長的話，將不使用現在的這個匹配。如果比現在這個短的話，將確定使用現在的這個匹配。
我們來舉個例子，串
0abc bcde abcde
處理到第10字節時，也就是"abcde"的a時，找到最長匹配的情況如下，[]所括部分。
0abc bcde [abc]de
這時，再看看下一個字節，也就是第11字節的情況，也就是'abcde"的b，找到最長匹配的情況如下，[]所括部分。
0abc bcde a[bcde]
發現第二次匹配的匹配長度大，就不使用第一次的匹配串。我們也看到了如果使用第一次匹配的話，將錯過更長的匹配串。
在滿足懶惰啊匹配的前提條件下，懶惰啊匹配不限制次數，一次懶惰啊匹配發現了更長的匹配串之后，仍會再進行懶惰啊匹配，如果這次懶匹配，發現了更長的匹配串，那么上一次的懶匹配找到的匹配串就不用了。
進行懶惰啊匹配是有條件的。進行懶惰啊匹配必須滿足兩個條件，第一，下一個處理字節開始的串，要有匹配串，如果下一個處理字節開始的串沒有匹配串的話，那么就確定使用當前的匹配串，不進行懶匹配。第二，當前匹配串的匹配長度，gzip不滿意，也就是當前匹配長度小于max_lazy_match（max_lazy_match在固定的壓縮級別下，有固定的值）。
討論：
我們可以看到了做另外一次嘗試的原因。如果當前串有匹配就使用了的話，可能錯過更長匹配的機會。使用懶惰啊匹配會有所改善。
不過從我簡單的分析來看，使用懶惰啊匹配對壓縮率的改善似乎是非常有限的。

2.3 大于64KB的文件，窗口的實現
窗口的實現：
實際中，當前串（當前處理字節開始的串）只是在它之前的窗口中尋找匹配串的，也就是說只是在它之前的一定大小的范圍內尋找匹配串的。有這個限制的原因，將在后面說明。
gzip 的窗口大小為 WSIZE，32KB。
內存中有一個叫window[]的緩沖區，大小為2個窗口的大小，也就是64KB。文件的內容將被讀到這個window[]中，我們在window[]上進行LZ77部分的處理，得到結果將放在其他緩沖區中。
gzip 對window[]中的內容，從開始處開始，一個字節一個字節的向后處理。有一個指針叫strstart（其實是個索引），指向當前處理字節，當當前處理字節開始的串沒有匹配時，不做改動的輸出當前處理字節，strstart向后移動一個字節。當當前處理字節開始的串找到了匹配時，輸出（匹配長度，相隔距離）對，strstart向后移動匹配長度個字節。我們把strstart到window[]結束的這部分內容，叫做 lookahead buffer，超前查看緩沖區。這樣叫的原因是，在我們處理當前字節的時候，就需要讀出之后的字節來進行串的匹配。在一個變量lookahead中，保存著超前查看緩沖區所剩的字節數。lookahead，最開始被初始化為整個讀入內容的大小，隨著處理的進行，strstart不斷后移，超前查看緩沖區不斷減小，lookahead的值也不斷的減小。
我們需要限制查找匹配串的范圍為一個窗口的大?。ㄟ@么做的原因后面說明），也就是說，只能在當前處理字節之前的32KB的范圍內尋找匹配串。而，由于處理是在2個窗口大小，也就是64KB大小的緩沖區中進行的，所以匹配鏈上的串與當前串之間的距離是很有可能超過32KB的。那么gzip是如何來實現這個限制的呢？
gzip 通過匹配時的判斷條件來實現這個限制。當當前串計算ins_h，發現head[ins_h]值不為空時（head[ins_h]為一個串的開始位置），說明當前串有可能有匹配串，把這個值保存在 hash_head中。這時就要做一個限制范圍的判斷，strstart – hash_head <= 窗口大小，strstart-hash_head 是當前串和最近的匹配串之間的距離，（注意前面說過，鏈頭和當前串的距離最近，越向前（prev）與當前處理位置之間的距離越大），也就是說要判斷當前串和距離最近的匹配串之間的距離是否在一個窗口的范圍之內。如果不是的話，那么鏈上的其他串肯定更遠，肯定更不在一個窗口的范圍之內，就不進行匹配處理了。如果是在一個窗口的范圍之內的話，還需要在鏈上尋找最長的匹配串，在和每個串進行比較的時候，也需要判斷當前串和該串的距離是否超過一個窗口的范圍，超過的話，就不能進行匹配。
實際中，gzip為了使代碼簡單點，距離限制要比一個窗口的大小還要小一點。
對于小于64KB的文件處理過程：
初始化的時候，會首先從文件中讀64KB的內容到window[]中。
對于小于64KB的文件，整個文件都被讀入到window[]中。在window[]上進行LZ77的處理，從開始直到文件結束。

大于64KB的文件處理過程：

每處理一個字節都要判斷 lookahead < MIN_LOOKAHEAD ，也就是window中還沒有處理的字節是否還夠MIN_LOOKAHEAD ，如果不夠的話，就會導致 fill_window()，從文件中讀內容到window[]中。由于我們一次最大可能使用的超前查看緩沖區的大小為，最大匹配長度（258個字節，后面進行說明）加上最小匹配長度，也就是下一個處理字節開始的串，可以找到一個最大匹配長度的匹配，發生匹配之后，還要預讀一個最小匹配長度來計算之后的ins_h。
不管是大于64KB的文件，還是小于64KB的文件，隨著處理的進行，最終都要到文件的結束，在接近文件結束的時候，都會出現 lookahead < MIN_LOOKAHEAD ，對于這種情況，fill_window() 讀文件，就再讀不出文件內容了，于是fill_window()會設置一個標志eofile，表示文件就要結束了，之后肯定會接著遇到 lookahead < MIN_LOOKAHEAD ，不過由于設置了 eofile 標志，就不會再去試圖讀文件到window[]中了。
壓縮開始之前的初始化，會從文件中讀入64KB的內容到window[]中，窗口大小為32KB，也就是讀入2窗的內容到window[]中。我們把第一窗的內容叫做w1_32k，第二窗的內容叫做w2_32k。
壓縮不斷進行，直到 lookahead < MIN_LOOKAHEAD，也就是處理到了64KB內容的接近結束部分，也就是如果再處理，超前查看緩沖區中的內容就可能不夠了。由于 lookahead < MIN_LOOKAHEAD ，將執行 fill_window()。
fill_window() 判斷是否壓縮已經進行到了2窗內容快用完了，該把新的內容放進來了。如果是的話，
fill_window() 把第二窗的內容 w2_32k，復制到第一窗中，第一窗中的內容就被覆蓋掉了，然后對match_start,strstart之類的索引，做修正。
然后更新匹配鏈的鏈頭數組，head[]，從頭到尾過一遍，如果這個頭中保存的串的位置，在w2_32k中，就對這個串的位置做修正。
如果這個頭中保存的串的位置，在w1_32k中，就不要了，設為空，因為第一窗的內容我們已經覆蓋掉了。
然后更新prev[]數組，從頭到尾過一遍，如果某項的內容，在w2_32k中，就做修正。如果這項的內容，在w1_32k中，就不要了，設為空，因為第一窗的內容我們已經覆蓋掉了。
最后fill_window()從文件中再讀出一窗內容，也就是讀出32KB的內容，復制到第二個窗中，注意第二個窗口中原來的內容，已經被復制到了第一個窗口中。
就這樣，一窗窗的處理，直到整個文件結束。
分析：
到第二窗文件內容也快要處理完的時候，才會從文件中讀入新的內容。而這時，第一窗中的所有串，對于當前處理字節和之后的字節來說，已經超出了一個窗口的距離，當前處理字節和之后的字節不能和第一窗的串進行匹配了，也就是說第一窗的內容已經沒有用了。所有插入字典的第一窗的串也已經沒有用了。所以覆蓋第一窗的內容是合理的，將字典中第一窗的串的開始位置都設為空也是合理的。
將第二窗的內容復制到第一窗中，那么第二窗在字典中的所有索引都需要做相應的修正。
由于第二窗的內容已經復制到了第一窗中，所以我們可以將新的內容讀入到第二窗中，新的內容之前的32KB的內容，就是原來的第二窗中的內容。而這時，做過修正的字典中，仍然有原來第二窗中所有串的信息，也就是說，新的內容，可以繼續利用前面一個窗口大小的范圍之內的串，進行壓縮，這也是合理的。

2.4 其他問題1
現在來說明一下，為什么最小匹配長度為3個字節。這是由于，gzip 中，(匹配長度，相隔距離)對中，"匹配長度"的范圍為3-258，也就是256種可能值，需要8bit來保存。"相隔距離"的范圍為0-32K，需要15bit來保存。所以一個(匹配長度，相隔距離)對需要23位，差一位3個字節。如果匹配串小于3個字節的話，使用(匹配長度，相隔距離)對進行替換，不但沒有壓縮，反而還會增大。所以保存(匹配長度，相隔距離)對所需要的位數，決定了最小匹配長度至少要為3個字節。
最大匹配長度為258的原因是，綜合各種因素，決定用8位來保存匹配長度，8位的最大值為255。實際中，我們在(匹配長度，相隔距離)對中的“匹配長度”保存的是，實際匹配長度-最小匹配長度，所以255對應的實際匹配長度為258。
在進行匹配時，會對匹配長度進行判斷，保證到達最大匹配長度時，匹配就停止。也就是說，即使有兩個串的相同部分超過了最大匹配長度，也只匹配到最大匹配長度。
保存相隔距離所用的位數和窗口大小是互相決定的，綜合兩方面各種因素，確定了窗口大小，也就確定了保存相隔距離所使用的位數。

2.5 gzip 的 LZ77部分的實現要點
gzip 的 LZ77 部分的實現主要在函數 defalte() 中。
所使用的緩沖區
window[] 用來放文件中讀入的內容。
l_buf[]，d_buf[]，flag_buf[] 用來放LZ77壓縮得到的結果。
l_buf[] 中的每個字節是一個沒有匹配的字節，或者是一個匹配的對中的匹配長度-3。l_buf[]共用了inbuf[]。
d_buf[] 中的每個unsigned short，是一個匹配的對中的相隔距離。
flag_buf[] 中每位是一個標志，用來指示l_buf[]中相應字節是沒有匹配的字節，還是一個匹配的對中的匹配長度-3。
prev[]，head[] 用來存放字典信息。實際上 head 為宏定義 prev+WSIZE。
初始化過程中，調用 lm_init()。
lm_init() 中，從輸入文件中讀入2個窗口大小，也就是64KB的內容到window[]中。lookahead 中為返回的讀入字節數。使用window中的頭兩個字節，UPDATE_HASH，初始化ins_h。
deflate() 中，一個處理循環中，首先 INSERT_STRING 把當前串插入字典，INSERT_STRING 是一個宏，作用就是用哈希函數計算當前串的ins_h，然后把原來的head[ins_h]中的內容，鏈入鏈中（放到prev中），同時把原來的head[ins_h]保存在hash_head變量中，用來后面進行匹配判斷，然后把當前串的開始位置，保存在head[ins_h]中。
判斷hash_head中保存的內容不為空，說明匹配鏈上有內容。調用 longest_match () 尋找匹配鏈上的最長匹配。
hash_head中保存的內容為空，說明當前字節開始的串，在窗口中沒有匹配。
由于使用了lazy match，使得判斷的情況更復雜。
匹配串的輸出，或者是沒有匹配的字節的輸出，都是調用函數 ct_tally()。
對于匹配串，輸出之后，還需要為匹配串中的每個字節使用 INSERT_STRING，把匹配串中每個字節開始的串都插入到字典中。
ct_tally()中，把傳入的"沒有匹配的字節"或者是"匹配長度-3"放到l_buf[]中，然后為以后的Huffman編碼做統計次數的工作，如果傳入的是匹配情況，傳入的參數中會有相隔距離，把相隔距離保存在d_buf[]中。根據傳入的參數，可以判斷是哪種情況，然后設置一個變量中相應的標志位，每8個標志位，也就是夠一個字節，就保存到flag_buf[]中。還有一些判斷，我們將在后面進行說明。

2.6 分塊輸出
LZ77 壓縮的結果放在，l_buf[]，d_buf[]，flag_buf[] 中。
對于 LZ77 的壓縮結果，可能使用一塊輸出或者分成多塊輸出（LZ77壓縮一定的部分之后，就進行一次塊輸出，輸出一塊）。塊的大小不固定。
輸出的時候，會對LZ77的壓縮結果，進行Huffman編碼，最終把Huffman編碼的結果輸出到outbuf[]緩沖區中。
進行Huffman編碼，并輸出的工作，在 flush_block() 中進行。
在ct_tally()中進行判斷，如果滿足一些條件的話，當從ct_tally()中返回之后，就會對現有的LZ77的結果，進行Huffman編碼，輸出到一個塊中。
在整個文件處理結束，deflate()函數要結束的時候，會把LZ77的結果，進行Huffman編碼，輸出到一個塊中。
在ct_tally()中，每當l_buf[]中的字節數（每個字節是一個沒有匹配的字節或者一個匹配長度）增加0x1000，也就是4096的時候。將估算壓縮的情況，以判斷現在結束這個塊是否比較好，如果覺得比較好，就輸出一個塊。如果覺得不好，就先不輸出。
而當l_buf[]滿了的時候，或者d_buf[]滿了的時候，將肯定對現有的LZ77壓縮的結果，進行Huffman編碼，輸出到一個塊中。
決定輸出一塊的話，會只針對這一塊的內容，建立Huffman樹，這一塊內容將會被進行Huffman編碼壓縮，并被輸出到outbuf[]中。如果是動態Huffman編碼，樹的信息也被輸出到outbuf[]中。輸出之后，會調用init_block()，初始化一個新塊，重新初始化一些變量，包括動態樹的結點被置0，也就是說，將為新塊將來的Huffman樹重新開始統計信息。
輸出塊的大小是不固定的，首先在進行Huffman編碼之前，要輸出的內容的大小就是不固定，要看情況，進行Huffman編碼之后，就更不固定了。
塊的大小不固定，那么解壓縮的時候，如何區分塊呢。編碼樹中有一個表示塊結束的結點，EOB，在每次輸出塊的最后，輸出這個結點的編碼，所以解壓縮的時候，當遇到了這個結點就表明一個塊結束了。
每個塊最開始的2位，用來指明本塊使用的是哪種編碼方式，00表示直接存儲，01表示靜態Huffman編碼，10表示動態Huffman編碼。接下來的1位，指明本塊是否是最后一塊，0表示不是，1表示是最后一塊。
輸出一個塊，對現在字典中的內容沒有影響，下一個塊，仍將用之前形成的字典，進行匹配。

2.7 靜態Huffman編碼與動態Huffman編碼
靜態Huffman編碼就是使用gzip自己預先定義好了一套編碼進行壓縮，解壓縮的時候也使用這套編碼，這樣不需要傳遞用來生成樹的信息。
動態Huffman編碼就是使用統計好的各個符號的出現次數，建立Huffman樹，產生各個符號的Huffman編碼，用這產生的Huffman編碼進行壓縮，這樣需要傳遞生成樹的信息。
gzip 在為一塊進行Huffman編碼之前，會同時建立靜態Huffman樹，和動態Huffman樹，然后根據要輸出的內容和生成的Huffman樹，計算使用靜態Huffman樹編碼，生成的塊的大小，以及計算使用動態Huffman樹編碼，生成塊的大小。然后進行比較，使用生成塊較小的方法進行Huffman編碼。
對于靜態樹來說，不需要傳遞用來生成樹的那部分信息。動態樹需要傳遞這個信息。而當文件比較小的時候，傳遞生成樹的信息得不償失，反而會使壓縮文件變大。也就是說對于文件比較小的時候，就可能會出現使用靜態Huffman編碼比使用動態Huffman編碼，生成的塊小。

2.8 編碼的產生
deflate算法在Huffman樹的基礎上，又加入了幾條規則，我們把這樣的樹稱作deflate樹，使得只要知道所有位長上的結點的個數，就可以得到所有結點的編碼。這樣做的原因是，減少需要存放在壓縮壓縮文件中的用來生成樹的信息。要想弄明白，deflate如何生成Huffman編碼，一定要弄明白一些Huffman樹，和deflate樹的性質，下面內容是對Huffman樹和deflate樹做了些簡單研究得到的。
Huffman樹的性質
1 葉子結點為n的話，那么整顆樹的總結點為 2n-1。
簡單證明說明，先證，最小的樹，也就是只有三個結點，一個根節點，兩個葉子節點的樹符合。然后在任何符合的樹上做最小的添加得到的樹也符合。所以都符合。
2 最左邊的葉子結點的編碼為0，但是位長不一定。
deflate中增加了附加條件的huffman樹的性質
1 同樣位長的葉子結點的編碼值為連續的，右面的總比左面的大1。
2 (n+1)位長最左面的葉子結點（也就是編碼值最小的葉子結點）的值為n位長最右面的葉子結點（也就是編碼值最大的葉子結點）的值+1，然后變長一位（也就是左移1位）。
3 n位長的葉子結點，最右面的葉子結點（也就是編碼值最大的葉子結點）的值為最左面的葉子結點（也就是編碼值最小的葉子結點）的值 加上 n位長的葉子結點的個數 減 1。
4 (n+1)位長最左面的葉子結點（也就是編碼值最小的葉子結點）的值 為 n位長最左面的葉子結點（也就是編碼值最小的葉子結點）的值 加上 n位長的葉子結點的個數，然后變長一位（也就是左移1位）。
還有一些樹的性質，比如，樹的某一深度上最大可能編碼數。
從所有編碼的位長，得到所有編碼的編碼：
統計每個位長上的編碼個數放在bl_count[]中。
根據 bl_count[] 中的值，計算出每個位長上的最小編碼值，放在 next_code[] 中。
計算方法為，code = (code + bl_count[bits-1]) << 1;
理由是deflate二叉樹的性質，(n+1)位長最左面的葉子結點（也就是編碼值最小的葉子結點）的值 為 n位長最左面的葉子結點（也就是編碼值最小的葉子結點）的值 加上 n位長的葉子結點的個數，然后變長一位（也就是左移1位）。
然后按照代碼值的順序，為所有的代碼編碼。
編碼方法為，某一位長對應的next_code[n]，最開始是這個位長上最左邊的葉子結點的編碼，然后++，就是下一個該位長上下一個葉子結點的編碼，依次類推，直到把這個位長上的葉子結點編碼完。實際上的編碼為bi_reverse(next_code[])。
這樣編碼的理由是，deflate二叉樹的性質。

1. 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()中。

/* global buffers */  
  
DECLARE(uch, inbuf,  INBUFSIZ +INBUF_EXTRA);  
  
DECLARE(uch, outbuf, OUTBUFSIZ+OUTBUF_EXTRA);  
  
DECLARE(ush, d_buf,  DIST_BUFSIZE);  
  
DECLARE(uch, window, 2L*WSIZE);  
  
#ifndef MAXSEG_64K  
  
    DECLARE(ush, tab_prefix, 1L<<BITS);  
  
#else  
  
    DECLARE(ush, tab_prefix0, 1L<<(BITS-1));  
  
    DECLARE(ush, tab_prefix1, 1L<<(BITS-1));  
  
#endif

實際上定義了一些全局數組：inbuf,outbuf,d_buf,window,tab_prefix,tab_prefix0,tabfix1.1

入口程序：gzip-1.2.4/gzip.c

函數： int main (argc, argv)

      int argc;

      char **argv;

功能： 1)通過命令內容(gzip,gunzip,unzip等)，設置操作類型(壓縮或是解壓縮)。

 2)通過參數，設置一些全局變量的值，對我們而言，有用的是：ascii(表示為文本文件，可以根據本地的換行符來代替解壓后的文件中的換行符)、decompress(表示進行解壓操作)和level(轉換操作的級別-進行更快的轉換還是進行更大壓縮比的轉換，當然，這只對壓縮而言)。

 3)為輸入、輸出及窗口的緩沖分配內存。7

4)調用treat_file(argv[optind++]);對文件進行操作。

函數： local void treat_file(iname)
      char *iname;
參數： 為文件的名稱；
功能： 1)得到輸入的文件的狀態：name,size,time,mode等。
  2)創建輸出文件的名稱。
  3)當進行解壓操作時，調用 local int get_method(in) 來得到gz文件的壓縮方法。
  4)如果命令行中的參數-l，則調用do_list()顯示文件信息。
  5)調用local int create_outfile()創建輸出文件。
  6) 調用(*work)(ifd, ofd)進行壓縮、解壓縮的操作。這時的work指針被get_method()
函數置為unzip()函數(解壓時)，或是為默認的zip()函數。在解壓縮時，
這個過程是在循環中的，因為可能會包含多個文件。

函數： local int get_method(in)
      int in;        /* input file descriptor */
參數： 文件名稱
功能： 1)驗證第一第二字節是否為0x1F,0x8B。
 2)驗證第三字節是否為0x08(deflate)。
 3)設置函數指針work = unzip。(work的默認值是zip)
 4)得到做為flags的第四字節。
 5)如果設置了第1、5、6、7位，則給出錯誤提示。(編號0到7是從最低位開始)
 6)將第5到8字節中的時間值保存在全局變量time_stamp中。
 7)跳過第9字節(壓縮時采用的算法-更快或是比例更高)和第10字節(壓縮時的操作系統)。
 8)如果設置了flags的第1位，則得到當前文件的編號
 9)如果設置了flags的第2位(存在有附加的內容)，則得到附加內容的長度，并跳過這部分內容。
 10)如果設置了flags的第3位(存在有原始文件的名稱)，則得到原始文件的名稱。
 11)如果設置了flags的第4位(存在一段不用解析的內容，是給人提供可讀信息的)，跳過這部分可讀信息。
 12) 設置頭部信息的長度：header_bytes，包括了最后的CRC及文件長度部分。
返回： 函數壓縮方法(一般為“deflate”，程序中的返回值為8)

在文件gzip-1.2.4/unzip.c中：
函數： int unzip(in, out)
     int in, out;   /* input and output file descriptors */
參數：為輸入、輸出文件。
功能： 1)初始化全局變量crc。
 2)調用函數inflate()進行解碼操作。
 3)得到原來文件中保存的CRC及長度值。如果與當前計算出的值不同，則產生提示。

在文件gzip-1.2.4/inflate.c中
函數： int inflate()
說明： ulg bb;                         /* 是 bit buffer */
unsigned bk;                    /* 是bit buffer中還有多少位，即剩余的位數 */
功能： 1) 循環調用inflate_block(&e)，一塊一塊的解壓數據。
 2)若bk>-8,即bb中有完整的字節，則將此字節放回輸入中。
 3)輸出解壓得到的內容。

函數： int inflate_block(e)
int *e;                 /* last block flag */
參數：如果是1，是說明當前塊是最后一塊。
功能：

1)得到第一位，這一位說明當前塊是否為最后一塊(0，不是；1，是)并相應的設置參數。
 2)得到下兩位的值： 
0， 本塊沒有壓縮，
1， 用固定的Huffman編碼壓縮，見RFC1951的3.2.6節。
2， 用動態的Huffman編碼壓縮，見RFC1951的3.2.7節。
 3)根據前面得到的值，調用不同的函數解壓：
  inflate_stored(); 對于未壓縮的數據，調用這個函數。
  inflate_fixed(); 對于用固定的Huffman編碼壓縮的數據，調用這個函數。
  inflate_dynamic(); 對于用動態的Huffman編碼壓縮的數據，調用這個函數。

函數： int inflate_stored()
功能： 處理非壓縮的數據內容
1) 丟棄不足一字節的位。由于非壓縮的數據中，內容都是以字節為單位的，所以原來按位讀取的時候，會剩余不足一字節位內容，現在要去掉這些位。
2)  2)讀入兩字節的內容，其值是未壓縮的數據長度。再讀入兩字節的內容，其值應該是前兩字節所表示的長度的補碼，若不是，則錯誤。
3)  3)逐字節的讀入內容，并輸出到輸出文件中。
函數： int inflate_fixed()
功能： 用固定的Huffman編碼壓縮的數據
1) 為0至287的文字/length值設定編碼長度:             

Lit Value    Bits        Codes
                   ---------    ----        -----
                     0 - 143     8          00110000 through
                                            10111111
                   144 - 255     9          110010000 through
                                            111111111
                   256 - 279     7          0000000 through
                                            0010111
                   280 - 287     8          11000000 through
                                            11000111

2) 調用huft_build()建造文字/length值的Huffman樹
3) 設置所有distance值(從0至29)的編碼長度為5。
4) 調用huft_build()建造distance值的Huffman樹
5) 調用函數inflate_codes()進行解碼。

函數： int inflate_dynamic()
功能： 用動態的Huffman編碼壓縮的數據
1) 讀入5位的值HLIT，算出nl = 257+HLIT。這是需要編碼的最大值。
2) 讀入5位的值HDIST，算出nd = 1+HDIST。這是distance的最大值。
3) 讀入4位的值HCLEN，算出nb = 4+HCLEN。說明有多少種編碼長度。
4) 再讀入3*nb位，每三位的值表示用多少位來表示所對應的編碼長度。
5) 調用huft_build()建造編碼長度的Huffman樹。
6) 利用這個Huffman樹，對接下來的若干位解碼出nl+nd個值，這些值依次是0~nl-1的編碼長度(對于文字/length平說)，及0~nd-1的編碼長度(對于distance來說)。
7) 利用上面解碼出的兩組長度值，兩次調用huft_build()函數，建造兩個Huffman樹 (一個是為文字/length，另一個是為distance)。
8) 調用函數inflate_codes()進行解碼。

函數： int inflate_codes(tl, td, bl, bd)
struct huft *tl, *td;　/* literal/length and distance decoder tables */
int bl, bd;            /* number of bits decoded by tl[] and td[] */
參數： tl,td是進行Huffman編碼解碼時用到的結構體，由于length和distance用不同的編碼方式，所以要有兩個指針進行解碼。
 在兩種編碼中，用struct huft結構編碼時，分別以bl,bd位進行編碼。
功能： 用兩個以經做好的鏈表來進行解碼。
1） 解碼一個值X，如果0<=X<=255，則X是一個字符，輸出，循環1）。
2） 如果X==255，則說明塊結束，函數返回。
3） X>255，則說明讀到的是一個length值，根據這個值，及其后的附加位，得到真實的length值。
4） 繼續讀入一個值，這個值是distance的標志值，根據這個值及其后的附加位得到真實的distance。
5） 在已經輸出的串中，向前查找distance個字節，拷貝length個字節到輸出串的末尾。
6） 循環1）
函數： int huft_build()　和函數int huft_free()比較獨立，可以直接引用，不再分析。
功能： int huft_build() ：建立Huffman解碼鏈表。
int huft_free() ：清除鏈表。

在文件gzip-1.2.4/zip.c中：
函數： int zip(in, out)
     int in, out;   /* input and output file descriptors */
參數：為輸入、輸出文件。
功能：
1） 向輸出寫入三字節：0x1F 0x8B 0x08。
2） 向輸出寫入一個含有8個標志位的字節。
3） 向輸出寫入4字節的系統時間。
4） 初始化CRC的值。
5） 調用bi_init(out)初始化讀入位串的程序。
6） 調用ct_init()進行分配內存，初始化變量表，保存原始文件信息的操作。
7） 調用lm_init()為新文件初始化“最長匹配”的程序。
8） 再向輸出寫入2字節，一個為額外的標志，一個為系統類型。
9） 如果需要，則保存原始文件名稱。
10) 保存頭部信息的長度。
11) 調用函數deflate()壓縮。
12) 寫入4字節的CRC值。
13)  寫入4字節的原始內容長度值。
14）修改前面保存的頭部信息長度的值。

在文件gzip-1.2.4/deflate.c中：
函數： ulg deflate()
功能： 壓縮數據。此函數通過一些復雜的算法來進行壓縮操作，可以直接引用。
1) 如果需要快速壓縮，則調用函數deflate_fast()，然后返回。
2) 將當前內容插入到哈希表中，并查找最長匹配。
3) 若找到匹配內容，則輸出<length,distence>對的編碼，否則輸出字符編碼

轉自：http://blog.csdn.net/hguisu/article/details/7795435