檔案壓縮算法

gzip 、zlib以及圖形格式png，使用的壓縮算法都是deflate算法。從gzip的源碼中，我們了解到了defalte算法的原理和實作。我閱讀的gzip版本為 gzip-1.2.4。下面我們将要對deflate算法做一個分析和說明。首先簡單介紹一下基本原理，然後詳細的介紹實作。

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編碼。

我們來看一個例子。

abbbbccccddde

我們統計一下各個符号的出現次數，

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編碼的長度不一，也就是變長編碼。對于變長編碼，可能會遇到一個問題，就是重新編碼的檔案中可能會無法如區分這些編碼。

比如，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 所使用壓縮算法的實作

我們将gzip的實作分成很多個部分，一個個來說明，這樣做的原因見本文最後一部分。

gzip 中所使用的各種實作技巧的出處或者靈感，gzip 的作者在源碼的注釋中進行了說明。

2.1 尋找比對串的實作

為一個串尋找比對串需要進行大量的比對工作，而且我們還需要為很多很多個串尋找比對串。是以 gzip 在尋找比對串的實作中使用哈希表來提高速度。

要達到的目标是，對于目前串，我們要在它之前的視窗中，尋找每一個比對長度達到最小比對的串，并找出比對長度最長的串。

在 gzip 中，最小比對長度為3，也就是說，兩個串，最少要前3個位元組相同，才能算作比對。為什麼最小比對長度為3，将在後面說明。

gzip 對遇到的每一個串，首先會把它插入到一個“字典”中。這樣當以後有和它比對的串，可以直接從“字典”中查出這個串。

插入的時候，使用這個插入串的前三個位元組，計算出插入的“字典”位置，然後把插入串的開始位置儲存在這個“字典”位置中。查出的時候，使用查出串的前三個位元組，計算出“字典”位置，由于插入和查出使用的是同一種計算方法，是以如果兩個串的前三個位元組相同的話，計算出的“字典”位置肯定是相同的，是以就可以直接在該“字典”位置中，取出以前插入時，儲存進去的那個串的開始位置。于是查出串，就找到了一個串，而這個串的前三個位元組和自己的一樣（其實隻是有極大的可能是一樣的，原因後面說明），是以就找到了一個比對串。

如果有多個串，他們的前三個位元組都相同，那麼他們的“字典”位置，也都是相同的，他們将被鍊成一條鍊，放在那個“字典”位置上。是以，如果一個串，查到了一個“字典”位置，也就查到了一個鍊，所有和它前三個位元組相同的串，都在這個鍊上。

也就是說，目前串之前的所有比對串被鍊在了一個鍊上，放在某個“字典”位置上。而目前串使用它的前三個位元組，進行某種計算，就可以得到這個“字典”位置（得到了“字典”位置之後，它首先也把自己鍊入到這個鍊上），也就找到了鍊有它的所有比對串的鍊，是以要找最長的比對，也就是周遊這個鍊上的每一個串，看和哪個串的比對長度最大。

下面我們更具體的說明，尋找比對串的實作。

我們前面所說的“字典”，是一個數組，叫做head[]（為什麼叫head,後面進行說明）。

我們前面所說的“字典”位置，放在一個叫做ins_h的變量中。

我們前面所說的鍊，是在一個叫做prev[]的數組中。

插入：

目前位元組為第 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，使用合适的哈希函數是高效的。

前三個位元組相同的所有的串所在的鍊：

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。

鍊的建立：

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）與目前處理位置之間的距離越大。比如，目前處理串，算出了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二叉樹的性質。

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[] 靜态huffman編碼時，用來對沒有改動的位元組和比對長度進行編碼的樹。

static_dtree[] 靜态huffman編碼時，用來對相隔距離進行編碼的樹。

dyn_ltree[] 動态huffman編碼時，用來對沒有改動的位元組和比對長度進行編碼的樹。

dyn_dtree[] 動态huffman編碼時，用來對相隔距離進行編碼的樹。

bl_tree[] 動态huffman編碼時，用來對解壓縮時用來産生dyn_ltree[]和dyn_dtree[]的資訊進行編碼的樹。

靜态樹在初始化的時候，為每個葉子結點直接産生編碼。

動态樹，每次要輸出一塊的内容，就根據這一塊的内容，生成動态樹，再根據生成的動态樹，為每個葉子結點産生編碼。

每次要輸出一塊的内容時，會計算用靜态樹編碼得到的塊的大小，和用動态樹編碼得到的塊的大小，然後誰産生的塊小就用誰。

用靜态編碼的話，就使用 static_ltree[]，static_dtree[]，來進行編碼輸出。

用動态編碼的話，就使用 dyn_ltree[]，dyn_dtree[]，bl_tree[] 來進行編碼輸出。

2.10 葉子結點

ltree （用來對沒有改動的位元組和比對長度進行編碼的樹，靜态，動态都一樣）的葉子結點

一共 l_codes 個，也就是286個。

0-255 256個葉子結點，是位元組的256個值

256 1個葉子結點，是 end_block，用來表示塊結束的葉子結點。

257-285 29個葉子結點，是表示比對長度的29個範圍。

dtree （用來對相隔距離進行編碼的樹，靜态，動态都一樣）的葉子結點

一共 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 靜态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個位元組值+1個eob+29個比對長度範圍=286個。多2個是為了滿樹。）并統計每個位長上的literal個數放在bl_count[]中。

然後從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二叉樹性質，最左邊的葉子節點編碼為0，之後每次加1即可，直到編完所有葉子結點。注意這裡也要bi_reverse()一下。也就是說，編碼為"從樹根開始到一個葉子結點的路徑對應的位流"的逆位流。

用huffman編碼對lz77處理結果進行編碼輸出。

這時，

l_buf[]中每個位元組為literal或者 比對長度-min_match。

d_buf[]為比對距離，每項為16位。

flag_buf[]中每位為訓示inbuf[]中對應位元組為literal還是比對長度-min_match 的标志，比如

flag_buf第i位為1，說明inbuf[i]為比對長度-min_match。

讀出flag_buf中的每一位，進行判斷。

如果為0，表示對應的l_buf中的那個位元組為literal。

如果為1，表示對應的l_buf中的那個位元組為比對長度-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。

發送完inbuf中的每個位元組之後，最後發送 end_block 的編碼。

2.12 動态huffman編碼

确定所有literal，比對長度範圍，和比對距離範圍的出現次數。

在進行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[]是用來輔助生成樹的緩沖區。

首先把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。

當遇到葉子結點時，進行動态編碼整個檔案的總位長的計算，和進行靜态編碼整個檔案的總位長的計算。

bl_count[bits]++; 用來一會兒産生編碼。

由于在葉子結點的freq域中儲存着這個結點的出現次數，現在又有了位長，是以可以計算該結點的動态位長。

而所有的結點的動态位長累加在一起就是總位長。

有了出現次數，對于靜态，結點位長是設定好的，也同樣可以進行計算。

最後調用 gen_codes()，為所有葉子結點産生編碼。和靜态huffman中的方法是相同的。

調用 build_tree() 建立 比對距離範圍（也就是dyn_dtree的葉子結點，共30個） 的樹，并為他們（比對距離範圍）編碼。和生成dyn_ltree的方法是相同的。

調用 build_bl_tree() 為l（literal&比對長度）和d（比對距離）的位長數組 生成樹，并為這些位長編碼。

調用scan_tree統計一個樹中的編碼長度情況。

分别對dyn_ltree和dyn_dtree進行統計。

scan_tree((ct_data near *)dyn_ltree, l_desc.max_code);

scan_tree((ct_data near *)dyn_dtree, d_desc.max_code);

統計結果放在 bl_tree[].freq 中。

弄明白了bl_tree[]中葉子結點的含義，就很容易了解scan_tree中所作的工作。

比如 bl_tree[0].freq 表示編碼位長為0的編碼個數。

bl_tree[10].freq 表示編碼位長為10的編碼個數。

bl_tree[16].freq 表示 連續幾個編碼長度的出現個數都相同，這種情況的出現次數。

最後調用 build_tree() 建立位長情況（就是那19種情況）的樹，并為他們（就是那19種情況）編碼。

發送用bl_tree編碼的結點位長數組。

defalte算法中，隻要知道了一個樹的每個葉子結點的位長，就可以得到該葉子結點的編碼。

是以我們需要發送ltree的286個葉子結點的位長，我們需要發送dtree的30個葉子結點的位長。

首先發送三個樹的最大葉子結點值的一個變形。

send_bits(lcodes-257, 5); 發送ltree有效最大葉子結點值+1-257

send_bits(dcodes-1, 5); 發送dtree有效最大葉子結點值+1-1

send_bits(blcodes-4, 4); 發送bl_tree有效最大葉子結點值+1-4。

ltree最大葉子結點值，就決定了我們将要發送的ltree的葉子結點位長數組的個數。隻發送到有效最大葉子結點數就行了。

比如，ltree有效最大葉子結點值為0x102的話，那麼我們隻需要發送ltree中前0x103個的位長，并告訴解壓縮程式，發送了0x103個就行了。

發送 bl_tree 的位長，注意發送的順序是按 bl_order[] 中規定的順序發送的。

調用 send_tree() 先後發送 dyn_ltree,dyn_dtree 的位長。

send_tree()中使用和scan_tree()中相同的方法，首先看這些位長屬于bl_tree的19個葉子結點對應的19種情況中的哪一種，确定了是哪一種之後，

就按這種情況對應的葉子結點，在bl_tree中的編碼，發送這個編碼。直到把這些位長都發完。

用huffman編碼對lz77處理結果進行編碼輸出。和靜态huffman編碼時使用的方法是相同的。

2.13 要點

第一，省去了lz77用來指明是"沒有改動的位元組"還是"比對的資訊對"的那個标志位。

由于gzip實作中，把比對長度的範圍和位元組值，做為不同的葉子結點進行編碼。比如說，值為1的位元組，和一個值為1的比對長度，他們的值雖然相同，但是他們是不同的葉子結點，他們的編碼也是不同的。這樣一來，解壓縮時，就可以直接區分，就不必再輸出那個訓示位了。

這個節省對壓縮率的改善應該有不小的幫助。

靜态huffman編碼時，編碼本身不會起到什麼壓縮作用，但是還會從這個節省中獲益。

第二，葉子結點所表示的内容。

我們看到gzip的實作中，葉子節點所代表的内容各種各樣，不僅僅是一個固定的值，而且有些代表了一個值的範圍，（然後用之後的更多的位來表示這個範圍中的一個值），而且還有代表情況的。

這個實作方法是相當不錯的，非常值得借鑒。

解壓縮也不說了，原因看最後。

2.14 比對延伸到lookahead中

可以進行這種壓縮，與解壓縮，關鍵是解壓縮的進行中，做了特别的處理。

例，串 0aaaaa

進行lz77壓縮時，當今行到下面位置時 0a 目前位置->aaaa

比對會延伸到lookahead中，結果就是 0a[比對長度4，距離1]

解壓縮時，首先0a被做為沒有改動的位元組解壓出來，

然後解壓發現[比對長度4，距離1]，

這裡将做一個判斷，看有沒有延伸到lookahead中，如果有的話，将做特别的處理，一個位元組一個位元組的進行複制。