1 gzip 所使用壓縮算法的基本原理
gzip 對于要壓縮的文件，首先使用LZ77算法的一個變種進行壓縮，對得到的結果再使用Huffman編碼的方法（實際上gzip根據情況，選擇使用靜態(tài)Huffman編碼或者動態(tài)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算法使用"滑動窗口"的方法，來尋找文件中的相同部分，也就是匹配串。我們先對這里的串做一個說明，它是指一個任意字節(jié)的序列，而不僅僅是可以在文本文件中顯示出來的那些字節(jié)的序列。這里的串強調的是它在文件中的位置，它的長度隨著匹配的情況而變化。
LZ77從文件的開始處開始，一個字節(jié)一個字節(jié)的向后進行處理。一個固定大小的窗口（在當前處理字節(jié)之前，并且緊挨著當前處理字節(jié)），隨著處理的字節(jié)不斷的向后滑動，就象在陽光下，飛機的影子滑過大地一樣。對于文件中的每個字節(jié)，用當前處理字節(jié)開始的串，和窗口中的每個串進行匹配，尋找最長的匹配串。窗口中的每個串指，窗口中每個字節(jié)開始的串。如果當前處理字節(jié)開始的串在窗口中有匹配串，就用(之間的距離，匹配長度) 這樣一對信息，來替換當前串，然后從剛才處理完的串之后的下一個字節(jié)，繼續(xù)處理。如果當前處理字節(jié)開始的串在窗口中沒有匹配串，就不做改動的輸出當前處理字節(jié)。
處理文件中第一個字節(jié)的時候，窗口在當前處理字節(jié)之前，也就是還沒有滑到文件上，這時窗口中沒有任何內容，被處理的字節(jié)就會不做改動的輸出。隨著處理的不斷向后，窗口越來越多的滑入文件，最后整個窗口滑入文件，然后整個窗口在文件上向后滑動，直到整個文件結束。
1.1.3 使用LZ77算法進行壓縮和解壓縮
為了在解壓縮時，可以區(qū)分“沒有匹配的字節(jié)”和“（之間的距離，匹配長度）對”，我們還需要在每個“沒有匹配的字節(jié)”或者“（之間的距離，匹配長度）對”之前，放上一位，來指明是“沒有匹配的字節(jié)”，還是“（之間的距離，匹配長度）對”。我們用0表示“沒有匹配的字節(jié)”，用1表示“（之間的距離，匹配長度）對”。
實際中，我們將固定（之間的距離，匹配長度）對中的，“之間的距離”和“匹配長度”所使用的位數。由于我們要固定“之間的距離”所使用的位數，所以我們才使用了固定大小的窗口，比如窗口的大小為32KB，那么用15位（2^15=32K）就可以保存0-32K范圍的任何一個值。實際中，我們還將限定最大的匹配長度，這樣一來，“匹配長度”所使用的位數也就固定了。
實際中，我們還將設定一個最小匹配長度，只有當兩個串的匹配長度大于最小匹配長度時，我們才認為是一個匹配。我們舉一個例子來說明這樣做的原因。比如，“距離”使用15位，“長度”使用8位，那么“（之間的距離，匹配長度）對”將使用23位，也就是差1位3個字節(jié)。如果匹配長度小于3個字節(jié)的話，那么用“（之間的距離，匹配長度）對”進行替換的話，不但沒有壓縮，反而會增大，所以需要一個最小匹配長度。
壓縮：
從文件的開始到文件結束，一個字節(jié)一個字節(jié)的向后進行處理。用當前處理字節(jié)開始的串，和滑動窗口中的每個串進行匹配，尋找最長的匹配串。如果當前處理字節(jié)開始的串在窗口中有匹配串，就先輸出一個標志位，表明下面是一個(之間的距離，匹配長度) 對，然后輸出(之間的距離，匹配長度) 對，然后從剛才處理完的串之后的下一個字節(jié)，繼續(xù)處理。如果當前處理字節(jié)開始的串在窗口中沒有匹配串，就先輸出一個標志位，表明下面是一個沒有改動的字節(jié)，然后不做改動的輸出當前處理字節(jié)，然后繼續(xù)處理當前處理字節(jié)的下一個字節(jié)。
解壓縮：
從文件開始到文件結束，每次先讀一位標志位，通過這個標志位來判斷下面是一個(之間的距離，匹配長度) 對，還是一個沒有改動的字節(jié)。如果是一個（之間的距離，匹配長度）對，就讀出固定位數的（之間的距離，匹配長度）對，然后根據對中的信息，將匹配串輸出到當前位置。如果是一個沒有改動的字節(jié)，就讀出一個字節(jié)，然后輸出這個字節(jié)。
我們可以看到，LZ77壓縮時需要做大量的匹配工作，而解壓縮時需要做的工作很少，也就是說解壓縮相對于壓縮將快的多。這對于需要進行一次壓縮，多次解壓縮的情況，是一個巨大的優(yōu)點。
1.2 Huffman編碼簡介
1.2.1 Huffman編碼的壓縮原理
我們把文件中一定位長的值看作是符號，比如把8位長的256種值，也就是字節(jié)的256種值看作是符號。我們根據這些符號在文件中出現的頻率，對這些符號重新編碼。對于出現次數非常多的，我們用較少的位來表示，對于出現次數非常少的，我們用較多的位來表示。這樣一來，文件的一些部分位數變少了，一些部分位數變多了，由于變小的部分比變大的部分多，所以整個文件的大小還是會減小，所以文件得到了壓縮。
1.2.2 Huffman編碼使用Huffman樹來產生編碼
要進行Huffman編碼，首先要把整個文件讀一遍，在讀的過程中，統(tǒng)計每個符號（我們把字節(jié)的256種值看作是256種符號）的出現次數。然后根據符號的出現次數，建立Huffman樹，通過Huffman樹得到每個符號的新的編碼。對于文件中出現次數較多的符號，它的Huffman編碼的位數比較少。對于文件中出現次數較少的符號，它的Huffman編碼的位數比較多。然后把文件中的每個字節(jié)替換成他們新的編碼。
建立Huffman樹：
把所有符號看成是一個結點，并且該結點的值為它的出現次數。進一步把這些結點看成是只有一個結點的樹。
每次從所有樹中找出值最小的兩個樹，為這兩個樹建立一個父結點，然后這兩個樹和它們的父結點組成一個新的樹，這個新的樹的值為它的兩個子樹的值的和。如此往復，直到最后所有的樹變成了一棵樹。我們就得到了一棵Huffman樹。
通過Huffman樹得到Huffman編碼：
這棵Huffman樹，是一棵二叉樹，它的所有葉子結點就是所有的符號，它的中間結點是在產生Huffman樹的過程中不斷建立的。
我們在Huffman樹的所有父結點到它的左子結點的路徑上標上0，右子結點的路徑上標上1。
現在我們從根節(jié)點開始，到所有葉子結點的路徑，就是一個0和1的序列。我們用根結點到一個葉子結點路徑上的0和1的序列，作為這個葉子結點的Huffman編碼。
我們來看一個例子。
有一個文件的內容如下
abbbbccccddde
我們統(tǒng)計一下各個符號的出現次數，
a b c d e
1 4 4 3 1
建立Huffman樹的過程如下圖所示
通過最終的Huffman樹，我們可以得到每個符號的Huffman編碼。
a 為 110
b 為 00
c 為 01
d 為 10
e 為 111
我們可以看到，Huffman樹的建立方法就保證了，出現次數多的符號，得到的Huffman編碼位數少，出現次數少的符號，得到的Huffman編碼位數多。
各個符號的Huffman編碼的長度不一，也就是變長編碼。對于變長編碼，可能會遇到一個問題，就是重新編碼的文件中可能會無法如區(qū)分這些編碼。
比如，a的編碼為000，b的編碼為0001，c的編碼為1，那么當遇到0001時，就不知道0001代表ac，還是代表b。出現這種問題的原因是a的編碼是b的編碼的前綴。
由于Huffman編碼為根結點到葉子結點路徑上的0和1的序列，而一個葉子結點的路徑不可能是另一個葉子結點路徑的前綴，所以一個Huffman編碼不可能為另一個Huffman編碼的前綴，這就保證了Huffman編碼是可以區(qū)分的。
1.2.3 使用Huffman編碼進行壓縮和解壓縮
為了在解壓縮的時候，得到壓縮時所使用的Huffman樹，我們需要在壓縮文件中，保存樹的信息，也就是保存每個符號的出現次數的信息。
壓縮：
讀文件，統(tǒng)計每個符號的出現次數。根據每個符號的出現次數，建立Huffman樹，得到每個符號的Huffman編碼。將每個符號的出現次數的信息保存在壓縮文件中，將文件中的每個符號替換成它的Huffman編碼，并輸出。
解壓縮：
得到保存在壓縮文件中的，每個符號的出現次數的信息。根據每個符號的出現次數，建立Huffman樹，得到每個符號的Huffman編碼。將壓縮文件中的每個Huffman編碼替換成它對應的符號，并輸出。
2 gzip 所使用壓縮算法的實現
我們將gzip的實現分成很多個部分，一個個來說明，這樣做的原因見本文最后一部分。
gzip 中所使用的各種實現技巧的出處或者靈感，gzip 的作者在源碼的注釋中進行了說明。
2.1 尋找匹配串的實現
為一個串尋找匹配串需要進行大量的匹配工作，而且我們還需要為很多很多個串尋找匹配串。所以 gzip 在尋找匹配串的實現中使用哈希表來提高速度。
要達到的目標是，對于當前串，我們要在它之前的窗口中，尋找每一個匹配長度達到最小匹配的串，并找出匹配長度最長的串。
在 gzip 中，最小匹配長度為3，也就是說，兩個串，最少要前3個字節(jié)相同，才能算作匹配。為什么最小匹配長度為3，將在后面說明。
gzip 對遇到的每一個串，首先會把它插入到一個“字典”中。這樣當以后有和它匹配的串，可以直接從“字典”中查出這個串。
插入不是亂插，查也不是亂查。插入的時候，使用這個插入串的前三個字節(jié)，計算出插入的“字典”位置，然后把插入串的開始位置保存在這個“字典”位置中。查出的時候，使用查出串的前三個字節(jié)，計算出“字典”位置，由于插入和查出使用的是同一種計算方法，所以如果兩個串的前三個字節(jié)相同的話，計算出的“字典”位置肯定是相同的，所以就可以直接在該“字典”位置中，取出以前插入時，保存進去的那個串的開始位置。于是查出串，就找到了一個串，而這個串的前三個字節(jié)和自己的一樣（其實只是有極大的可能是一樣的，原因后面說明），所以就找到了一個匹配串。
如果有多個串，他們的前三個字節(jié)都相同，那么他們的“字典”位置，也都是相同的，他們將被鏈成一條鏈，放在那個“字典”位置上。所以，如果一個串，查到了一個“字典”位置，也就查到了一個鏈，所有和它前三個字節(jié)相同的串，都在這個鏈上。
也就是說，當前串之前的所有匹配串被鏈在了一個鏈上，放在某個“字典”位置上。而當前串使用它的前三個字節(jié)，進行某種計算，就可以得到這個“字典”位置（得到了“字典”位置之后，它首先也把自己鏈入到這個鏈上），也就找到了鏈有它的所有匹配串的鏈，所以要找最長的匹配，也就是遍歷這個鏈上的每一個串，看和哪個串的匹配長度最大。
下面我們更具體的說明，尋找匹配串的實現。
我們前面所說的“字典”，是一個數組，叫做head[]（為什么叫head,后面進行說明）。
我們前面所說的“字典”位置，放在一個叫做ins_h的變量中。
我們前面所說的鏈，是在一個叫做prev[]的數組中。
插入：
當前字節(jié)為第 strstart 個字節(jié)。通過第strstart,strstart+1,strstart+2,這三個字節(jié)，使用一個設計好的哈希函數算出ins_h，也就是插入的位置。然后將當前字節(jié)的位置，即strstart，保存在head[ins_h]中。
注意由 strstart,strstart+1,strstart+2,這三個字節(jié)（也就是strstart開始處的串的頭三個字節(jié)，也就是當前字節(jié)和之后的兩個字節(jié)）確定了ins_h。head[ins_h]中保存的又是strstart，也就是這個串開始的位置。
判斷是否有匹配：
當前串的前三個字節(jié)，使用哈希函數算出ins_h，這時如果head[ins_h]的值不為空的話，那么head[ins_h]中的值，便是之前保存在這里的另一個串的位置，并且這個串的前三個字節(jié)算出的ins_h，和當前串的前三個字節(jié)算出的ins_h相同。也就是說有可能有匹配。如果head[ins_h]的值為空的話，那么肯定沒有匹配。
gzip所使用的哈希函數：
gzip 所使用的哈希函數，用三個字節(jié)來計算一個ins_h，這是由于最小匹配為三個字節(jié)。
對于相同的三個字節(jié)，通過哈希函數得到的ins_h必然是相同的。
而不同的三個字節(jié)，通過哈希函數有可能得到同一個ins_h，不過這并不要緊，
當gzip發(fā)現head[ins_h]不空后，也就是說有可能有匹配串的話，會對鏈上的每一個串進行真正的串的比較。
所以一個鏈上的串，只是前三個字節(jié)用哈希函數算出的值相同，而并不一定前三個字節(jié)都是相同的。但是這樣已經很大的縮小了需要進行串比較的范圍。
我們來強調一下，前三個字節(jié)相同的串，必然在同一個鏈上。在同一個鏈上的，不一定前三個字節(jié)都相同。
不同的三個字節(jié)有可能得到同一個結果的原因是，三個字節(jié)，一共24位，有2^24種可能值。而三個字節(jié)的哈希函數的計算結果為15位，有2^15種可能值。也就是說2^24種值，與2^15種值進行對應，必然是多對一的，也就是說，必然是有多種三個字節(jié)的值，用這個哈希函數計算出的值都是相同的。
而我們使用哈希函數的理由是，實際上，我們只是在一個窗口大小的范圍內（后面將會看到）尋找匹配串，一個窗口的大小范圍是很有限的，能出現的三個字節(jié)的值組合情況也是很有限的，將遠遠小于2^24，使用合適的哈希函數是高效的。
前三個字節(jié)相同的所有的串所在的鏈：
head[ins_h] 中的值，有兩個作用。一個作用，是一個前三個字節(jié)計算結果為ins_h的串的位置。另一個作用，是一個在prev[]數組中的索引，用這個索引在prev[]中，將找到前一個前三個字節(jié)計算結果為ins_h的串的位置。即prev[head[ins_h]]的值（不為空的話）為前一個前三個字節(jié)計算結果為ins_h的串的位置。
prev[]的值，也有兩個作用。一個作用，是一個前三個字節(jié)計算結果為ins_h的串的位置。另一個作用，是一個在prev[]數組中的索引，用這個索引在prev[]中，將找到前一個前三個字節(jié)計算結果為ins_h的串的位子哈。即prev[]的值（不為空的話）為前一個三個字節(jié)計算結果為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。
鏈的建立：
gzip在每次處理當前串的時候，首先用當前串的前三個字節(jié)計算出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;
就這樣，每次把一個串的位置加入到鏈中，鏈就形成了。
現在我們也就知道了，前三個字節(jié)計算得到同一ins_h的所有的串被鏈在了一起，head[ins_h]為鏈頭，prev[]數組中放著的更早的串的位置。head數組和prev數組的名字，也正反應了他們的作用。
鏈的特點：
越向前（prev）與當前處理位置之間的距離越大。比如，當前處理串，算出了ins_h，而且head[ins_h]中的值不空，那么head[ins_h]就是離當前處理串距離最近的一個可能的匹配串，并且順著prev[]向前所找到的串，越來距離越遠。
匹配串中的字節(jié)開始的串的插入：
我們說過了，所有字節(jié)開始的串，都將被插入“字典”。對于確定了的匹配串，匹配串中的每個字節(jié)開始的串，仍要被插入“字典”，以便后面串可以和他們進行匹配。
注意：
對于文件中的第0字節(jié)，情況很特殊，它開始的串的位置為0。所以第0串的前三個字節(jié)計算出ins_h之后，在head[ins_h]中保存的位置為0。而對是否有可能有匹配的判斷，就是通過head[ins_h]不為0，并且head[ins_h]的值為一個串的開始位置。所以第0字節(jié)開始的串，由于其特殊性，將不會被用來匹配，不過這種情況只會出現在第0個字節(jié)，所以通常不會造成影響，即使影響，也會極小。
例如，文件內容為
jiurl jiurl
找到的匹配情況如下，[]所括部分。
jiurl j[iurl]
2.2 懶惰啊匹配（lazy match）
對于當前字節(jié)開始的串，尋找到了最長匹配之后，gzip并不立即決定使用這個串進行替換。而是看看這個匹配長度是否滿意，如果匹配長度不滿意，而下一個字節(jié)開始的串也有匹配串的話，那么gzip就找到下一個字節(jié)開始的串的最長匹配，看看是不是比現在這個長。這叫懶惰啊匹配。如果比現在這個長的話，將不使用現在的這個匹配。如果比現在這個短的話，將確定使用現在的這個匹配。
我們來舉個例子，串
0abc bcde abcde
處理到第10字節(jié)時，也就是"abcde"的a時，找到最長匹配的情況如下，[]所括部分。
0abc bcde [abc]de
這時，再看看下一個字節(jié)，也就是第11字節(jié)的情況，也就是'abcde"的b，找到最長匹配的情況如下，[]所括部分。
0abc bcde a[bcde]
發(fā)現第二次匹配的匹配長度大，就不使用第一次的匹配串。我們也看到了如果使用第一次匹配的話，將錯過更長的匹配串。
在滿足懶惰啊匹配的前提條件下，懶惰啊匹配不限制次數，一次懶惰啊匹配發(fā)現了更長的匹配串之后，仍會再進行懶惰啊匹配，如果這次懶匹配，發(fā)現了更長的匹配串，那么上一次的懶匹配找到的匹配串就不用了。
進行懶惰啊匹配是有條件的。進行懶惰啊匹配必須滿足兩個條件，第一，下一個處理字節(jié)開始的串，要有匹配串，如果下一個處理字節(jié)開始的串沒有匹配串的話，那么就確定使用當前的匹配串，不進行懶匹配。第二，當前匹配串的匹配長度，gzip不滿意，也就是當前匹配長度小于max_lazy_match（max_lazy_match在固定的壓縮級別下，有固定的值）。
討論：
我們可以看到了做另外一次嘗試的原因。如果當前串有匹配就使用了的話，可能錯過更長匹配的機會。使用懶惰啊匹配會有所改善。
不過從我簡單的分析來看，使用懶惰啊匹配對壓縮率的改善似乎是非常有限的。
2.3 大于64KB的文件，窗口的實現
窗口的實現：
實際中，當前串（當前處理字節(jié)開始的串）只是在它之前的窗口中尋找匹配串的，也就是說只是在它之前的一定大小的范圍內尋找匹配串的。有這個限制的原因，將在后面說明。
gzip 的窗口大小為 WSIZE，32KB。
內存中有一個叫window[]的緩沖區(qū)，大小為2個窗口的大小，也就是64KB。文件的內容將被讀到這個window[]中，我們在window[]上進行LZ77部分的處理，得到結果將放在其他緩沖區(qū)中。
gzip 對window[]中的內容，從開始處開始，一個字節(jié)一個字節(jié)的向后處理。有一個指針叫strstart（其實是個索引），指向當前處理字節(jié)，當當前處理字節(jié)開始的串沒有匹配時，不做改動的輸出當前處理字節(jié)，strstart向后移動一個字節(jié)。當當前處理字節(jié)開始的串找到了匹配時，輸出（匹配長度，相隔距離）對，strstart向后移動匹配長度個字節(jié)。我們把strstart到window[]結束的這部分內容，叫做 lookahead buffer，超前查看緩沖區(qū)。這樣叫的原因是，在我們處理當前字節(jié)的時候，就需要讀出之后的字節(jié)來進行串的匹配。在一個變量lookahead中，保存著超前查看緩沖區(qū)所剩的字節(jié)數。lookahead，最開始被初始化為整個讀入內容的大小，隨著處理的進行，strstart不斷后移，超前查看緩沖區(qū)不斷減小，lookahead的值也不斷的減小。
我們需要限制查找匹配串的范圍為一個窗口的大?。ㄟ@么做的原因后面說明），也就是說，只能在當前處理字節(jié)之前的32KB的范圍內尋找匹配串。而，由于處理是在2個窗口大小，也就是64KB大小的緩沖區(qū)中進行的，所以匹配鏈上的串與當前串之間的距離是很有可能超過32KB的。那么gzip是如何來實現這個限制的呢？
gzip 通過匹配時的判斷條件來實現這個限制。當當前串計算ins_h，發(fā)現head[ins_h]值不為空時（head[ins_h]為一個串的開始位置），說明當前串有可能有匹配串，把這個值保存在 hash_head中。這時就要做一個限制范圍的判斷，strstart - hash_head <= 窗口大小，strstart-hash_head 是當前串和最近的匹配串之間的距離，（注意前面說過，鏈頭和當前串的距離最近，越向前（prev）與當前處理位置之間的距離越大），也就是說要判斷當前串和距離最近的匹配串之間的距離是否在一個窗口的范圍之內。如果不是的話，那么鏈上的其他串肯定更遠，肯定更不在一個窗口的范圍之內，就不進行匹配處理了。如果是在一個窗口的范圍之內的話，還需要在鏈上尋找最長的匹配串，在和每個串進行比較的時候，也需要判斷當前串和該串的距離是否超過一個窗口的范圍，超過的話，就不能進行匹配。
實際中，gzip為了使代碼簡單點，距離限制要比一個窗口的大小還要小一點。
小于64KB的文件：
初始化的時候，會首先從文件中讀64KB的內容到window[]中。
對于小于64KB的文件，整個文件都被讀入到window[]中。在window[]上進行LZ77的處理，從開始直到文件結束。
大于64KB的文件：
每處理一個字節(jié)都要判斷 lookahead < MIN_LOOKAHEAD ，也就是window中還沒有處理的字節(jié)是否還夠MIN_LOOKAHEAD ，如果不夠的話，就會導致 fill_window()，從文件中讀內容到window[]中。由于我們一次最大可能使用的超前查看緩沖區(qū)的大小為，最大匹配長度（258個字節(jié)，后面進行說明）加上最小匹配長度，也就是下一個處理字節(jié)開始的串，可以找到一個最大匹配長度的匹配，發(fā)生匹配之后，還要預讀一個最小匹配長度來計算之后的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內容的接近結束部分，也就是如果再處理，超前查看緩沖區(qū)中的內容就可能不夠了。由于 lookahead < MIN_LOOKAHEAD ，將執(zhí)行 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的內容，復制到第二個窗中，注意第二個窗口中原來的內容，已經被復制到了第一個窗口中。
就這樣，一窗窗的處理，直到整個文件結束。
分析：
到第二窗文件內容也快要處理完的時候，才會從文件中讀入新的內容。而這時，第一窗中的所有串，對于當前處理字節(jié)和之后的字節(jié)來說，已經超出了一個窗口的距離，當前處理字節(jié)和之后的字節(jié)不能和第一窗的串進行匹配了，也就是說第一窗的內容已經沒有用了。所有插入字典的第一窗的串也已經沒有用了。所以覆蓋第一窗的內容是合理的，將字典中第一窗的串的開始位置都設為空也是合理的。
將第二窗的內容復制到第一窗中，那么第二窗在字典中的所有索引都需要做相應的修正。
由于第二窗的內容已經復制到了第一窗中，所以我們可以將新的內容讀入到第二窗中，新的內容之前的32KB的內容，就是原來的第二窗中的內容。而這時，做過修正的字典中，仍然有原來第二窗中所有串的信息，也就是說，新的內容，可以繼續(xù)利用前面一個窗口大小的范圍之內的串，進行壓縮，這也是合理的。
2.4 其他問題1
現在來說明一下，為什么最小匹配長度為3個字節(jié)。這是由于，gzip 中，(匹配長度，相隔距離)對中，"匹配長度"的范圍為3-258，也就是256種可能值，需要8bit來保存。"相隔距離"的范圍為0-32K，需要15bit來保存。所以一個(匹配長度，相隔距離)對需要23位，差一位3個字節(jié)。如果匹配串小于3個字節(jié)的話，使用(匹配長度，相隔距離)對進行替換，不但沒有壓縮，反而還會增大。所以保存(匹配長度，相隔距離)對所需要的位數，決定了最小匹配長度至少要為3個字節(jié)。
最大匹配長度為258的原因是，綜合各種因素，決定用8位來保存匹配長度，8位的最大值為255。實際中，我們在(匹配長度，相隔距離)對中的“匹配長度”保存的是，實際匹配長度-最小匹配長度，所以255對應的實際匹配長度為258。
在進行匹配時，會對匹配長度進行判斷，保證到達最大匹配長度時，匹配就停止。也就是說，即使有兩個串的相同部分超過了最大匹配長度，也只匹配到最大匹配長度。
保存相隔距離所用的位數和窗口大小是互相決定的，綜合兩方面各種因素，確定了窗口大小，也就確定了保存相隔距離所使用的位數。
2.5 gzip 的 LZ77部分的實現要點
gzip 的 LZ77 部分的實現主要在函數 defalte() 中。
所使用的緩沖區(qū)
window[] 用來放文件中讀入的內容。
l_buf[]，d_buf[]，flag_buf[] 用來放LZ77壓縮得到的結果。
l_buf[] 中的每個字節(jié)是一個沒有匹配的字節(jié)，或者是一個匹配的對中的匹配長度-3。l_buf[]共用了inbuf[]。
d_buf[] 中的每個unsigned short，是一個匹配的對中的相隔距離。
flag_buf[] 中每位是一個標志，用來指示l_buf[]中相應字節(jié)是沒有匹配的字節(jié)，還是一個匹配的對中的匹配長度-3。
prev[]，head[] 用來存放字典信息。實際上 head 為宏定義 prev+WSIZE。
初始化過程中，調用 lm_init()。
lm_init() 中，從輸入文件中讀入2個窗口大小，也就是64KB的內容到window[]中。lookahead 中為返回的讀入字節(jié)數。使用window中的頭兩個字節(jié)，UPDATE_HASH，初始化ins_h。
deflate() 中，一個處理循環(huán)中，首先 INSERT_STRING 把當前串插入字典，INSERT_STRING 是一個宏，作用就是用哈希函數計算當前串的ins_h，然后把原來的head[ins_h]中的內容，鏈入鏈中（放到prev中），同時把原來的head[ins_h]保存在hash_head變量中，用來后面進行匹配判斷，然后把當前串的開始位置，保存在head[ins_h]中。
判斷hash_head中保存的內容不為空，說明匹配鏈上有內容。調用 longest_match () 尋找匹配鏈上的最長匹配。
hash_head中保存的內容為空，說明當前字節(jié)開始的串，在窗口中沒有匹配。
由于使用了lazy match，使得判斷的情況更復雜。
匹配串的輸出，或者是沒有匹配的字節(jié)的輸出，都是調用函數 ct_tally()。
對于匹配串，輸出之后，還需要為匹配串中的每個字節(jié)使用 INSERT_STRING，把匹配串中每個字節(jié)開始的串都插入到字典中。
ct_tally()中，把傳入的"沒有匹配的字節(jié)"或者是"匹配長度-3"放到l_buf[]中，然后為以后的Huffman編碼做統(tǒng)計次數的工作，如果傳入的是匹配情況，傳入的參數中會有相隔距離，把相隔距離保存在d_buf[]中。根據傳入的參數，可以判斷是哪種情況，然后設置一個變量中相應的標志位，每8個標志位，也就是夠一個字節(jié)，就保存到flag_buf[]中。還有一些判斷，我們將在后面進行說明。
2.6 分塊輸出
LZ77 壓縮的結果放在，l_buf[]，d_buf[]，flag_buf[] 中。
對于 LZ77 的壓縮結果，可能使用一塊輸出或者分成多塊輸出（LZ77壓縮一定的部分之后，就進行一次塊輸出，輸出一塊）。塊的大小不固定。
輸出的時候，會對LZ77的壓縮結果，進行Huffman編碼，最終把Huffman編碼的結果輸出到outbuf[]緩沖區(qū)中。
進行Huffman編碼，并輸出的工作，在 flush_block() 中進行。
在ct_tally()中進行判斷，如果滿足一些條件的話，當從ct_tally()中返回之后，就會對現有的LZ77的結果，進行Huffman編碼，輸出到一個塊中。
在整個文件處理結束，deflate()函數要結束的時候，會把LZ77的結果，進行Huffman編碼，輸出到一個塊中。
在ct_tally()中，每當l_buf[]中的字節(jié)數（每個字節(jié)是一個沒有匹配的字節(jié)或者一個匹配長度）增加0x1000，也就是4096的時候。將估算壓縮的情況，以判斷現在結束這個塊是否比較好，如果覺得比較好，就輸出一個塊。如果覺得不好，就先不輸出。
而當l_buf[]滿了的時候，或者d_buf[]滿了的時候，將肯定對現有的LZ77壓縮的結果，進行Huffman編碼，輸出到一個塊中。
決定輸出一塊的話，會只針對這一塊的內容，建立Huffman樹，這一塊內容將會被進行Huffman編碼壓縮，并被輸出到outbuf[]中。如果是動態(tài)Huffman編碼，樹的信息也被輸出到outbuf[]中。輸出之后，會調用init_block()，初始化一個新塊，重新初始化一些變量，包括動態(tài)樹的結點被置0，也就是說，將為新塊將來的Huffman樹重新開始統(tǒng)計信息。
輸出塊的大小是不固定的，首先在進行Huffman編碼之前，要輸出的內容的大小就是不固定，要看情況，進行Huffman編碼之后，就更不固定了。
塊的大小不固定，那么解壓縮的時候，如何區(qū)分塊呢。編碼樹中有一個表示塊結束的結點，EOB，在每次輸出塊的最后，輸出這個結點的編碼，所以解壓縮的時候，當遇到了這個結點就表明一個塊結束了。
每個塊最開始的2位，用來指明本塊使用的是哪種編碼方式，00表示直接存儲，01表示靜態(tài)Huffman編碼，10表示動態(tài)Huffman編碼。接下來的1位，指明本塊是否是最后一塊，0表示不是，1表示是最后一塊。
輸出一個塊，對現在字典中的內容沒有影響，下一個塊，仍將用之前形成的字典，進行匹配。
2.7 靜態(tài)Huffman編碼與動態(tài)Huffman編碼
靜態(tài)Huffman編碼就是使用gzip自己預先定義好了一套編碼進行壓縮，解壓縮的時候也使用這套編碼，這樣不需要傳遞用來生成樹的信息。
動態(tài)Huffman編碼就是使用統(tǒng)計好的各個符號的出現次數，建立Huffman樹，產生各個符號的Huffman編碼，用這產生的Huffman編碼進行壓縮，這樣需要傳遞生成樹的信息。
gzip 在為一塊進行Huffman編碼之前，會同時建立靜態(tài)Huffman樹，和動態(tài)Huffman樹，然后根據要輸出的內容和生成的Huffman樹，計算使用靜態(tài)Huffman樹編碼，生成的塊的大小，以及計算使用動態(tài)Huffman樹編碼，生成塊的大小。然后進行比較，使用生成塊較小的方法進行Huffman編碼。
對于靜態(tài)樹來說，不需要傳遞用來生成樹的那部分信息。動態(tài)樹需要傳遞這個信息。而當文件比較小的時候，傳遞生成樹的信息得不償失，反而會使壓縮文件變大。也就是說對于文件比較小的時候，就可能會出現使用靜態(tài)Huffman編碼比使用動態(tài)Huffman編碼，生成的塊小。
2.8 編碼的產生
deflate算法在Huffman樹的基礎上，又加入了幾條規(guī)則，我們把這樣的樹稱作deflate樹，使得只要知道所有位長上的結點的個數，就可以得到所有結點的編碼。這樣做的原因是，減少需要存放在壓縮壓縮文件中的用來生成樹的信息。要想弄明白，deflate如何生成Huffman編碼，一定要弄明白一些Huffman樹，和deflate樹的性質，下面內容是對Huffman樹和deflate樹做了些簡單研究得到的。
Huffman樹的性質
1 葉子結點為n的話，那么整顆樹的總結點為 2n-1。
簡單證明說明，先證，最小的樹，也就是只有三個結點，一個根節(jié)點，兩個葉子節(jié)點的樹符合。然后在任何符合的樹上做最小的添加得到的樹也符合。所以都符合。
2 最左邊的葉子結點的編碼為0，但是位長不一定。
deflate中增加了附加條件的huffman樹的性質
1 同樣位長的葉子結點的編碼值為連續(xù)的，右面的總比左面的大1。
2 (n+1)位長最左面的葉子結點（也就是編碼值最小的葉子結點）的值為n位長最右面的葉子結點（也就是編碼值最大的葉子結點）的值+1，然后變長一位（也就是左移1位）。
3 n位長的葉子結點，最右面的葉子結點（也就是編碼值最大的葉子結點）的值為最左面的葉子結點（也就是編碼值最小的葉子結點）的值 加上 n位長的葉子結點的個數 減 1。
4 (n+1)位長最左面的葉子結點（也就是編碼值最小的葉子結點）的值 為 n位長最左面的葉子結點（也就是編碼值最小的葉子結點）的值 加上 n位長的葉子結點的個數，然后變長一位（也就是左移1位）。
還有一些樹的性質，比如，樹的某一深度上最大可能編碼數。
從所有編碼的位長，得到所有編碼的編碼：
統(tǒng)計每個位長上的編碼個數放在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二叉樹的性質。
2.9 5棵樹
一共有5棵樹 static_ltree[]，static_dtree[]，dyn_ltree[]，dyn_dtree[]，bl_tree[]。
對于所有的樹，一個葉子結點表示的符號的值為n的話，那么這個符號對應的葉子結點放在 tree[n] 中，
比如 static_ltree 的葉子結點'a' 的值為十進制97，那么'a'的葉子結點就放在 static_ltree[97] 。
static_ltree[] 靜態(tài)Huffman編碼時，用來對沒有改動的字節(jié)和匹配長度進行編碼的樹。
static_dtree[] 靜態(tài)Huffman編碼時，用來對相隔距離進行編碼的樹。
dyn_ltree[] 動態(tài)Huffman編碼時，用來對沒有改動的字節(jié)和匹配長度進行編碼的樹。
dyn_dtree[] 動態(tài)Huffman編碼時，用來對相隔距離進行編碼的樹。
bl_tree[] 動態(tài)Huffman編碼時，用來對解壓縮時用來產生dyn_ltree[]和dyn_dtree[]的信息進行編碼的樹。
靜態(tài)樹在初始化的時候，為每個葉子結點直接產生編碼。
動態(tài)樹，每次要輸出一塊的內容，就根據這一塊的內容，生成動態(tài)樹，再根據生成的動態(tài)樹，為每個葉子結點產生編碼。
每次要輸出一塊的內容時，會計算用靜態(tài)樹編碼得到的塊的大小，和用動態(tài)樹編碼得到的塊的大小，然后誰產生的塊小就用誰。
用靜態(tài)編碼的話，就使用 static_ltree[]，static_dtree[]，來進行編碼輸出。
用動態(tài)編碼的話，就使用 dyn_ltree[]，dyn_dtree[]，bl_tree[] 來進行編碼輸出。
2.10 葉子結點
ltree （用來對沒有改動的字節(jié)和匹配長度進行編碼的樹，靜態(tài)，動態(tài)都一樣）的葉子結點
一共 L_CODES 個，也就是286個。
0-255 256個葉子結點，是字節(jié)的256個值
256 1個葉子結點，是 END_BLOCK，用來表示塊結束的葉子結點。
257-285 29個葉子結點，是表示匹配長度的29個范圍。
dtree （用來對相隔距離進行編碼的樹，靜態(tài)，動態(tài)都一樣）的葉子結點
一共 D_CODES 個，也就是30個。
0-29 30個葉子結點，是表示相隔距離的30個范圍。
bl_tree 的葉子結點
一共 BL_CODES 個，也就是19個。
0-15 表示編碼位長為 0-15。
16 復制之前的編碼長度3-6次。之后的兩位指明重復次數。
17 重復編碼位長為0的，3-10次，之后的3位指明重復次數。
18 重復編碼位長為0的，11-138次，之后的7位指明重復次數。
2.11 靜態(tài)Huffman編碼
初始化base_length[],length_code[],base_dist[],dist_code[]。
base_length[]為，29個 匹配長度 范圍的，每個范圍開始的長度值。
length_code[]為，256 個可能的匹配長度 所屬的范圍。
比如，base_length[9]=0xa，表示第9個范圍的開始值為0xa。
length_code[11]=9,表示匹配長度為11的匹配長度，屬于第9個范圍。
base_dist[],30個 匹配距離 范圍的，每個范圍的開始的值，就是每個范圍內最小的值。
dist_code[],這個有點特殊，一共有32K個取值，這里把這32K種值，分成了兩大類，
0-255這256個值為一類，這時他們直接為dist_code[]的索引。
256-32K為一類，這時他們的去掉低7位，和最高位，剩下的8位為索引，8位剛好索引256項。能這么做的原因是，首先最大32K的距離最大需要15位，所以16位的最高位總不會用，其次剩下這些范圍的邊界至少都為二進制1 000 0000 的整數倍。
比如 匹配距離為 10,小于256，所以它屬于類 dist_code[10]=6，第6類。
匹配距離為 10K ，大于256，所以它屬于類 dist_code[256+10K>>7]=dist_code[256+10240>>7]=dist_code[256+80]=dist_code[336]=0x1a=26，屬于26類，26類的范圍為8193-12288，10240就是在這個范圍內。
指定了每個literal的位長。（一共將有288個literal。包括256個字節(jié)值+1個EOB+29個匹配長度范圍=286個。多2個是為了滿樹。）并統(tǒng)計每個位長上的literal個數放在bl_count[]中。
根據 bl_count[] 中的值，計算出每個位長上的最小編碼值，放在 next_code[] 中。
計算方法為，code = (code + bl_count[bits-1]) << 1;
理由是deflate二叉樹的性質，(n+1)位長最左面的葉子結點（也就是編碼值最小的葉子結點）的值 為 n位長最左面的葉子結點（也就是編碼值最小的葉子結點）的值 加上 n位長的葉子結點的個數，然后變長一位（也就是左移1位）。
然后從literal值的0，到literal值的最大。為每個literal編碼。
編碼方法為，某一位長對應的next_code[n]，最開始是這個位長上最左邊的葉子結點的編碼，然后++，就是下一個該位長上下一個葉子結點的編碼，依次類推，直到把這個位長上的葉子結點編碼完。
實際上的編碼為bi_reverse(next_code[])。
比如
tree[n].Code = bi_reverse(next_code[len]++, len);
此時 next_code[len] 值為 二進制 00110000 即0x30
tree[n].Code 最后被賦值為 二進制 00001100 即0x0c
這樣我們就得到了 static_ltree[]，它以literal的值為索引，存放著literal對應的編碼。
比如 'a' 的值為十進制97， static_ltree[97].code=0x0089 static_ltree[97].len=8。
說明a的編碼為二進制 10001001。
為static_dtree編碼。這個編碼很簡單，由于所有結點都是5位長的（指定的），所以根據deflate二叉樹性質，最左邊的葉子節(jié)點編碼為0，之后每次加1即可，直到編完所有葉子結點。注意這里也要bi_reverse()一下。也就是說，編碼為"從樹根開始到一個葉子結點的路徑對應的位流"的逆位流。
用Huffman編碼對LZ77處理結果進行編碼輸出。
這時，
l_buf[]中每個字節(jié)為literal或者 匹配長度-MIN_MATCH。
d_buf[]為匹配距離，每項為16位。
flag_buf[]中每位為指示inbuf[]中對應字節(jié)為literal還是 匹配長度-MIN_MATCH 的標志，比如
flag_buf第i位為1，說明inbuf[i]為匹配長度-MIN_MATCH。
讀出flag_buf中的每一位，進行判斷。
如果為0，表示對應的l_buf中的那個字節(jié)為literal。
如果為1，表示對應的l_buf中的那個字節(jié)為匹配長度-MIN_MATCH。
對于literal，就用l_buf[]的這個值做索引，在static_ltree中得到編碼，和編碼長度，然后輸出這個編碼。
對于 匹配長度-MIN_MATCH，就用l_buf[]的這個值做索引，在length_code[]中首先得到這個匹配長度所在的范圍，一共有29個范圍。也就是說 匹配長度-MIN_MATCH 取值范圍為 (3..258)，一共有256種可能的值。這256種可能值，被分配在了29個范圍中。
我們用l_buf[]的這個值做索引，在length_code[]中得到這個匹配長度所在的范圍。
然后用 范圍值+256+1 得到該范圍所對應的 literal。用這個literal做索引，在static_ltree中得到編碼，和編碼長度，然后輸出這個編碼。
然后用 范圍值 做索引，在 extra_lbits[] 中得到該范圍的附加位的位數，如果附加位位數不為0，
就輸出附加位。附加位為 inbuf[]中的那個值，就是 匹配長度-MIN_MATCH 減去 這個范圍的對應的 base_length[]。
然后從d_buf[]中取出，匹配距離。
當匹配距離小于256時，用匹配距離做索引，在dist_code中取出對應的范圍值。
當匹配距離不小于256時，用匹配距離右移7位，也就是用高8位，做索引，在dist_code+256中取出對應的范圍值。
對匹配距離，匹配距離的取值范圍為，(1..32,768)，一共有32k種可能的值。
分成了30個范圍。由于匹配距離的取值范圍為，(1..32,768)，所以匹配距離使用15位。
然后用距離的范圍值做索引，在static_dtree[] 中得到編碼，和編碼長度。然后輸出這個編碼。
然后用距離的范圍值做索引，在extra_dbits[] 中得到該范圍的附加位的位數，如果附加位位數不為0，
就輸出附加位。輸出的附加位為 dist-base_dist[code]。
比如，取出一個dist為10。dist_code[10]=6，說明屬于第6個范圍。
然后查 extra_dbits,extra_dbits[6]=2，說明有兩個extra bits。
local int near extra_dbits[D_CODES] /* extra bits for each distance code */
= {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13};
首先輸出 static_dtree[6].len位的位流，static_dree[6].code。（static_dtree的位長都為5）
然后輸出 extra_dbits[6]位的位流，10-base_dist[6]=10-8=2=二進制的10。
發(fā)送完inbuf中的每個字節(jié)之后，最后發(fā)送 END_BLOCK 的編碼。
2.12 動態(tài)Huffman編碼
確定所有l(wèi)iteral，匹配長度范圍，和匹配距離范圍的出現次數。
在進行LZ77壓縮的過程中，每確定一個literal或者匹配，都會調用 ct_tally()。
在 ct_tally() 中，如果是一個literal，就 dyn_ltree[lc].Freq++。
如果是一個匹配，就 dyn_ltree[length_code[lc]+LITERALS+1].Freq++，dyn_dtree[d_code(dist)].Freq++。
調用 build_tree() 建立 literal和匹配長度范圍（也就是dyn_ltree的葉子結點，共286個） 的樹，并為他們（literal和匹配長度范圍）編碼。
生成樹中，heap[]是用來輔助生成樹的緩沖區(qū)。
首先把tree[]中所有出現次數不為0的值（也就是索引，比如tree[0x61]就為'a'的對應項），放到heap[]中。
tree[] 的元素個數為 2*L_CODES+1，L_CODES為葉子結點的個數，286。
由Huffman二叉樹性質，葉子結點為n,那么這棵樹的總結點為2n-1。
tree[] 將用來保存生成的樹。tree[]的前L_CODES 項，用來存放葉子結點。比如'a'的結點信息，放在tree[0x61]中。L_CODES 之后的項用來放中間結點。
heap[] 將用來放生成樹的過程中產生的臨時內容。heap[]的大小也為 2*L_CODES+1 。它的前 L_CODES 用來放
生成樹過程中的結點，最開始是葉子結點，隨著生成樹的進行，兩個葉子結點被弄掉，放入他們的中間結點。后 L_CODES ，從后向前用。在生成樹的過程中，所有結點（根，中間，葉子）都將按權值大小順序放在這里。
將來生成位長時，需要使用。
pqdownheap(tree, SMALLEST); 的作用就是將heap中的結點中，找出freq最小的那個，放在heap[1]中。
生成樹的過程為，每次從heap中找出兩個最小的結點，然后給他們弄一個父結點。并把他們的tree[]的相應內容指向他們的父結點。
并在heap中刪掉這兩個結點，而把他們的父結點加入到heap中。
heaplen 為heap中結點的個數，每次由于要刪2個結點，加1個結點，所以每次會使heaplen--，也就是結點數變少一個。
等到heaplen，也就是結點數，小于2時，說明樹已經要弄好了。
樹生成好之后，tree[]中的域 freq 和 dad 都被設置好了，調用 gen_bitlen()，為他們生成位長。
gen_bitlen()中，
從根開始，根的位長為0，向下，為每個結點設置位長。
判斷是否為葉子結點，判斷的方法是，看是否大于最大代碼，這里最大代碼是286。
當遇到葉子結點時，進行動態(tài)編碼整個文件的總位長的計算，和進行靜態(tài)編碼整個文件的總位長的計算。
bl_count[bits]++; 用來一會兒產生編碼。
由于在葉子結點的freq域中保存著這個結點的出現次數，現在又有了位長，所以可以計算該結點的動態(tài)位長。
而所有的結點的動態(tài)位長累加在一起就是總位長。
有了出現次數，對于靜態(tài)，結點位長是設定好的，也同樣可以進行計算。
最后調用 gen_codes()，為所有葉子結點產生編碼。和靜態(tài)Huffman中的方法是相同的。
調用 build_tree() 建立 匹配距離范圍（也就是dyn_dtree的葉子結點，共30個） 的樹，并為他們（匹配距離范圍）編碼。和生成dyn_ltree的方法是相同的。
調用 build_bl_tree() 為l（literal&匹配長度）和d（匹配距離）的位長數組 生成樹，并為這些位長編碼。
調用scan_tree統(tǒng)計一個樹中的編碼長度情況。
分別對dyn_ltree和dyn_dtree進行統(tǒng)計。
scan_tree((ct_data near *)dyn_ltree, l_desc.max_code);
scan_tree((ct_data near *)dyn_dtree, d_desc.max_code);
統(tǒng)計結果放在 bl_tree[].Freq 中。
弄明白了bl_tree[]中葉子結點的含義，就很容易理解scan_tree中所作的工作。
比如 bl_tree[0].Freq 表示編碼位長為0的編碼個數。
bl_tree[10].Freq 表示編碼位長為10的編碼個數。
bl_tree[16].Freq 表示 連續(xù)幾個編碼長度的出現個數都相同，這種情況的出現次數。
最后調用 build_tree() 建立位長情況（就是那19種情況）的樹，并為他們（就是那19種情況）編碼。
發(fā)送用bl_tree編碼的結點位長數組。
defalte算法中，只要知道了一個樹的每個葉子結點的位長，就可以得到該葉子結點的編碼。
所以我們需要發(fā)送ltree的286個葉子結點的位長，我們需要發(fā)送dtree的30個葉子結點的位長。
首先發(fā)送三個樹的最大葉子結點值的一個變形。
send_bits(lcodes-257, 5); 發(fā)送ltree有效最大葉子結點值+1-257
send_bits(dcodes-1, 5); 發(fā)送dtree有效最大葉子結點值+1-1
send_bits(blcodes-4, 4); 發(fā)送bl_tree有效最大葉子結點值+1-4。
ltree最大葉子結點值，就決定了我們將要發(fā)送的ltree的葉子結點位長數組的個數。只發(fā)送到有效最大葉子結點數就行了。
比如，ltree有效最大葉子結點值為0x102的話，那么我們只需要發(fā)送ltree中前0x103個的位長，并告訴解壓縮程序，發(fā)送了0x103個就行了。
發(fā)送 bl_tree 的位長，注意發(fā)送的順序是按 bl_order[] 中規(guī)定的順序發(fā)送的。
調用 send_tree() 先后發(fā)送 dyn_ltree,dyn_dtree 的位長。
send_tree()中使用和scan_tree()中相同的方法，首先看這些位長屬于bl_tree的19個葉子結點對應的19種情況中的哪一種，確定了是哪一種之后，
就按這種情況對應的葉子結點，在bl_tree中的編碼，發(fā)送這個編碼。直到把這些位長都發(fā)完。
用Huffman編碼對LZ77處理結果進行編碼輸出。和靜態(tài)Huffman編碼時使用的方法是相同的。
2.13 要點
第一，省去了LZ77用來指明是"沒有改動的字節(jié)"還是"匹配的信息對"的那個標志位。
由于gzip實現中，把匹配長度的范圍和字節(jié)值，做為不同的葉子結點進行編碼。比如說，值為1的字節(jié)，和一個值為1的匹配長度，他們的值雖然相同，但是他們是不同的葉子結點，他們的編碼也是不同的。這樣一來，解壓縮時，就可以直接區(qū)分，就不必再輸出那個指示位了。
這個節(jié)省對壓縮率的改善應該有不小的幫助。
靜態(tài)Huffman編碼時，編碼本身不會起到什么壓縮作用，但是還會從這個節(jié)省中獲益。
第二，葉子結點所表示的內容。
我們看到gzip的實現中，葉子節(jié)點所代表的內容各種各樣，不僅僅是一個固定的值，而且有些代表了一個值的范圍，（然后用之后的更多的位來表示這個范圍中的一個值），而且還有代表情況的。
這個實現方法是相當不錯的，非常值得借鑒。
解壓縮也不說了，原因看最后。
2.14 匹配延伸到lookahead中
可以進行這種壓縮，與解壓縮，關鍵是解壓縮的處理中，做了特別的處理。
例，串 0aaaaa
進行l(wèi)z77壓縮時，當今行到下面位置時 0a 當前位置->aaaa
匹配會延伸到lookahead中，結果就是 0a[匹配長度4，距離1]
解壓縮時，首先0a被做為沒有改動的字節(jié)解壓出來，
然后解壓發(fā)現[匹配長度4，距離1]，
這里將做一個判斷，看有沒有延伸到lookahead中，如果有的話，將做特別的處理，一個字節(jié)一個字節(jié)的進行復制。
3 最后
一個人，從找資料，到讀資料，到讀完源碼，到寫這個東西，花了三周多的時間，太慢了。中間到處找人希望可以一起來搞，也沒找著。太慢了，太花時間了，而且一個人，而且。反正一想起這事，就得淚水打濕了雙眼，淚過三巡以后，還得把脖子伸長，頭仰成一個角度，吟道:"我觀古昔之英雄，慷慨然諾杯酒中。義重生輕死知己，所以與人成大功"?？抟部蘖耍娨材盍?，回味一下這巨感人的一套，自己把自己又感動的不行，于是再來一遍。如此這般，一遍一遍，慘不忍睹。唉，還是該干嗎干嗎去吧。
