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