1、1 gzip 所使用壓縮算法的基本原理gzip 對于要壓縮的文件,首先使用LZ77算法的一個變種進行壓縮,對得到的結果再使用Huffman編碼的方法(實際上gzip根據情況,選擇使用靜態Huffman編碼或者動態Huffman 編碼,詳細內容在實現中說明進行壓縮。所以明白了LZ77算法和Huffman編碼的壓縮原理,也就明白了gzip的壓縮原理。我們來對LZ77算法和Huffman編碼做一個簡單介紹。1.1 LZ77算法簡介這一算法是由Jacob Ziv 和Abraham Lempel 于1977 年提出,所以命名為LZ77。如果文件中有兩塊內容相同的話,那么只要知道前一塊的位置和大小,我們就

2、可以確定后一塊的內容。所以我們可以用(兩者之間的距離,相同內容的長度這樣一對信息,來替換后一塊內容。由于(兩者之間的距離,相同內容的長度這一對信息的大小,小于被替換內容的大小,所以文件得到了壓縮。下面我們來舉一個例子。有一個文件的內容如下(22,13中,22為相同內容塊與當前位置之間的距離,13為相同內容的長度。(23,4中,23為相同內容塊與當前位置之間的距離,4為相同內容的長度。由于(兩者之間的距離,相同內容的長度這一對信息的大小,小于被替換內容的大小,所以文件得到了壓縮。LZ77算法使用"滑動窗口"的方法,來尋找文件中的相同部分,也就是匹配串。我們先對這里的串做一個說

3、明,它是指一個任意字節的序列,而不僅僅是可以在文本文件中顯示出來的那些字節的序列。這里的串強調的是它在文件中的位置,它的長度隨著匹配的情況而變化。LZ77從文件的開始處開始,一個字節一個字節的向后進行處理。一個固定大小的窗口(在當前處理字節之前,并且緊挨著當前處理字節,隨著處理的字節不斷的向后滑動,就象在陽光下,飛機的影子滑過大地一樣。對于文件中的每個字節,用當前處理字節開始的串,和窗口中的每個串進行匹配,尋找最長的匹配串。窗口中的每個串指,窗口中每個字節開始的串。如果當前處理字節開始的串在窗口中有匹配串,就用(之間的距離,匹配長度 這樣一對信息,來替換當前串,然后從剛才處理完的串之后的下一個

4、字節,繼續處理。如果當前處理字節開始的串在窗口中沒有匹配串,就不做改動的輸出當前處理字節。處理文件中第一個字節的時候,窗口在當前處理字節之前,也就是還沒有滑到文件上,這時窗口中沒有任何內容,被處理的字節就會不做改動的輸出。隨著處理的不斷向后,窗口越來越多的滑入文件,最后整個窗口滑入文件,然后整個窗口在文件上向后滑動,直到整個文件結束。為了在解壓縮時,可以區分“沒有匹配的字節”和“(之間的距離,匹配長度對”,我們還需要在每個“沒有匹配的字節”或者“(之間的距離,匹配長度對”之前,放上一位,來指明是“沒有匹配的字節”,還是“(之間的距離,匹配長度對”。我們用0表示“沒有匹配的字節”,用1表示“(之

5、間的距離,匹配長度對”。實際中,我們將固定(之間的距離,匹配長度對中的,“之間的距離”和“匹配長度”所使用的位數。由于我們要固定“之間的距離”所使用的位數,所以我們才使用了固定大小的窗口,比如窗口的大小為32KB,那么用15位(215=32K就可以保存0-32K范圍的任何一個值。實際中,我們還將限定最大的匹配長度,這樣一來,“匹配長度”所使用的位數也就固定了。實際中,我們還將設定一個最小匹配長度,只有當兩個串的匹配長度大于最小匹配長度時,我們才認為是一個匹配。我們舉一個例子來說明這樣做的原因。比如,“距離”使用15位,“長度”使用8位,那么“(之間的距離,匹配長度對”將使用23位,也就是差1位

6、3個字節。如果匹配長度小于3個字節的話,那么用“(之間的距離,匹配長度對”進行替換的話,不但沒有壓縮,反而會增大,所以需要一個最小匹配長度。壓縮:從文件的開始到文件結束,一個字節一個字節的向后進行處理。用當前處理字節開始的串,和滑動窗口中的每個串進行匹配,尋找最長的匹配串。如果當前處理字節開始的串在窗口中有匹配串,就先輸出一個標志位,表明下面是一個(之間的距離,匹配長度 對,然后輸出(之間的距離,匹配長度 對,然后從剛才處理完的串之后的下一個字節,繼續處理。如果當前處理字節開始的串在窗口中沒有匹配串,就先輸出一個標志位,表明下面是一個沒有改動的字節,然后不做改動的輸出當前處理字節,然后繼續處理

7、當前處理字節的下一個字節。解壓縮:從文件開始到文件結束,每次先讀一位標志位,通過這個標志位來判斷下面是一個(之間的距離,匹配長度 對,還是一個沒有改動的字節。如果是一個(之間的距離,匹配長度對,就讀出固定位數的(之間的距離,匹配長度對,然后根據對中的信息,將匹配串輸出到當前位置。如果是一個沒有改動的字節,就讀出一個字節,然后輸出這個字節。我們可以看到,LZ77壓縮時需要做大量的匹配工作,而解壓縮時需要做的工作很少,也就是說解壓縮相對于壓縮將快的多。這對于需要進行一次壓縮,多次解壓縮的情況,是一個巨大的優點。1.2 Huffman編碼簡介我們把文件中一定位長的值看作是符號,比如把8位長的256種

8、值,也就是字節的256種值看作是符號。我們根據這些符號在文件中出現的頻率,對這些符號重新編碼。對于出現次數非常多的,我們用較少的位來表示,對于出現次數非常少的,我們用較多的位來表示。這樣一來,文件的一些部分位數變少了,一些部分位數變多了,由于變小的部分比變大的部分多,所以整個文件的大小還是會減小,所以文件得到了壓縮。要進行Huffman編碼,首先要把整個文件讀一遍,在讀的過程中,統計每個符號(我們把字節的256種值看作是256種符號的出現次數。然后根據符號的出現次數,建立Huffman 樹,通過Huffman樹得到每個符號的新的編碼。對于文件中出現次數較多的符號,它的Huffman編碼的位數比

9、較少。對于文件中出現次數較少的符號,它的Huffman編碼的位數比較多。然后把文件中的每個字節替換成他們新的編碼。建立Huffman樹:把所有符號看成是一個結點,并且該結點的值為它的出現次數。進一步把這些結點看成是只有一個結點的樹。每次從所有樹中找出值最小的兩個樹,為這兩個樹建立一個父結點,然后這兩個樹和它們的父結點組成一個新的樹,這個新的樹的值為它的兩個子樹的值的和。如此往復,直到最后所有的樹變成了一棵樹。我們就得到了一棵Huffman樹。通過Huffman樹得到Huffman編碼:這棵Huffman樹,是一棵二叉樹,它的所有葉子結點就是所有的符號,它的中間結點是在產生Huffman樹的過程

10、中不斷建立的。我們在Huffman樹的所有父結點到它的左子結點的路徑上標上0,右子結點的路徑上標上1。現在我們從根節點開始,到所有葉子結點的路徑,就是一個0和1的序列。我們用根結點到一個葉子結點路徑上的0和1的序列,作為這個葉子結點的Huffman編碼。我們來看一個例子。有一個文件的內容如下abbbbccccddde我們統計一下各個符號的出現次數,a b c d e1 4 4 3 1建立Huffman樹的過程如下圖所示. 通過最終的Huffman樹,我們可以得到每個符號的Huffman編碼。a 為110b 為00c 為01d 為10e 為111我們可以看到,Huffman樹的建立方法就保證了,

11、出現次數多的符號,得到的Huffman編碼位數少,出現次數少的符號,得到的Huffman編碼位數多。各個符號的Huffman編碼的長度不一,也就是變長編碼。對于變長編碼,可能會遇到一個問題,就是重新編碼的文件中可能會無法如區分這些編碼。比如,a的編碼為000,b的編碼為0001,c的編碼為1,那么當遇到0001時,就不知道0001代表ac,還是代表b。出現這種問題的原因是a的編碼是b的編碼的前綴。由于Huffman編碼為根結點到葉子結點路徑上的0和1的序列,而一個葉子結點的路徑不可能是另一個葉子結點路徑的前綴,所以一個Huffman編碼不可能為另一個Huffman編碼的前綴,這就保證了Huff

12、man編碼是可以區分的。為了在解壓縮的時候,得到壓縮時所使用的Huffman樹,我們需要在壓縮文件中,保存樹的信息,也就是保存每個符號的出現次數的信息。壓縮:讀文件,統計每個符號的出現次數。根據每個符號的出現次數,建立Huffman樹,得到每個符號的Huffman編碼。將每個符號的出現次數的信息保存在壓縮文件中,將文件中的每個符號替換成它的Huffman編碼,并輸出。解壓縮:得到保存在壓縮文件中的,每個符號的出現次數的信息。根據每個符號的出現次數,建立Huffman樹,得到每個符號的Huffman編碼。將壓縮文件中的每個Huffman編碼替換成它對應的符號,并輸出。2 gzip 所使用壓縮算法

13、的實現我們將gzip的實現分成很多個部分,一個個來說明,這樣做的原因見本文最后一部分。gzip 中所使用的各種實現技巧的出處或者靈感,gzip 的作者在源碼的注釋中進行了說明。2.1 尋找匹配串的實現為一個串尋找匹配串需要進行大量的匹配工作,而且我們還需要為很多很多個串尋找匹配串。所以gzip 在尋找匹配串的實現中使用哈希表來提高速度。要達到的目標是,對于當前串,我們要在它之前的窗口中,尋找每一個匹配長度達到最小匹配的串,并找出匹配長度最長的串。在gzip 中,最小匹配長度為3,也就是說,兩個串,最少要前3個字節相同,才能算作匹配。為什么最小匹配長度為3,將在后面說明。gzip 對遇到的每一個

14、串,首先會把它插入到一個“字典”中。這樣當以后有和它匹配的串,可以直接從“字典”中查出這個串。插入不是亂插,查也不是亂查。插入的時候,使用這個插入串的前三個字節,計算出插入的“字典”位置,然后把插入串的開始位置保存在這個“字典”位置中。查出的時候,使用查出串的前三個字節,計算出“字典”位置,由于插入和查出使用的是同一種計算方法,所以如果兩個串的前三個字節相同的話,計算出的“字典”位置肯定是相同的,所以就可以直接在該“字典”位置中,取出以前插入時,保存進去的那個串的開始位置。于是查出串,就找到了一個串,而這個串的前三個字節和自己的一樣(其實只是有極大的可能是一樣的,原因后面說明,所以就找到了一個

15、匹配串。如果有多個串,他們的前三個字節都相同,那么他們的“字典”位置,也都是相同的,他們將被鏈成一條鏈,放在那個“字典”位置上。所以,如果一個串,查到了一個“字典”位置,也就查到了一個鏈,所有和它前三個字節相同的串,都在這個鏈上。也就是說,當前串之前的所有匹配串被鏈在了一個鏈上,放在某個“字典”位置上。而當前串使用它的前三個字節,進行某種計算,就可以得到這個“字典”位置(得到了“字典”位置之后,它首先也把自己鏈入到這個鏈上,也就找到了鏈有它的所有匹配串的鏈,所以要找最長的匹配,也就是遍歷這個鏈上的每一個串,看和哪個串的匹配長度最大。下面我們更具體的說明,尋找匹配串的實現。我們前面所說的“字典”

16、,是一個數組,叫做head(為什么叫head,后面進行說明。我們前面所說的“字典”位置,放在一個叫做ins_h的變量中。我們前面所說的鏈,是在一個叫做prev的數組中。插入:當前字節為第strstart 個字節。通過第strstart,strstart+1,strstart+2,這三個字節,使用一個設計好的哈希函數算出ins_h,也就是插入的位置。然后將當前字節的位置,即strstart,保存在headins_h中。注意由strstart,strstart+1,strstart+2,這三個字節(也就是strstart開始處的串的頭三個字節,也就是當前字節和之后的兩個字節確定了ins_h。hea

17、dins_h中保存的又是strstart,也就是這個串開始的位置。判斷是否有匹配:當前串的前三個字節,使用哈希函數算出ins_h,這時如果headins_h的值不為空的話,那么headins_h中的值,便是之前保存在這里的另一個串的位置,并且這個串的前三個字節算出的ins_h,和當前串的前三個字節算出的ins_h相同。也就是說有可能有匹配。如果headins_h的值為空的話,那么肯定沒有匹配。gzip所使用的哈希函數:gzip 所使用的哈希函數,用三個字節來計算一個ins_h,這是由于最小匹配為三個字節。對于相同的三個字節,通過哈希函數得到的ins_h必然是相同的。而不同的三個字節,通過哈希函

18、數有可能得到同一個ins_h,不過這并不要緊,當gzip發現headins_h不空后,也就是說有可能有匹配串的話,會對鏈上的每一個串進行真正的串的比較。所以一個鏈上的串,只是前三個字節用哈希函數算出的值相同,而并不一定前三個字節都是相同的。但是這樣已經很大的縮小了需要進行串比較的范圍。我們來強調一下,前三個字節相同的串,必然在同一個鏈上。在同一個鏈上的,不一定前三個字節都相同。不同的三個字節有可能得到同一個結果的原因是,三個字節,一共24位,有224種可能值。而三個字節的哈希函數的計算結果為15位,有215種可能值。也就是說224種值,與215種值進行對應,必然是多對一的,也就是說,必然是有多

19、種三個字節的值,用這個哈希函數計算出的值都是相同的。而我們使用哈希函數的理由是,實際上,我們只是在一個窗口大小的范圍內(后面將會看到尋找匹配串,一個窗口的大小范圍是很有限的,能出現的三個字節的值組合情況也是很有限的,將遠遠小于224,使用合適的哈希函數是高效的。前三個字節相同的所有的串所在的鏈:headins_h 中的值,有兩個作用。一個作用,是一個前三個字節計算結果為ins_h的串的位置。另一個作用,是一個在prev數組中的索引,用這個索引在prev中,將找到前一個前三個字節計算結果為ins_h的串的位置。即prevheadins_h的值(不為空的話為前一個前三個字節計算結果為ins_h的串

20、的位置。prev的值,也有兩個作用。一個作用,是一個前三個字節計算結果為ins_h的串的位置。另一個作用,是一個在prev數組中的索引,用這個索引在prev中,將找到前一個前三個字節計算結果為ins_h的串的位子哈。即prev的值(不為空的話為前一個三個字節計算結果為ins_h的串的位置。直到prev為空,表示鏈結束。我們來舉一個例子,串,0abcd abce,abcf_abcg當處理到abcg的a時,由abcg的abc算出ins_h。這時的headins_h中為11,即串"abcf abcg"的開始位置。這時的prev11中為6,即串"abce abcf abc

21、g"的開始位置。這時的prev6中為1,即串"abcd abce abcf abcg"的開始位置。這時的prev1中為0。表示鏈結束了。我們看到所有頭三個字母為abc的串,被鏈在了一起,從head可以一直找下去,直到找到0。鏈的建立:gzip在每次處理當前串的時候,首先用當前串的前三個字節計算出ins_h,然后,就要把當前的串也插入到相應的鏈中,也就是把當前的串的位置,保存到headins_h 中,而此時, headins_h 中(不空的話為前一個串的開始位置。所以這時候需要把前一個串的位置,也就是原來的headins_h放入鏈中。于是把現在的headins_h的

22、值,用當前串的位置做索引,保存到prev 中。然后再把headins_h 賦值為當前串的位置。如果當前串的位置為strstart的話,那么也就是prevstrstart = headins_h;headins_h = strstart;就這樣,每次把一個串的位置加入到鏈中,鏈就形成了?，F在我們也就知道了,前三個字節計算得到同一ins_h的所有的串被鏈在了一起,headins_h為鏈頭,prev數組中放著的更早的串的位置。head數組和prev數組的名字,也正反應了他們的作用。鏈的特點:越向前(prev與當前處理位置之間的距離越大。比如,當前處理串,算出了ins_h,而且headins_h中的值

23、不空,那么headins_h就是離當前處理串距離最近的一個可能的匹配串,并且順著prev向前所找到的串,越來距離越遠。匹配串中的字節開始的串的插入:我們說過了,所有字節開始的串,都將被插入“字典”。對于確定了的匹配串,匹配串中的每個字節開始的串,仍要被插入“字典”,以便后面串可以和他們進行匹配。注意:對于文件中的第0字節,情況很特殊,它開始的串的位置為0。所以第0串的前三個字節計算出ins_h之后,在headins_h中保存的位置為0。而對是否有可能有匹配的判斷,就是通過headins_h不為0,并且headins_h的值為一個串的開始位置。所以第0字節開始的串,由于其特殊性,將不會被用來匹配

24、,不過這種情況只會出現在第0個字節,所以通常不會造成影響,即使影響,也會極小。例如,文件內容為jiurl jiurl找到的匹配情況如下,所括部分。jiurl jiurl2.2 懶惰啊匹配(lazy match對于當前字節開始的串,尋找到了最長匹配之后,gzip并不立即決定使用這個串進行替換。而是看看這個匹配長度是否滿意,如果匹配長度不滿意,而下一個字節開始的串也有匹配串的話,那么gzip就找到下一個字節開始的串的最長匹配,看看是不是比現在這個長。這叫懶惰啊匹配。如果比現在這個長的話,將不使用現在的這個匹配。如果比現在這個短的話,將確定使用現在的這個匹配。我們來舉個例子,串0abc bcde a

25、bcde處理到第10字節時,也就是"abcde"的a時,找到最長匹配的情況如下,所括部分。0abc bcde abcde這時,再看看下一個字節,也就是第11字節的情況,也就是'abcde"的b,找到最長匹配的情況如下,所括部分。0abc bcde abcde發現第二次匹配的匹配長度大,就不使用第一次的匹配串。我們也看到了如果使用第一次匹配的話,將錯過更長的匹配串。在滿足懶惰啊匹配的前提條件下,懶惰啊匹配不限制次數,一次懶惰啊匹配發現了更長的匹配串之后,仍會再進行懶惰啊匹配,如果這次懶匹配,發現了更長的匹配串,那么上一次的懶匹配找到的匹配串就不用了。進行懶惰

26、啊匹配是有條件的。進行懶惰啊匹配必須滿足兩個條件,第一,下一個處理字節開始的串,要有匹配串,如果下一個處理字節開始的串沒有匹配串的話,那么就確定使用當前的匹配串,不進行懶匹配。第二,當前匹配串的匹配長度,gzip不滿意,也就是當前匹配長度小于max_lazy_match(max_lazy_match在固定的壓縮級別下,有固定的值。討論:我們可以看到了做另外一次嘗試的原因。如果當前串有匹配就使用了的話,可能錯過更長匹配的機會。使用懶惰啊匹配會有所改善。不過從我簡單的分析來看,使用懶惰啊匹配對壓縮率的改善似乎是非常有限的。2.3 大于64KB的文件,窗口的實現窗口的實現:實際中,當前串(當前處理字

27、節開始的串只是在它之前的窗口中尋找匹配串的,也就是說只是在它之前的一定大小的范圍內尋找匹配串的。有這個限制的原因,將在后面說明。gzip 的窗口大小為WSIZE,32KB。內存中有一個叫window的緩沖區,大小為2個窗口的大小,也就是64KB。文件的內容將被讀到這個window中,我們在window上進行LZ77部分的處理,得到結果將放在其他緩沖區中。gzip 對window中的內容,從開始處開始,一個字節一個字節的向后處理。有一個指針叫strstart(其實是個索引,指向當前處理字節,當當前處理字節開始的串沒有匹配時,不做改動的輸出當前處理字節,strstart向后移動一個字節。當當前處理

28、字節開始的串找到了匹配時,輸出(匹配長度,相隔距離對,strstart向后移動匹配長度個字節。我們把strstart 到window結束的這部分內容,叫做lookahead buffer,超前查看緩沖區。這樣叫的原因是,在我們處理當前字節的時候,就需要讀出之后的字節來進行串的匹配。在一個變量lookahead 中,保存著超前查看緩沖區所剩的字節數。lookahead,最開始被初始化為整個讀入內容的大小,隨著處理的進行,strstart不斷后移,超前查看緩沖區不斷減小,lookahead的值也不斷的減小。我們需要限制查找匹配串的范圍為一個窗口的大小(這么做的原因后面說明,也就是說,只能在當前處理

29、字節之前的32KB的范圍內尋找匹配串。而,由于處理是在2個窗口大小,也就是64KB大小的緩沖區中進行的,所以匹配鏈上的串與當前串之間的距離是很有可能超過32KB的。那么gzip是如何來實現這個限制的呢?gzip 通過匹配時的判斷條件來實現這個限制。當當前串計算ins_h,發現headins_h值不為空時(headins_h為一個串的開始位置,說明當前串有可能有匹配串,把這個值保存在hash_head中。這時就要做一個限制范圍的判斷,strstart - hash_head <= 窗口大小, strstart-hash_head 是當前串和最近的匹配串之間的距離,(注意前面說過,鏈頭和當前

30、串的距離最近,越向前(prev與當前處理位置之間的距離越大,也就是說要判斷當前串和距離最近的匹配串之間的距離是否在一個窗口的范圍之內。如果不是的話,那么鏈上的其他串肯定更遠,肯定更不在一個窗口的范圍之內,就不進行匹配處理了。如果是在一個窗口的范圍之內的話,還需要在鏈上尋找最長的匹配串,在和每個串進行比較的時候,也需要判斷當前串和該串的距離是否超過一個窗口的范圍,超過的話,就不能進行匹配。實際中,gzip為了使代碼簡單點,距離限制要比一個窗口的大小還要小一點。小于64KB的文件:初始化的時候,會首先從文件中讀64KB的內容到window中。對于小于64KB的文件,整個文件都被讀入到window中

31、。在window上進行LZ77的處理,從開始直到文件結束。大于64KB的文件:每處理一個字節都要判斷lookahead < MIN_LOOKAHEAD ,也就是window中還沒有處理的字節是否還夠MIN_LOOKAHEAD ,如果不夠的話,就會導致fill_window(,從文件中讀內容到window中。由于我們一次最大可能使用的超前查看緩沖區的大小為,最大匹配長度(258個字節,后面進行說明加上最小匹配長度,也就是下一個處理字節開始的串,可以找到一個最大匹配長度的匹配,發生匹配之后,還要預讀一個最小匹配長度來計算之后的ins_h。不管是大于64KB的文件,還是小于64KB的文件,隨著

32、處理的進行,最終都要到文件的結束,在接近文件結束的時候,都會出現lookahead < MIN_LOOKAHEAD ,對于這種情況, fill_window( 讀文件,就再讀不出文件內容了,于是fill_window(會設置一個標志eofile,表示文件就要結束了,之后肯定會接著遇到lookahead < MIN_LOOKAHEAD ,不過由于設置了eofile 標志,就不會再去試圖讀文件到window中了。壓縮開始之前的初始化,會從文件中讀入64KB的內容到window中,窗口大小為32KB,也就是讀入2窗的內容到window中。我們把第一窗的內容叫做w1_32k,第二窗的內容叫

33、做w2_32k。壓縮不斷進行,直到lookahead < MIN_LOOKAHEAD,也就是處理到了64KB內容的接近結束部分,也就是如果再處理,超前查看緩沖區中的內容就可能不夠了。由于lookahead < MIN_LOOKAHEAD ,將執行fill_window(。fill_window( 判斷是否壓縮已經進行到了2窗內容快用完了,該把新的內容放進來了。如果是的話,fill_window( 把第二窗的內容w2_32k,復制到第一窗中,第一窗中的內容就被覆蓋掉了,然后對match_start,strstart之類的索引,做修正。然后更新匹配鏈的鏈頭數組,head,從頭到尾過一遍

34、,如果這個頭中保存的串的位置,在w2_32k中,就對這個串的位置做修正。如果這個頭中保存的串的位置,在w1_32k中,就不要了,設為空,因為第一窗的內容我們已經覆蓋掉了。然后更新prev數組,從頭到尾過一遍,如果某項的內容,在w2_32k中,就做修正。如果這項的內容,在w1_32k中,就不要了,設為空,因為第一窗的內容我們已經覆蓋掉了。最后fill_window(從文件中再讀出一窗內容,也就是讀出32KB的內容,復制到第二個窗中,注意第二個窗口中原來的內容,已經被復制到了第一個窗口中。就這樣,一窗窗的處理,直到整個文件結束。分析:到第二窗文件內容也快要處理完的時候,才會從文件中讀入新的內容。而

35、這時,第一窗中的所有串,對于當前處理字節和之后的字節來說,已經超出了一個窗口的距離,當前處理字節和之后的字節不能和第一窗的串進行匹配了,也就是說第一窗的內容已經沒有用了。所有插入字典的第一窗的串也已經沒有用了。所以覆蓋第一窗的內容是合理的,將字典中第一窗的串的開始位置都設為空也是合理的。將第二窗的內容復制到第一窗中,那么第二窗在字典中的所有索引都需要做相應的修正。由于第二窗的內容已經復制到了第一窗中,所以我們可以將新的內容讀入到第二窗中,新的內容之前的32KB的內容,就是原來的第二窗中的內容。而這時,做過修正的字典中,仍然有原來第二窗中所有串的信息,也就是說,新的內容,可以繼續利用前面一個窗口

36、大小的范圍之內的串,進行壓縮,這也是合理的。2.4 其他問題1現在來說明一下,為什么最小匹配長度為3個字節。這是由于,gzip 中,(匹配長度,相隔距離對中,"匹配長度"的范圍為3-258,也就是256種可能值,需要8bit來保存。"相隔距離"的范圍為0-32K,需要15bit來保存。所以一個(匹配長度,相隔距離對需要23位,差一位3個字節。如果匹配串小于3個字節的話,使用(匹配長度,相隔距離對進行替換,不但沒有壓縮,反而還會增大。所以保存(匹配長度,相隔距離對所需要的位數,決定了最小匹配長度至少要為3個字節。最大匹配長度為258的原因是,綜合各種因素,

37、決定用8位來保存匹配長度,8位的最大值為255。實際中,我們在(匹配長度,相隔距離對中的“匹配長度”保存的是,實際匹配長度-最小匹配長度,所以255對應的實際匹配長度為258。在進行匹配時,會對匹配長度進行判斷,保證到達最大匹配長度時,匹配就停止。也就是說,即使有兩個串的相同部分超過了最大匹配長度,也只匹配到最大匹配長度。保存相隔距離所用的位數和窗口大小是互相決定的,綜合兩方面各種因素,確定了窗口大小,也就確定了保存相隔距離所使用的位數。2.5 gzip 的LZ77部分的實現要點gzip 的LZ77 部分的實現主要在函數defalte( 中。所使用的緩沖區window 用來放文件中讀入的內容。

38、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中。lookahe

39、ad 中為返回的讀入字節數。使用window中的頭兩個字節,UPDATE_HASH,初始化ins_h。deflate( 中,一個處理循環中,首先INSERT_STRING 把當前串插入字典,INSERT_STRING 是一個宏,作用就是用哈希函數計算當前串的ins_h,然后把原來的headins_h中的內容,鏈入鏈中(放到prev中,同時把原來的headins_h保存在hash_head變量中,用來后面進行匹配判斷,然后把當前串的開始位置,保存在headins_h中。判斷hash_head中保存的內容不為空,說明匹配鏈上有內容。調用longest_match ( 尋找匹配鏈上的最長匹配。has

40、h_head中保存的內容為空,說明當前字節開始的串,在窗口中沒有匹配。由于使用了lazy match,使得判斷的情況更復雜。匹配串的輸出,或者是沒有匹配的字節的輸出,都是調用函數ct_tally(。對于匹配串,輸出之后,還需要為匹配串中的每個字節使用INSERT_STRING,把匹配串中每個字節開始的串都插入到字典中。ct_tally(中,把傳入的"沒有匹配的字節"或者是"匹配長度-3"放到l_buf中,然后為以后的Huffman編碼做統計次數的工作,如果傳入的是匹配情況,傳入的參數中會有相隔距離,把相隔距離保存在d_buf中。根據傳入的參數,可以判斷是

41、哪種情況,然后設置一個變量中相應的標志位,每8個標志位,也就是夠一個字節,就保存到flag_buf中。還有一些判斷,我們將在后面進行說明。2.6 分塊輸出LZ77 壓縮的結果放在,l_buf,d_buf,flag_buf 中。對于LZ77 的壓縮結果,可能使用一塊輸出或者分成多塊輸出(LZ77壓縮一定的部分之后,就進行一次塊輸出,輸出一塊。塊的大小不固定。輸出的時候,會對LZ77的壓縮結果,進行Huffman編碼,最終把Huffman編碼的結果輸出到outbuf緩沖區中。進行Huffman編碼,并輸出的工作,在flush_block( 中進行。在ct_tally(中進行判斷,如果滿足一些條件的

42、話,當從ct_tally(中返回之后,就會對現有的LZ77的結果,進行Huffman編碼,輸出到一個塊中。在整個文件處理結束,deflate(函數要結束的時候,會把LZ77的結果,進行Huffman編碼,輸出到一個塊中。在ct_tally(中,每當l_buf中的字節數(每個字節是一個沒有匹配的字節或者一個匹配長度增加0x1000,也就是4096的時候。將估算壓縮的情況,以判斷現在結束這個塊是否比較好,如果覺得比較好,就輸出一個塊。如果覺得不好,就先不輸出。而當l_buf滿了的時候,或者d_buf滿了的時候,將肯定對現有的LZ77壓縮的結果,進行Huffman編碼,輸出到一個塊中。決定輸出一塊的

43、話,會只針對這一塊的內容,建立Huffman樹,這一塊內容將會被進行Huffman編碼壓縮,并被輸出到outbuf中。如果是動態Huffman編碼,樹的信息也被輸出到outbuf中。輸出之后,會調用init_block(,初始化一個新塊,重新初始化一些變量,包括動態樹的結點被置0,也就是說,將為新塊將來的Huffman樹重新開始統計信息。輸出塊的大小是不固定的,首先在進行Huffman編碼之前,要輸出的內容的大小就是不固定,要看情況,進行Huffman編碼之后,就更不固定了。塊的大小不固定,那么解壓縮的時候,如何區分塊呢。編碼樹中有一個表示塊結束的結點, EOB,在每次輸出塊的最后,輸出這個結

44、點的編碼,所以解壓縮的時候,當遇到了這個結點就表明一個塊結束了。每個塊最開始的2位,用來指明本塊使用的是哪種編碼方式,00表示直接存儲,01表示靜態Huffman編碼,10表示動態Huffman編碼。接下來的1位,指明本塊是否是最后一塊,0表示不是,1表示是最后一塊。輸出一個塊,對現在字典中的內容沒有影響,下一個塊,仍將用之前形成的字典,進行匹配。2.7 靜態Huffman編碼與動態Huffman編碼靜態Huffman編碼就是使用gzip自己預先定義好了一套編碼進行壓縮,解壓縮的時候也使用這套編碼,這樣不需要傳遞用來生成樹的信息。動態Huffman編碼就是使用統計好的各個符號的出現次數,建立H

45、uffman樹,產生各個符號的Huffman編碼,用這產生的Huffman編碼進行壓縮,這樣需要傳遞生成樹的信息。gzip 在為一塊進行Huffman編碼之前,會同時建立靜態Huffman樹,和動態Huffman樹,然后根據要輸出的內容和生成的Huffman樹,計算使用靜態Huffman樹編碼,生成的塊的大小,以及計算使用動態Huffman樹編碼,生成塊的大小。然后進行比較,使用生成塊較小的方法進行Huffman編碼。對于靜態樹來說,不需要傳遞用來生成樹的那部分信息。動態樹需要傳遞這個信息。而當文件比較小的時候,傳遞生成樹的信息得不償失,反而會使壓縮文件變大。也就是說對于文件比較小的時候,就可

46、能會出現使用靜態Huffman編碼比使用動態Huffman編碼,生成的塊小。2.8 編碼的產生deflate算法在Huffman樹的基礎上,又加入了幾條規則,我們把這樣的樹稱作deflate樹,使得只要知道所有位長上的結點的個數,就可以得到所有結點的編碼。這樣做的原因是,減少需要存放在壓縮壓縮文件中的用來生成樹的信息。要想弄明白,deflate如何生成Huffman 編碼,一定要弄明白一些Huffman樹,和deflate樹的性質,下面內容是對Huffman樹和deflate 樹做了些簡單研究得到的。Huffman樹的性質1 葉子結點為n的話,那么整顆樹的總結點為2n-1。簡單證明說明,先證,

47、最小的樹,也就是只有三個結點,一個根節點,兩個葉子節點的樹符合。然后在任何符合的樹上做最小的添加得到的樹也符合。所以都符合。2 最左邊的葉子結點的編碼為0,但是位長不一定。deflate中增加了附加條件的huffman樹的性質1 同樣位長的葉子結點的編碼值為連續的,右面的總比左面的大1。2 (n+1位長最左面的葉子結點(也就是編碼值最小的葉子結點的值為n位長最右面的葉子結點(也就是編碼值最大的葉子結點的值+1,然后變長一位(也就是左移1位。3 n位長的葉子結點,最右面的葉子結點(也就是編碼值最大的葉子結點的值為最左面的葉子結點(也就是編碼值最小的葉子結點的值加上n位長的葉子結點的個數減1。4

48、(n+1位長最左面的葉子結點(也就是編碼值最小的葉子結點的值為n位長最左面的葉子結點(也就是編碼值最小的葉子結點的值加上n位長的葉子結點的個數,然后變長一位(也就是左移1位。還有一些樹的性質,比如,樹的某一深度上最大可能編碼數。從所有編碼的位長,得到所有編碼的編碼:統計每個位長上的編碼個數放在bl_count中。根據bl_count 中的值,計算出每個位長上的最小編碼值,放在next_code 中。計算方法為,code = (code + bl_countbits-1 << 1;理由是deflate二叉樹的性質,(n+1位長最左面的葉子結點(也就是編碼值最小的葉子結點的值為n位長最

49、左面的葉子結點(也就是編碼值最小的葉子結點的值加上n位長的葉子結點的個數,然后變長一位(也就是左移1位。然后按照代碼值的順序,為所有的代碼編碼。編碼方法為,某一位長對應的next_coden,最開始是這個位長上最左邊的葉子結點的編碼,然后+,就是下一個該位長上下一個葉子結點的編碼,依次類推,直到把這個位長上的葉子結點編碼完。實際上的編碼為bi_reverse(next_code。這樣編碼的理由是,deflate二叉樹的性質。2.9 5棵樹一共有5棵樹static_ltree,static_dtree,dyn_ltree,dyn_dtree,bl_tree。對于所有的樹,一個葉子結點表示的符號的

50、值為n的話,那么這個符號對應的葉子結點放在treen 中,比如static_ltree 的葉子結點'a' 的值為十進制97,那么'a'的葉子結點就放在static_ltree97 。static_ltree 靜態Huffman編碼時,用來對沒有改動的字節和匹配長度進行編碼的樹。static_dtree 靜態Huffman編碼時,用來對相隔距離進行編碼的樹。dyn_ltree 動態Huffman編碼時,用來對沒有改動的字節和匹配長度進行編碼的樹。dyn_dtree 動態Huffman編碼時,用來對相隔距離進行編碼的樹。bl_tree 動態Huffman編碼時,用來

51、對解壓縮時用來產生dyn_ltree和dyn_dtree的信息進行編碼的樹。靜態樹在初始化的時候,為每個葉子結點直接產生編碼。動態樹,每次要輸出一塊的內容,就根據這一塊的內容,生成動態樹,再根據生成的動態樹,為每個葉子結點產生編碼。每次要輸出一塊的內容時,會計算用靜態樹編碼得到的塊的大小,和用動態樹編碼得到的塊的大小,然后誰產生的塊小就用誰。用靜態編碼的話,就使用static_ltree,static_dtree,來進行編碼輸出。用動態編碼的話,就使用dyn_ltree,dyn_dtree,bl_tree 來進行編碼輸出。2.10 葉子結點ltree (用來對沒有改動的字節和匹配長度進行編碼的

52、樹,靜態,動態都一樣的葉子結點一共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

53、次,之后的3位指明重復次數。18 重復編碼位長為0的,11-138次,之后的7位指明重復次數。2.11 靜態Huffman編碼初始化base_length,length_code,base_dist,dist_code。base_length為,29個匹配長度范圍的,每個范圍開始的長度值。length_code為,256 個可能的匹配長度所屬的范圍。比如,base_length9=0xa,表示第9個范圍的開始值為0xa。length_code11=9,表示匹配長度為11的匹配長度,屬于第9個范圍。base_dist,30個匹配距離范圍的,每個范圍的開始的值,就是每個范圍內最小的值。dist_c

54、ode,這個有點特殊,一共有32K個取值,這里把這32K種值,分成了兩大類,0-255這256個值為一類,這時他們直接為dist_code的索引。256-32K為一類,這時他們的去掉低7位,和最高位,剩下的8位為索引,8位剛好索引256項。能這么做的原因是,首先最大32K的距離最大需要15位,所以16位的最高位總不會用,其次剩下這些范圍的邊界至少都為二進制1 000 0000 的整數倍。比如匹配距離為10,小于256,所以它屬于類dist_code10=6,第6類。匹配距離為10K ,大于256,所以它屬于類dist_code256+10K>>7=dist_code256+1024

55、0>>7=dist_code256+80=dist_code336=0x1a=26,屬于26類,26類的范圍為8193-12288,10240就是在這個范圍內。指定了每個literal的位長。(一共將有288個literal。包括256個字節值+1個EOB+29個匹配長度范圍=286個。多2個是為了滿樹。并統計每個位長上的literal個數放在bl_count中。根據bl_count 中的值,計算出每個位長上的最小編碼值,放在next_code 中。計算方法為,code = (code + bl_countbits-1 << 1;理由是deflate二叉樹的性質,(n+

56、1位長最左面的葉子結點(也就是編碼值最小的葉子結點的值為n位長最左面的葉子結點(也就是編碼值最小的葉子結點的值加上n位長的葉子結點的個數,然后變長一位(也就是左移1位。然后從literal值的0,到literal值的最大。為每個literal編碼。編碼方法為,某一位長對應的next_coden,最開始是這個位長上最左邊的葉子結點的編碼,然后+,就是下一個該位長上下一個葉子結點的編碼,依次類推,直到把這個位長上的葉子結點編碼完。實際上的編碼為bi_reverse(next_code。比如treen.Code = bi_reverse(next_codelen+, len;此時next_codel

57、en 值為二進制00110000 即0x30treen.Code 最后被賦值為二進制00001100 即0x0c這樣我們就得到了static_ltree,它以literal的值為索引,存放著literal對應的編碼。比如'a' 的值為十進制97,static_ltree97.code=0x0089 static_ltree97.len=8。說明a的編碼為二進制10001001。為static_dtree編碼。這個編碼很簡單,由于所有結點都是5位長的(指定的,所以根據deflate二叉樹性質,最左邊的葉子節點編碼為0,之后每次加1即可,直到編完所有葉子結點。注意這里也要bi_reverse(一下。也就是說,編碼為"從樹根開始到一個葉子結點的路徑對應的位流"的逆位流。用Huffman編碼對LZ77處理結果進行編碼輸出。這時,l_buf中每個字節為literal或者匹配長度-MIN_MATCH。d_buf為匹配距離,每項為16位。flag_buf中每