ZIP壓縮算法詳細分析及解壓實例解釋

最近自己實現(xiàn)了一個ZIP壓縮數(shù)據(jù)的解壓程序，覺得有必要把ZIP壓縮格式進行一下詳細總結(jié)，數(shù)據(jù)壓縮是一門通信原理和計算機科學都會涉及到的學科，在通信原理中，一般稱為信源編碼，在計算機科學里，一般稱為數(shù)據(jù)壓縮，兩者本質(zhì)上沒啥區(qū)別，在數(shù)學家看來，都是映射。一方面在進行通信的時候，有必要將待傳輸?shù)臄?shù)據(jù)進行壓縮，以減少帶寬需求；另一方面，計算機存儲數(shù)據(jù)的時候，為了減少磁盤容量需求，也會將文件進行壓縮，盡管現(xiàn)在的網(wǎng)絡帶寬越來越高，壓縮巳經(jīng)不像90年代初那個時候那么迫切，但在很多場合下仍然需要，其中一個原因是壓縮后的數(shù)據(jù)容量減小后，磁盤訪問IO的時間也縮短，盡管壓縮和解壓縮過程會消耗CPU資源，但是CPU計算資源增長得很快，但是磁盤IO資源卻變化得很慢，比如目前主流的SATA硬盤仍然是7200轉(zhuǎn)，如果把磁盤的IO壓力轉(zhuǎn)化到CPU上，總體上能夠提升系統(tǒng)運行速度。壓縮作為一種非常典型的技術，會應用到很多很多場合下，比如文件系統(tǒng)、數(shù)據(jù)庫、消息傳輸、網(wǎng)頁傳輸?shù)鹊雀黝悎龊?。盡管壓縮里面會涉及到很多術語和技術，但無需擔心，博主盡量將其描述得通俗易懂。另外，本文涉及的壓縮算法非常主流并且十分精巧，理解了ZIP的壓縮過程，對理解其它相關的壓縮算法應該就比較容易了。1、引子壓縮可以分為無損壓縮和有損壓縮，有損，指的是壓縮之后就無法完整還原原始信息，但是壓縮率可以很高，主要應用于視頻、話音等數(shù)據(jù)的壓縮，因為損失了一點信息，人是很難察覺的，或者說，也沒必要那么清晰照樣可以看可以聽；無損壓縮則用于文件等等必須完整還原信息的場合，ZIP自然就是一種無損壓縮，在通信原理中介紹數(shù)據(jù)壓縮的時候，往往是從信息論的角度出發(fā)，引出香農(nóng)所定義的熵的概念，這方面的介紹實在太多，這里換一種思路，從最原始的思想出發(fā)，為了達到壓縮的目的，需要怎么去設計算法。而ZIP為我們提供了相當好的案例。盡管我們不去探討信息論里面那些復雜的概念，不過我們首先還是要從兩位信息論大牛談起。因為是他們奠基了今天大多數(shù)無損數(shù)據(jù)壓縮的核心，包括ZIP、RAR、GZIP、GIF、PNG等等大部分無損壓縮格式。這兩位大牛的名字分別是JacobZiv和AbrahamLempel，是兩位以色列人，在1977年的時候發(fā)表了一篇論文《AUniversalAlgorithmforSequentialDataCompression》，從名字可以看出，這是一種通用壓縮算法，所謂通用壓縮算法，指的是這種壓縮算法沒有對數(shù)據(jù)的類型有什么限定。不過論文我覺得不用仔細看了，因為博主作為一名通信專業(yè)的PHD，看起來也焦頭爛額，不過我們后面可以看到，它的思想還是很簡單的，之所以看起來復雜，主要是因為IEEE的某些雜志就是這個特點，需要從數(shù)學上去證明，這種壓縮算法到底有多優(yōu)，比如針對一個各態(tài)歷經(jīng)的隨機序列（不用追究什么叫各態(tài)歷經(jīng)隨機序列），經(jīng)過這樣的壓縮算法后，是否可以接近信息論里面的極限（也就是前面說的熵的概念）等等，不過在理解其思想之前，個人認為沒必要深究這些東西，除非你要發(fā)論文。這兩位大牛提出的這個算法稱為LZ77，兩位大牛過了一年又提了一個類似的算法，稱為LZ78,思想類似，ZIP這個算法就是基于LZ77的思想演變過來的，但ZIP對LZ77編碼之后的結(jié)果又繼續(xù)進行壓縮，直到難以壓縮為止。除了LZ77、LZ78，還有很多變種的算法，基本都以LZ開頭，如LZW、LZO、LZMA、LZSS、LZR、LZB、LZH、LZC、LZT、LZMW、LZJ、LZFG等等，非常多，LZW也比較流行，GIF那個動畫格式記得用了LZW。我也寫過解碼程序，以后有時間可以再寫一篇，但感覺跟LZ77這些類似，寫的必要性不大。ZIP的作者是一個叫PhilKatz的人，這個人算是開源界的一個具有悲劇色彩的傳奇人物。雖然二三十年前，開源這個詞還沒有現(xiàn)在這樣風起云涌，但是總有一些具有黑客精神的牛人，內(nèi)心里面充滿了自由，無論他處于哪個時代。PhilKatz這個人是個牛逼程序員，成名于DOS時代，我個人也沒有經(jīng)歷過那個時代，我是從Windows98開始接觸電腦的，只是從書籍中得知，那個時代網(wǎng)速很慢，撥號使用的是只有幾十Kb（比特不是字節(jié)）的貓，56Kb實際上是這種貓的最高速度，在ADSL出現(xiàn)之后，這種技術被迅速淘汰。當時記錄文件的也是硬盤，但是在電腦之間拷貝文件的是軟盤，這個東西我大一還用過，最高容量記得是1.44MB，這還是200X年的軟盤，以前的軟盤容量具體多大就不知道了，PhilKatz上網(wǎng)的時候還不到1990年，WWW實際上就沒出現(xiàn)，瀏覽器當然是沒有的，當時上網(wǎng)干嘛呢？基本就是類似于網(wǎng)管敲各種命令，這樣實際上也可以聊天、上論壇不是嗎，傳個文件不壓縮的話肯定死慢死慢的，所以壓縮在那個時代很重要。當時有個商業(yè)公司提供了一種稱為ARC的壓縮軟件，可以讓你在那個時代聊天更快，當然是要付費的，PhilKatz就感覺到不爽，于是寫了一個PKARC，免費的，看名字知道是兼容ARC的，于是網(wǎng)友都用PKARC了，ARC那個公司自然就不爽，把哥們告上了法庭，說牽涉了知識產(chǎn)權等等，結(jié)果PhilKatz坐牢了。。。牛人就是牛人，在牢里面冥思苦想，決定整一個超越ARC的牛逼算法出來，牢里面就是適合思考，用了兩周就整出來的，稱為PKZIP，不僅免費，而且這次還開源了，直接公布源代碼，因為算法都不一樣了，也就不涉及到知識產(chǎn)權了，于是ZIP流行開來，不過PhilKatz這個人沒有從里面賺到一分錢，還是窮困潦倒，因為喝酒過多等眾多原因，2000年的時候死在一個汽車旅館里。英雄逝去，精神永存，現(xiàn)在我們用UE打開ZIP文件，我們能看到開頭的兩個字節(jié)就是PK兩個字符的ASCII碼。2、一個案例的入門思考好了，PhilKatz在牢里面到底思考了什么？用什么樣的算法來壓縮數(shù)據(jù)呢？我們想一個簡單的例子：生，容易。活，容易。生活，不容易。上面這句話假如不壓縮，如果使用Unicode編碼，每個字會用2個字節(jié)表示。為什么是兩個字節(jié)呢？Unicode是一種國際標準，把常見各國的字符，比如英文字符、日文字符、韓文字符、中文字符、拉丁字符等等全部制定了一個標準，顯然，用2個字節(jié)可以最多表示2^16=65536個字符，那么65536就夠了嗎？生僻字其實是很多的，比如光康熙字典里面收錄的漢字就好幾萬，所以實際上是不夠的，那么是不是擴到4個字節(jié)？也可以，這樣空間倒是變大了，可以收錄更多字符，但一方面擴到4個字節(jié)就一定保證夠嗎？另一方面，4個字節(jié)是不是太浪費空間了，就為了那些一般情況都不會出現(xiàn)的生僻字？所以，一般情況下，使用2個字節(jié)表示，當出現(xiàn)生僻字的時候，再使用4個字節(jié)表示。這實際上就體現(xiàn)了信息論中數(shù)據(jù)壓縮基本思想，出現(xiàn)頻繁的那些字符，表示得短一些；出現(xiàn)稀少的，可以表示得長些（反正一般情況下也不會出現(xiàn)），這樣整體長度就會減小。除了。nicode，ASCII編碼是針對英文字符的編碼方案，用1個字節(jié)即可，除了這兩種編碼方案，還有很多地區(qū)性的編碼方案，比如GB2312可以對中文簡體字進行編碼，Big5可以對中文繁體字進行編碼。兩個文件如果都使用一種編碼方案，那是沒有問題的，不過考慮到國際化，還是盡量使用Unicode這種國際標準吧。不過這個跟ZIP沒啥關系，純屬背景介紹。好了，回到我們前面說的例子，一共有17個字符（包括標點符號），如果用普通Unicode表示，一共是17*2=34字節(jié)?？刹豢梢詨嚎s呢？所有人一眼都可以看出里面出現(xiàn)了很多重復的字符，比如里面出現(xiàn)了好多次容易（實際上是容易加句號三個字符）這個詞，第一次出現(xiàn)的時候用普通的Unicode，第二次出現(xiàn)的''容易?！眲t可以用（距離、長度）表示，距離的意思是接下來的字符離前面重復的字符隔了幾個，長度則表示有幾個重復字符，上面的例子的第二個''容易?！本捅硎緸椋?,3），就是距離為5個字符，長度是3，在解壓縮的時候，解到這個地方的時候，往前跳5個字符，把這個位置的連續(xù)3個字符拷貝過來就完成了解壓縮，這實際上不就是指針的概念？沒有錯，跟指針很類似，不過在數(shù)據(jù)壓縮領域，一般稱為字典編碼，為什么叫字典呢，當我們?nèi)ゲ橐粋€字的時候，我們總是先去目錄查找這個字在哪一頁，再翻到那一頁去看，指針不也是這樣，指針不就是內(nèi)存的地址，要對一個內(nèi)存進行操作，我們先拿到指針，然后去那塊內(nèi)存去操作。所謂的指針、字典、索引、目錄等等術語，不同的背景可能稱呼不同，但我們要理解他們的本質(zhì)。如果使用（5,3）這種表示方法，原來需要用6個字節(jié)表示，現(xiàn)在只需要記錄5和3即可。那么，5和3怎么記錄呢？一種方法自然還是可以用Unicode，那么就相當于節(jié)省了2個字節(jié)，但是有兩個問題，第一個問題是解壓縮的時候怎么知道是正常的5和3這兩個字符，還是這只是一個特殊標記呢？所以前面還得加一個標志來區(qū)分一下，到底接下來的Unicode碼是指普通字符，還是指距離和長度，如果是普通Unicode，則直接查Unicode碼表，如果是距離和長度，則往前面移動一段距離，拷貝即可。第二個問題，還是壓縮程度不行，這么一弄，感覺壓縮不了多少，如果重復字符比較長那倒是比較劃算，因為反正''距離+長度”就夠了，但比如這個例子，如果5和3前面加一個特殊字節(jié)，豈不是又是3個字節(jié)，那還不如不壓縮。咋辦呢？能不能對（5,3）這種整數(shù)進行再次壓縮？這里就利用了我們前面說的一個基本原則：出現(xiàn)的少的整數(shù)多編一些比特，出現(xiàn)的多的整數(shù)少編一些比特。那么，比如3、4、5、6、7、8、9這些距離誰出現(xiàn)得多？誰出現(xiàn)的少呢？誰知道？壓縮之前當然不知道，不過掃描一遍不就知道了？比如，后面那個重復的字符串''容易?！卑凑涨懊娴囊?guī)則可以表示為（7,3）,即離前面重復的字符串距離為7,長度為3。（7,3）指著前面跟自己一樣那個字符串。那么，為什么不指著第一個''容易?！币钢诙€''容易。”呢？如果指著第一個，那就不是（7,3）了，就是（12,3）了。當然，表示為（12,3）也可以解壓縮，但是有一個問題，就是12這個值比7大，大了又怎么了？我們在生活中會發(fā)現(xiàn)一些普遍規(guī)律，重復現(xiàn)象往往具有局部性。比如，你跟一個人說話，你說了一句話以后，往往很快會重復一遍，但是你不會隔了5個小時又重復這句話，這種特點在文件里面也存在著，到處都是這種例子，比如你在編程的時候，你定義了一個變量intnCount，這個nCount一般你很快就會用到，不會離得很遠。我們前面所說的距離代表了你隔了多久再說這句話，這個距離一般不大，既然如此，應該以離當前字符串距離最近的那個作為記錄的依據(jù)（也就是指向離自己最近那個重復字符串），這樣的話，所有的標記都是一些短距離，比如都是3、4、5、6、7而不會是3、5、78、965等等，如果大多數(shù)都是一些短距離，那么這些短距離就可以用短一些的比特表示，長一些的距離不太常見，則用一些長一些的比特表示。這樣，總體的表示長度就會減少。好了，我們前面得到了（5,3）、（7、3）這種記錄重復的表示，距離有兩種：5、7；長度只有1種：3。咋編碼？越短越好。既然表示的比特越短越好，3表示為0、5表示為10、7表示為11，行不行？這樣（5,3）,（7,3）就只需要表示為100、110,這樣豈不是很短？貌似可以，貌似很高效。但解壓縮遇到10這兩個比特的時候，怎么知道10表示5呢？這種表示方法是一個映射表，稱為碼表。我們設計的上面這個例子的碼表如下：3-->05-->107-->11這個碼表也得傳過去或者記錄在壓縮文件里才行啊，否則無法解壓縮，但會不會記錄了碼表以后整體空間又變大了，會不會起不到壓縮的作用？而且一個碼表怎么記錄？碼表記錄下來也是一堆數(shù)據(jù)，是不是也需要編碼？碼表是否可以繼續(xù)壓縮？那豈不是又需要新的碼表？壓縮會不會是一個永無止境的過程？作為一個入門級的同學，大概想到這兒就不容易想下去了。3、ZIP中的LZ編碼思想上面我們說的重復字符串用指針標記記錄下來，這種方法就是LZ這兩個人提出來的，理解起來比較簡單。后面分析（5,3）這種指針標記應該怎么編碼的時候，就涉及到一種非常廣泛的編碼方式，Huffman編碼，Huffman大致和香農(nóng)是一個時代的人，這種編碼方式是他在MIT讀書的時候提出來的。接下來，我們來看看ZIP是怎么做的。以上面的例子，一個很簡單的示意圖如下：可以看出，ZIP中使用的LZ77算法和前面分析的類似，當然，如果仔細對比的話，ZIP中使用的算法和LZ提出來的LZ77算法其實還是有差異的，不過我建議不用仔細去扣里面的差異，思想基本是相同的，我們后面會簡要分析一下兩者的差異。LZ77算法一般稱為''滑動窗口壓縮”，我們前面說過，該算法的核心是在前面的歷史數(shù)據(jù)中尋找重復字符串，但如果要壓縮的文件有100MB，是不是從文件頭開始找？不是，這里就涉及前面提過的一個規(guī)律，重復現(xiàn)象是具有局部性的，它的基本假設是，如果一個字符串要重復，那么也是在附近重復，遠的地方就不用找了，因此設置了一個滑動窗口，ZIP中設置的滑動窗口是32KB，那么就是往前面32KB的數(shù)據(jù)中去找，這個32KB隨著編碼不斷進行而往前滑動。當然，理論上講，把滑動窗口設置得很大，那樣就有更大的概率找到重復的字符串，壓縮率不就更高了？初看起來如此，找的范圍越大，重復概率越大，不過仔細想想，可能會有問題，一方面，找的范圍越大，計算量會增大，不顧一切地增大滑動窗口，甚至不設置滑動窗口，那樣的軟件可能不可用，你想想，現(xiàn)在這種方式，我們在壓縮一個大文件的時候，速度都巳經(jīng)很慢了，如果增大滑動窗口，速度就更慢，從工程實現(xiàn)角度來說，設置滑動窗口是必須的；另一方面，找的范圍越大，距離越遠，出現(xiàn)的距離很多，也不利于對距離進行進一步壓縮吧，我們前面說過，距離和長度最好出現(xiàn)的值越少越好，那樣更好壓縮，如果出現(xiàn)的很多，如何記錄距離和長度可能也存在問題。不過，我相信滑動窗口設置得越大，最終的結(jié)果應該越好一些，不過應該不會起到特別大的作用，比如壓縮率提高了5%，但計算量增加了10倍，這顯然有些得不償失。在第一個圖中，''容易?！笔且粋€重復字符串，距離distance=5,字符串長度length=3。當對這三個字符壓縮完畢后，接下來滑動窗口向前移動3個字符，要壓縮的是''我...”這個字符串，但這個串在滑動窗口內(nèi)沒找到，所以無法使用distance+length的方式記錄。這種結(jié)果稱為literaloliteral的中文含義是原義的意思，表示沒有使用distance+length的方式記錄的那些普通字符。literal是不是就用原始的編碼方式，比如Unicode方式表示？ZIP里不是這么做的，ZIP把literal認為也是一個數(shù)，盡管不能用distance+length表示，但不代表不可以繼續(xù)壓縮。另外，如果'我"出現(xiàn)在了滑動窗口內(nèi)，是不是就可以用distance+length的方式表示？也不是，因為一個字出現(xiàn)重復，不值得用這種方式表示，兩個字呢？distance+length就是兩個整數(shù)，看起來也不一定值得，ZIP中確實認為2個字節(jié)如果在滑動窗口內(nèi)找到重復，也不管，只有3個字節(jié)以上的重復字符串，才會用distance+length表示，重復字符串的長度越長越好，因為不管多長，都用distance+length表示就行了。這樣的話，一段字符串最終就可以表示成literal、distance+length這兩種形式了。LZ系列算法的作用到此為止，下面，PhilKatz考慮使用Huffman對上面的這些LZ壓縮后的結(jié)果進行二次壓縮。個人認為接下來的過程才是ZIP的核心，所以我們要熟悉一下Huffman編碼。4、ZIP中的Huffman編碼思想上面LZ壓縮結(jié)果有三類（literal、distance、length），我們拿出distance一類來舉例。distance代表重復字符串離前一個一模一樣的字符串之間的距離，是一個大于0的整數(shù)。如何對一個整數(shù)進行編碼呢？一種方法是直接用固定長度表示，比如采用計算機里面描述一個4字節(jié)整數(shù)那樣去記錄，這也是可以的，主要問題當然是浪費存儲空間，在ZIP中，distance這個數(shù)表示的是重復字符串之間的距離，顯然，一般而言，越小的距離，出現(xiàn)的數(shù)量可能越多，而越大的距離，出現(xiàn)的數(shù)量可能越少，那么，按照我們前面所說的原則，小的值就用較少比特表示，大的值就用較多比特表示，在我們這個場景里,distance當然也不會無限大，比如不會超過滑動窗口的最大長度，假如對一個文件進行LZ壓縮后，得到的distance值為：3、6、4、3、4、3、4、3、5這個例子里，3出現(xiàn)了4次，4出現(xiàn)了3次，5出現(xiàn)了1次，6出現(xiàn)了1次。當然，不同的文件得到的結(jié)果不同，這里只是舉一個典型的例子，因為只有4種值，所以我們沒有必要對其它整數(shù)編碼。只需要對這4個整數(shù)進行編碼即可。那么，怎么設計一個算法，符合3的編碼長度最短？6的編碼長度最長這種直觀上可行的原則（我們并沒有說這是理論上最優(yōu)的方式）呢？看起來似乎很難想出來。我們先來簡化一下，用固定長度表示。這里有4個整數(shù)，只要使用2個比特表示即可。于是這樣表示就很簡單：00-->3；01-->4；10-->5;11-->6o00、01這種編碼結(jié)果稱為碼字，碼字的平均長度是2。上面這個對應關系即為碼表，在壓縮時，需要將碼表放在最前面，后面的數(shù)字就用碼字表示，解碼時，先把碼表記錄在內(nèi)存里，比如用一個哈希表記錄下來，解壓縮時，遇到00，就解碼為3等等。因為出現(xiàn)了9個數(shù)，所以全部碼字總長度為18個比特。（我們暫時不考慮記錄碼表到底要占多少空間）想要編碼結(jié)果更短，因為3出現(xiàn)的最多，所以考慮把3的碼字縮短點，比如3是不是可以用1個比特表示，這樣才算縮短吧，因為0和1只是二進制的一個標志，所以用0還是1沒有本質(zhì)區(qū)別，那么，我們暫定把3用比特0表示。那么，4、5、6還能用0開頭的碼字表示呢？這樣會存在問題，因為4、5、6的編碼結(jié)果如果以0開頭，那么，在解壓縮的時候，遇到比特0，就不知道是表示3還是表示4、5、6了，就無法解碼，當然，似乎理論上也不是不可以，比如可以往后解解看，比如假定0表示3的條件下往后解，如果無效則說明這個假設不對，但這種方式很容易出現(xiàn)兩個字符串的編碼結(jié)果是一樣的，這個誰來保證？所以，4、5、6都得以1開頭才行，那么，按照這個原則，4用1個比特也不行，因為5、6要么以0開頭，要么以1開頭，就無法編碼了，所以我們將4的碼字增加至2個比特，比如10，于是我們得到了部分碼表：0-->3；10-->4。按照這個道理，5、6既不能以0開頭，也不能以10開頭了，因為同樣存在無法解碼的問題，所以5應該以11開頭，就定為11行不行呢？也不行，因為6就不知道怎么編碼了，6也不能以0開頭，也不能以10、11開頭，那就無法表示了，所以，迫不得巳，我們必須把5擴展一位，比如110，那么，6顯然就可以用111表示了，反正也沒有其他數(shù)了。于是我們得到了最終的碼表：0-->3；10-->4；110-->5；111-->6?？雌饋?，編碼結(jié)果只能是這樣了，我們來算一下，碼字的總長度減少了沒有，原來的9個數(shù)是3、6、4、3、4、3、4、3、5，分別對應的碼字是：0、111、10、0、10、0、10、0、110算一下，總共16個比特，果然比前面那種方式變短了。我們在前面的設計過程中，是按照這些值出現(xiàn)次數(shù)由高到底的順序去找碼字的，比如先確定3,再確定4、5、6等等。按照一個碼字不能是另一個碼字的前綴這一規(guī)則，逐步獲得所有的碼字。這種編碼規(guī)則有一個專用術語，稱為前綴碼oHuffman編碼基本上就是這么做的，把出現(xiàn)頻率排個序，然后逐個去找，這個逐個去找的過程，就引入了二叉樹。不過Huffman的算法一般是從頻率由低到高排序，從樹的下面依次往上合并，不過本質(zhì)上沒區(qū)別，理解思想即可。上面的結(jié)果可以用一顆二叉樹表示為下圖：這棵樹也稱為碼樹，其實就是碼表的一種形式化描述，每個節(jié)點（除了葉子節(jié)點）都會分出兩個分支，左分支代表比特0，右邊分支代表1，從根節(jié)點到葉子節(jié)點的一個比特序列就是碼字。因為只有葉子節(jié)點可以是碼字，所以這樣也符合一個碼字不能是另一個碼字的前綴這一原則。說到這里，可以說一下另一個話題，就是一個映射表map在內(nèi)存中怎么存儲，沒有相關經(jīng)驗的可以跳過，map實現(xiàn)的是key-->value這樣的一個表，map的存儲一般有哈希表和樹形存儲兩類，樹形存儲就可以采用上面這棵樹，樹的中間節(jié)點并沒有什么含義，葉子節(jié)點的值表示value，從根節(jié)點到葉子節(jié)點上分支的值就是key，這樣比較適合存儲那些key由多個不等長字符組成的場合，比如key如果是字符串，那么把二叉樹的分支擴展很多，成為多叉樹，每個分支就是a,b,c,d這種字符，這棵樹也就是Trie樹，是一種很好使的數(shù)據(jù)結(jié)構(gòu)。利用樹的遍歷算法，就實現(xiàn)了一個有序Map。好了，我們理解了Huffman編碼的思想，我們來看看distance的實際情況。ZIP中滑動窗口大小固定為32KB，也就是說，distance的值范圍是1-32768。那么，通過上面的方式，統(tǒng)計頻率后，就得到32768個碼字，按照上面這種方式可以構(gòu)建出來。于是我們會遇到一個最大的問題，那就是這棵樹太大了，怎么記錄呢？好了，個人認為到了ZIP的核心了，那就是碼樹應該怎么縮小，以及碼樹怎么記錄的問題。5、ZIP中Huffman碼樹的記錄方式分析上面的例子，看看這個碼表：0-->3；10-->4；110-->5；111-->6。我們之前提過，0和1就是二進制的一個標志，互換一下其實根本不影響編碼長度，所以，下面的碼表其實是一樣的：1-->3；00-->4；010-->5；011-->6。1-->3；01-->4；000-->5；001-->6。0-->3；11-->4；100-->5；101-->6。。。。。。這些都可以，而且編碼長度完全一樣，只是碼字不同而巳。對比一下第一個和第二個例子，對應的碼樹是這個樣子：也就是說，我們把碼樹的任意節(jié)點的左右分支旋轉(zhuǎn)（0、1互換），也可以稱為樹的左右互換，其實不影響編碼長度，也就是說，這些碼表其實都是一樣好的，使用哪個都可以。這個規(guī)律暗示了什么信息呢？暗示了碼表可以怎么記錄呢？PhilKatz當年在牢里也深深地思考了這一問題。為了體會PhilKatz當時的心情，我們有必要盯著這兩棵樹思考幾分鐘：怎么把一顆樹用最少的比特記錄下來？PhilKatz當時思考的邏輯我猜是這樣的，既然這些樹的壓縮程度都一樣，那干脆使用最特殊的那棵樹，反正壓縮程度都一樣，只要ZIP規(guī)定了這棵樹的特殊性，那么我記錄的信息就可以最少，這種特殊化的思想在后面還會看到。不同的樹當然有不同的特點，比如數(shù)據(jù)結(jié)構(gòu)里面常見的平衡樹也是一類特殊的樹，他選的樹就是左邊那棵，這棵樹有一個特點，越靠左邊越淺，越往右邊越深，是這些樹中最不平衡的樹。ZIP里的壓縮算法稱為Deflate算法，這棵樹也稱為Deflate樹，對應的解壓縮算法稱為Inflate，Deflate的大致意思是把輪胎放氣了，意為壓縮；Inflate是給輪胎打氣的意思，意為解壓。那么，Deflate樹的特殊性又帶來什么了？揭曉答案吧，PhilKatz認為換來換去只有碼字長度不變，如果規(guī)定了一類特殊的樹，那么就只需要記錄碼字長度即可。比如，一個有效的碼表是0-->3；10-->4；110-->5；111-->6。但只需要記錄這個對應關系即可：34561233也就是說，把1、2、3、3記錄下來，解壓一邊照著左邊那棵樹的形狀構(gòu)造一顆樹，然后只需要1、2、3、3這個信息自然就知道是0、10、110、111。這就是PhilKatz想出來的ZIP最核心的一點：這棵碼樹用碼字長度序列記錄下來即可。當然，只把1、2、3、3這個序列記錄下來還不行，比如不知道111對應5還是對應6？所以，構(gòu)造出樹來只是知道了有哪些碼字了，但是這些碼字到底對應哪些整數(shù)還是不知道。PhilKatz于是又出現(xiàn)了一個想法：記錄1、2、3、3還是記錄1、3、2、3,或者3、3、2、1，其實都能構(gòu)造出這棵樹來，那么，為什么不按照一個特殊的順序記錄呢？這個順序就是整數(shù)的大小順序，比如上面的3、4、5、6是整數(shù)大小順序排列的，那么，記錄的順序就是1、2、3、3。而不是2、3、3、1。好了，根據(jù)1、2、3、3這個信息構(gòu)造出了碼字，這些碼字對應的整數(shù)一個比一個大，假如我們知道編碼前的整數(shù)就是3、4、5、6這四個數(shù)，那就能對應起來了，不過到底是哪四個還是不知道啊？這個整數(shù)可以表示距離啊，距離不知道怎么去解碼LZ？PhilKatz又想了，既然distance的范圍是1-32768,那么就按照這個順序記錄。上面的例子1和2沒有，那就記錄長度0。所以記錄下來的碼字長度序列為：0、0、1、2、3、3、0、0、0、0、0、。。。。。。。。。。。。這樣就知道構(gòu)造出來的碼字對應哪個整數(shù)了吧，但因為distance可能的值很多（32768個），但實際出現(xiàn)的往往不多，中間會出現(xiàn)很多0（也就是根本就沒出現(xiàn)這個距離），不過這個問題倒是可以對連續(xù)的0做個特殊標記，這樣是不是就行了呢？還有什么問題？我們還是要站在時代的高度來看待這個問題。我們明白，每個distance肯定對應唯一一個碼字，使用Huffman編碼可以得到所有碼字，但是因為distance可能非常多，雖然一般不會有32768這么多，但對一個大些的文件進行LZ編碼，distance上千還是很正常的，所以這棵樹很大，計算量、消耗的內(nèi)存都容易超越了那個時代的硬件條件，那么怎么辦呢？這里再次體現(xiàn)了PhilKatz對Huffman編碼掌握的深度，他把distance劃分成多個區(qū)間，每個區(qū)間當做一個整數(shù)來看，這個整數(shù)稱為DistanceCode。當一個distance落到某個區(qū)間，則相當于是出現(xiàn)了那個Code，多個distance對應于一個DistanceCode，Distance雖然很多，但DistanceCode可以劃分得很少，只要我們對Code進行Huffman編碼，得到Code的編碼后，DistanceCode再根據(jù)一定規(guī)則擴展出來。那么，劃分多少個區(qū)間？怎么劃分區(qū)間呢？我們分析過，越小的距離，出現(xiàn)的越多；越大的距離，出現(xiàn)的越少，所以這種區(qū)間劃分不是等間隔的，而是越來越稀疏的，類似于下面的劃分：1、2、3、4這四個特殊distance不劃分，或者說1個Distance就是1個區(qū)間；5,6作為一個區(qū)間；7、8作為一個區(qū)間等等，基本上，區(qū)間的大小都是1、2、4、8、16、32這么遞增的，越往后，涵蓋的距離越多。為什么這么分呢？首先自然是距離越小出現(xiàn)頻率越高，所以距離值小的時候，劃分密一些，這樣相當于一個放大鏡，可以對小的距離進行更精細地編碼，使得其編碼長度與其出現(xiàn)次數(shù)盡量匹配；對于距離較大那些，因為出現(xiàn)頻率低，所以可以適當放寬一些。另一個原因是，只要知道這個區(qū)間Code的碼字，那么對于這個區(qū)間里面的所有distance，后面追加相應的多個比特即可，比如，17-24這個區(qū)間的Huffman碼字是110，因為17-24這個區(qū)間有8個整數(shù)，于是按照下面的規(guī)則即可獲得其distance對應的碼字：->110000->110001->110010->110011->110100->110101->110110->110111這樣計算復雜度和內(nèi)存消耗是不是很小了，因為需要進行Huffman編碼的整數(shù)一下字變少了，這棵樹不會多大，計算起來時間和空間復雜度降低，擴展起來也比較簡單。當然，從理論上來說，這樣的編碼方式實際上將編碼過程分為了兩級，并不是理論上最優(yōu)的，把所有distance當作一個大空間去編碼才可能得到最優(yōu)結(jié)果，不過還是那句話，工程實現(xiàn)的限制，在壓縮軟件實現(xiàn)上，我們不能用壓縮率作為衡量一個算法優(yōu)劣的唯一指標，其實耗費的時間和空間同樣是指標，所以需要看綜合指標。很多其他軟件也一樣，擴展性、時間空間復雜度、穩(wěn)定性、移植性、維護的方便性等等是工程上很重要的東西。我沒有看過RAR是如何壓縮的，有可能是在類似的地方進行了改進，如果如此，那也是站在巨人的肩膀上，而且硬件條件不同，進行一些改進也并不奇怪。具體來說，PhilKatz把distance劃分為30個區(qū)間，如下圖：這個圖是我從DavidSalomon的《DataCompressionTheCompleteReference這本書（第四版）中拷貝出來的，下面的有些圖也是，如果需要對數(shù)據(jù)壓縮進行全面的了解，這本書幾乎是最全的了，強烈推薦。當然，你要問為什么是30個區(qū)間，我也沒分析過，也許是復雜度和壓縮率經(jīng)過試驗之后的一種折中吧。其中，左邊的Code表示區(qū)間的編號，是0-29,共30個區(qū)間，這只是個編號，沒有特別的含義，但Huffman就是對0-29這30個Code進行編碼的，得到區(qū)間的碼字；bits表示distance的碼字需要在Code的碼字基礎上擴展幾位，比如0就表示不擴展，最大的13表示要擴展13位，因此，最大的區(qū)間包含的distance數(shù)量為8192個。Distance一列則表示這個區(qū)間涵蓋的distance范圍。理解了碼樹如何有效記錄，以及如何縮小碼樹的過程，我覺得就理解了ZIP的精髓。6、ZIP中l(wèi)iteral和length的壓縮方式說完了distance，LZ編碼結(jié)果還有兩類：literal和length。這兩類也利用了類似于distance的方式進行壓縮。前面分析過，literal表示未匹配的字符，我們前面之所以拿漢字來舉例，完全是為了便于理解，ZIP之所以是通用壓縮，它實際上是針對字節(jié)作為基本字符來編碼的，所以一個literal至多有256種可能。length表示重復字符串長度，length=1當然不會出現(xiàn)，因為一個字符不值得用distance+length去記錄，重復字符串當然越長越好，PhilKatz（下面還是簡稱PK了，拷貝太麻煩）認為，length=2也不值得用這種方式記錄，還是太短了，所以PK把length最小值認為是3,必須3個以上字符的字符串出現(xiàn)重復才用distance+length記錄。那么，最大的length是多少呢？理論上當然可以很長很長，比如一個文件就是連續(xù)的0，這個重復字符串長度其實接近于這個文件的實際長度。但是PK把length的范圍做了限制，限定length的個數(shù)跟literal一樣，也只有256個，因為PK認為，一個重復字符串達到了256個巳經(jīng)很長了，概率非常??；另外，其實哪怕超過了256，我還是認為是一段256再加上另外一段，增加一個distance+length就行了嘛，并不影響結(jié)果。而且這樣做，我想同樣也考慮了硬件條件吧。初看有點奇怪的在于，將literal和length二者合二為一，什么意思呢？就是對這兩種整數(shù)（literal本質(zhì)上是一個字節(jié)）共用一個Huffman碼表，一會兒解釋為什么。PK對Huffman的理解我覺得達到了爐火純青的地步，前面巳經(jīng)看到，后面還會看到。他認為Huffman編碼的輸入反正說白了就是一個集合的元素就行，無論這個元素是啥，所以多個集合看做一個集合當作Huffman編碼的輸入沒啥問題。literal用整數(shù)0-255表示，256是一個結(jié)束標志，解碼以后結(jié)果是256表示解碼結(jié)束；從257開始表示length，所以257這個數(shù)表示length=3,258這個數(shù)表示length=4等等，但PK也不是一直這么一一對應，和distance一樣，也是把length（總共256個值）劃分為29個區(qū)間，其結(jié)果如下圖：其中的含義和distance類似，不再贅述，所以literal/length這個Huffman編碼的輸入元素一共285個，其中256表示解碼結(jié)束標志。為什么要把二者合二為一呢？因為當解碼器接收到一個比特流的時候，首先可以按照literal/length這個碼表來解碼，如果解出來是0-255，就表示未匹配字符，如果是256，那自然就結(jié)束，如果是257-285之間，則表示length，把后面擴展比特加上形成length后，后面的比特流肯定就表示distance，因此，實際上通過一個Huffman碼表，對各類情況進行了統(tǒng)一，而不是通過加一個什么標志來區(qū)分到底是literal還是重復字符串。好了，理解了上面的過程，就理解了ZIP壓縮的第二步，第一步是LZ編碼，第二步是對LZ編碼后結(jié)果（literal、distance、length）進行的再編碼，因為literal/length是一個碼表，我稱其為Huffman碼表1，distance那個碼表稱為Huffman碼表2。前面我們巳經(jīng)分析了，Huffman碼樹用一個碼字長度序列表示，稱為CL（CodeLength），記錄兩個碼表的碼字長度序列分別記為CL1、CL2。碼樹記錄下來，對literal/length的編碼比特流稱為LIT比特流；對distance的編碼比特流稱為DIST比特流。按照上面的方法，LZ的編碼結(jié)果就變成四塊：CL1、CL2、LIT比特流、DIST比特流。CL1、CL2是碼字長度的序列，這個序列說白了就是一堆正整數(shù)，因此，PK繼續(xù)深挖，認為這個序列還應該繼續(xù)壓縮，也就是說，對碼表進行壓縮。7、ZIP中對CL進行再次壓縮的方法這里仍然沿用Huffman的想法，因為CL也是一堆整數(shù)，那么當然可以再次應用Huffman編碼。不過在這之前，PK對CL序列進行了一點處理。這個處理也是很精巧的。CL序列表示一系列整數(shù)對應的碼字長度，對于literal/length來說，總共有0-285這么多符號，所以這個序列長度為286，每個符號都有一個碼字長度，當然，這里面可能會出現(xiàn)大段連續(xù)的0，因為某些字符或長度不存在，尤其是對英文文本編碼的時候，非ASCII字符就根本不會出現(xiàn)，length較大的值出現(xiàn)概率也很小，所以出現(xiàn)大段的0是很正常的；對于distance也類似，也可能出現(xiàn)大段的0。PK于是先進行了一下游程編碼。在說什么是游程編碼之前，我們談談PK對CL序列的認識。literal/length的編碼符號總共286個（回憶：256個Literal+1個結(jié)束標志+29個length區(qū)間），distance的編碼符號總共30個（回憶：30個區(qū)間），所以這顆碼樹不會特別深，Huffman編碼后的碼字長度不會特別長，PK認為最長不會超過15,也就是樹的深度不會超過15,這個是否是理論證明我還沒有分析，有興趣的同學可以分析一下。因此，CL1和CL2這兩個序列的任意整數(shù)值的范圍是0-15。0表示某個整數(shù)沒有出現(xiàn)（比如literal=0x12,lengthCode=8,distanceCode=15等等）。什么叫游程呢？就是一段完全相同的數(shù)的序列。什么叫游程編碼呢？說起來原理更簡單，就是對一段連續(xù)相同的數(shù)，記錄這個數(shù)一次，緊接著記錄出現(xiàn)了多少個即可。David的書中舉了這個例子，比如CL序列如下：4,4,4,4,4,3,3,3,6,6,6,6,6,6,6,6,6,6,0,0,0,0,0,0,2,2,2,2那么，游程編碼的結(jié)果為：4,16,01（二進制），3,3,3,6,16,11（二進制），16,00（二進制），17,011（二進制），2,16,00（二進制）這是什么意思呢？因為CL的范圍是0-15,PK認為重復出現(xiàn)2次太短就不用游程編碼了，所以游程長度從3開始。用16這個特殊的數(shù)表示重復出現(xiàn)3、4、5、6個這樣一個游程，分別后面跟著00、01、10、11表示（實際存儲的時候需要低比特優(yōu)先存儲，需要把比特倒序來存，博文的一些例子有時候會忽略這點，實際寫程序的時候一定要注意，否則會得到錯誤結(jié)果）。于是4,4,4,4,4，這段游程記錄為4,16,01，也就是說，4這個數(shù)，后面還會連續(xù)出現(xiàn)了4次。6,16,11,16,00表示6后面還連續(xù)跟著6個6,再跟著3個6；因為連續(xù)的0出現(xiàn)的可能很多，所以用17、18這兩個特殊的數(shù)專門表示0游程，17后面跟著3個比特分別記錄長度為3-10（總共8種可能）的游程；18后面跟著7個比特表示11-138（總共128種可能）的游程。17,011（二進制）表示連續(xù)出現(xiàn)6個0；18,0111110（二進制）表示連續(xù)出現(xiàn)62個0?？傊涀?，0-15是CL可能出現(xiàn)的值，16表示除了0以外的其它游程；17、18表示0游程。因為二進制實際上也是個整數(shù)，所以上面的序列用整數(shù)表示為：4,16,1,3,3,3,6,16,3,16,0,17,3,2,16,0我們又看到了一串整數(shù)，這串整數(shù)的值的范圍是0-18。這個序列稱為SQ（Sequence的意思）。因為有兩個CL1、CL2,所以對應的有兩個SQ1、SQ2。針對SQ1、SQ2,PK用了第三個Huffman碼表來對這兩個序列進行編碼。通過統(tǒng)計各個整數(shù)（0-18范圍內(nèi)）的出現(xiàn)次數(shù)，按照相同的思路，對SQ1和SQ2進行了Huffman編碼，得到的碼流記為SQ1bits和SQ2bits。同時，這里又需要記錄第三個碼表，稱為Huffman碼表3。同理，這個碼表也用相同的方法記錄，也等效為一個碼長序列，稱為CCL，因為至多有0-18個，PK認為樹的深度至多為7,于是CCL的范圍是0-7。當?shù)玫搅薈CL序列后，PK決定不再折騰，對這個序列用普通的3比特定長編碼記錄下來即可，即000代表0,111代表7。但實際上還有一點小折騰，就是最后這個序列如果全部記錄，那就需要19*3=57個比特，PK認為CL序列里面CL范圍為0-15,特殊的幾個值是16、17、18,如果把CCL序列位置置換一下，把16、17、18這些放前面，那么這個CCL序列就很可能最后面跟著一串0（因為CL=14,15這些很可能沒有），所以最后還引入了一個置換，其示意圖如下，分別表示置換前的CCL序列和置換后的CCL?？梢钥闯觯?6、17、18對應的CCL被放到了前面，這樣如果尾部出現(xiàn)了一些0，就只需要記錄CCL長度即可，后面的0不記錄。可以繼續(xù)節(jié)省一些比特，不過這個例子尾部置換后只有1個0：不過粗看起來，這個置換效果并不好，我一開始接觸這個置換的時候，我覺得應該按照16、17、18、0、1、2、3、。。。這樣的順序來存儲，如果按照我理解的，那么置換后的結(jié)果如下：2、4、0、4、5、5、1、5、0、6、0、0、0、0、0、0、0、0、0這樣后面的一大串0直接截斷，比PK的方法更短。但PK卻按照上面的順序。我總是認為，我覺得牛人可能出錯了的時候，往往是我自己錯了，所以我又仔細想了一下，上面的順序特點比較明顯，直觀上看，PK認為CL為0和中間的值出現(xiàn)得比較多（放在了前面），但CL比較小的和比較大的出現(xiàn)得比較少（1、15、2、14這些放在了后面，你看，后面交叉著放），在文件比較小的時候，這種方法效果不算好，上面就是一個典型的例子，但文件比較大了以后，CL1、CL2碼樹比較大，碼字長度普遍比較長，大部分很可能接近于中間值，那么這個時候PK的方法可能就體現(xiàn)出優(yōu)勢了。不得不說，對一個算法或者數(shù)據(jù)結(jié)構(gòu)的優(yōu)化程度，簡直完全取決于程序員對那個東西細節(jié)的理解的深度。當我仔細研究了ZIP壓縮算法的過程之后，我對PK這種深夜埋頭冥思苦想的大牛佩服得五體投地。到此為止，ZIP壓縮算法的結(jié)果巳經(jīng)完畢。這個算法命名為Deflate算法?？偨Y(jié)一下其編碼流程為:8、Deflate壓縮數(shù)據(jù)格式ZIP的格式實際上就是Deflate壓縮碼流外面套了一層文件相關的信息，這里先介紹Deflate壓縮碼流格式。其格式為：Header：3個比特，第一個比特如果是1，表示此部分為最后一個壓縮數(shù)據(jù)塊；否則表示這是.ZIP文件的某個中間壓縮數(shù)據(jù)塊，但后面還有其他數(shù)據(jù)塊。這是ZIP中使用分塊壓縮的標志之一；第2、3比特表示3個選擇：壓縮數(shù)據(jù)中沒有使用Huffman＞使用靜態(tài)Huffman＞使用動態(tài)Huffman，這是對LZ77編碼后的literal/length/distance進行進一步編碼的標志。我們前面分析的都是動態(tài)Huffman，其實Deflate也支持靜態(tài)Huffman編碼，靜態(tài)Huffman編碼原理更為簡單，無需記錄碼表（因為PK自己定義了一個固定的碼表），但壓縮率不高，所以大多數(shù)情況下都是動態(tài)Huffman。HLIT：5比特，記錄literal/length碼樹中碼長序列（CL1）個數(shù)的一個變量。后面CL1個數(shù)等于HLIT+257（因為至少有0-255總共256個literal，還有一個256表示解碼結(jié)束，但length的個數(shù)不定）。HDIST：5比特，記錄distance碼樹中碼長序列（CL2）個數(shù)的一個變量。后面CL2個數(shù)等于HDIST+1。哪怕沒有1個重復字符串，distance都為0也是一個CL。HCLEN：4比特，記錄Huffman碼表3中碼長序列（CCL）個數(shù)的一個變量。后面CCL個數(shù)等于HCLEN+4。PK認為CCL個數(shù)不會低于4個，即使對于整個文件只有1個字符的情況。接下來是3比特編碼的CCL，一共HCLEN+4個，用以構(gòu)造Huffman碼表3；接下來是對CL1（碼長）序列經(jīng)過游程編碼（SQ1：縮短的整數(shù)序列）后，并對SQ1繼續(xù)用Huffman編碼后的比特流。包含HLIT+257個CL1，其解碼碼表為Huffman碼表3,用以構(gòu)造Huffman碼表1；接下來是對CL2（碼長）序列經(jīng)過游程編碼（SQ2：縮短的整數(shù)序列）后，并對SQ2繼續(xù)用Huffman編碼后的比特流。包含HDIST+1個CL2,其解碼碼表為Huffman碼表3,用于構(gòu)造Huffman碼表2；總之，上面的數(shù)據(jù)都是為了構(gòu)造LZ解碼需要的2個Huffman碼表。接下來才是經(jīng)過Huffman編碼的壓縮數(shù)據(jù)，解碼碼表為Huffman碼表1和碼表2。最后是數(shù)據(jù)塊結(jié)束標志，即literal/length這個碼表輸入符號位256的編碼比特。對倒數(shù)第1、2內(nèi)容塊進行解碼時，首先利用Huffman碼表1進行解碼，如果解碼所得整數(shù)位于0-255之間，表示literal未匹配字符，接下來仍然利用Huffman碼表1解碼；如果位于257-285之間，表示length匹配長度，之后需要利用Huffman碼表2進行解碼得到distance偏移距離；如果等于256，表示數(shù)據(jù)塊解碼結(jié)束。9、ZIP文件格式解析上面各節(jié)對ZIP的原理進行了分析，這一節(jié)我們來看一個實際的例子，為了更好地描述，我們盡量把這個例子舉得簡單一些。下面是我隨便從一本書拷貝出來的一段較短的待壓縮的英文文本數(shù)據(jù)：Asmentionedabove,therearemanykindsofwirelesssystemsotherthancellular.這段英文文本長度為80字節(jié)。經(jīng)過ZIP壓縮后，其內(nèi)容如下：可以看到，第1、2字節(jié)就是PK?？粗趺幢仍倪€長，這怎么叫壓縮？實際上，這里面大部分內(nèi)容是ZIP的文件標記開銷，真正壓縮的內(nèi)容（也就是我們前面提到的Deflate數(shù)據(jù)，劃線部分都是ZIP文件開銷）其實肯定要比原文短（否則ZIP不會啟用壓縮），我們這個例子是個短文本，但對于更長的文本而言，那ZIP文件總體長度肯定是要短于原始文本的。上面的這個ZIP文件，可以看到好幾個以PK開頭的區(qū)域，也就是不同顏色的劃線區(qū)域，這些其實都是ZIP文件本身的開銷。所以，我們首先來看一看ZIP的格式，其格式定義為：[localfileheader1][filedata1][datadescriptor1][localfileheadern][filedatan][datadescriptorn][archivedecryptionheader][archiveextradatarecord][centraldirectory][zip64endofcentraldirectoryrecord][zip64endofcentraldirectorylocator][endofcentraldirectoryrecord]localfileheader+filedata+datadescriptor這是一段ZIP壓縮數(shù)據(jù)，在一個ZIP文件里，至少有一段，至多那就不好說了，假如你要壓縮的文件一共有10個，那這個地方至少會有10段，ZIP對每個文件進行了獨立壓縮，RAR在此進行了改進，將多個文件聯(lián)合起來進行壓縮，提高了壓縮率。localfileheader的格式如下：可見，起始的4個字節(jié)就是0x50（P）、0x4B（K）、0x03、0x04，因為是低字節(jié)優(yōu)先，所以Signature=0x03044B50.接下來的內(nèi)容按照上面的格式解析，十分簡單，這個區(qū)域在上面ZIP數(shù)據(jù)的那個圖里面是紅色劃線區(qū)域，之后則是壓縮后的Deflate數(shù)據(jù)。在文件的尾部，還有ZIP尾部數(shù)據(jù)，上面這個例子包含了centraldirectory和endofcentraldirectoryrecord一般這兩部分也是必須的°centraldirectory以0x50、0x4B、0x01、0x02開頭；endofcentraldirectoryrecord以0x50、0x4B、0x05、0x06開頭，其含義比較簡單，分別對應于上面ZIP數(shù)據(jù)那個圖的藍色和綠色部分，下面是兩者的格式：endofcentraldirectoryrecord格式：這幾張圖是我從網(wǎng)上找的，寫得比較清晰。對于其中的含義，解釋起來也比較簡單，我分析的結(jié)果如下：注意ZIP采用的低字節(jié)優(yōu)先，在一個字節(jié)里面低位優(yōu)先，需要反過來看。LocalFileHeader:(38B,304b)00000000000100000(signature)0000000000010100(version:20)0000000000000000(generalBitFlag)0000000000001000(compressionMethod:8)0(lastModTime:19854)0(lastModDate:17701)00(CRC32)00000000000000000000000001001000(compressedSize:72)00000000000000000000000001010000(uncompressedSize:80)0000000000001000(filenameLength:8)0000000000000000(extraFieldLength:0)00000011(fileName:Test.txt)(extraField)CentralFileHeader:(54B,432b)00000000001000000(signature)0000000000010100(versionMadeBy:20)0000000000010100(versionNeeded:20)0000000000000000(generalBitFlag)0000000000001000(compressionMethod:8)0(lastModTime:19854)0(lastModDate:17701)00(CRC32)00000000000000000000000001001000(compressedSize:72)00000000000000000000000001010000(uncompressedSize:80)0000000000001000(filenameLength:8)0000000000000000(extraFieldLength:0)0000000000000000(fileCommenLength:0)0000000000000000(diskNumberStart)0000000000000001(internalFileAttr)00000000000100000(externalFileAttr)00000000000000000000000000000000(relativeOffsetLocalHeader)00000011(fileName:Test.txt)(extraField)(fileComment)endofCentralDirectoryRecord:(22B,176b)00000000001100000(signature)0000000000000000(numberOfThisDisk:0)0000000000000000(numberDiskCentralDirectory:0)0000000000000001(EntriesCentralDirectDisk:1)0000000000000001(EntriesCentralDirect:1)00000000000000000000000000110110(sizeCentralDirectory:54)00000000000000000000000001101110(offsetStartCentralDirectory:110)0000000000000000(fileCommentLength:0)(fileComment)LocalFileHeaderLength:304CentralFileHeaderLength:432EndCentralDirectoryRecordLength:176可見，開銷總的長度為38+54+22=114字節(jié)，整個文件長度為186字節(jié)，因此Deflate壓縮數(shù)據(jù)長度為72字節(jié)(576比特)。盡管這里看起來只是從80字節(jié)壓縮到72字節(jié)，那是因為這是一段短文本，重復字符串出現(xiàn)較少，但如果文本較長，那壓縮率就會增加，這里只是舉個例子。下面對其中的關鍵部分，也就是Deflate壓縮數(shù)據(jù)進行解析。10，Deflate解碼過程實例分析我們按照ZIP格式把Deflate壓縮數(shù)據(jù)(72字節(jié))提取出來，如下(每行8字節(jié))：00000000000000001001010000000110101010000000100000000000100000010Deflate格式除了上面的介紹，也可以參考RFC1951，解析如下：Header:101,第一個比特是1，表示此部分為最后一個壓縮數(shù)據(jù)塊；后面的兩個比特01表示采用動態(tài)哈夫曼、靜態(tài)哈夫曼、或者沒有編碼的標志，01表示采用動態(tài)Huffman；在RFC1951里面是這么說明的：00-nocompression01-compressedwithfixedHuffmancodes-compressedwithdynamicHuffmancodes-reserved(error)注意，這里需要按照低比特在先的方式去看，否則會誤以為是靜態(tài)Huffmano接下來：HLIT:01000,記錄literal/length碼樹中碼長序列個數(shù)的一個變量，表示HLIT=2(低位在前)，說明后面存在HLIT+257=259個CL1，CL1即0-258被編碼后的長度，其中0-255表示Literal，256表示無效符號，257、258分別表示Length=3、4(length從3開始)。因此，這里實際上只出現(xiàn)了兩種重復字符串的長度，即3和4?；仡欉@個圖可以更清楚：繼續(xù)：HDIST:01010,記錄distance碼樹中碼長序列個數(shù)的一個變量，表示HDIST=10，說明后面存在HDIST+1=11個CL2，CL2即DistanceCode=0-10被編碼的長度。繼續(xù)：HCLEN:0111,記錄Huffman碼樹3中碼長序列個數(shù)的一個變量，表示HCLEN=14(1110二進制)，即說明緊接著跟著HCLEN+4=18個CCL，前面巳經(jīng)分析過，CCL記錄了一個Huffman碼表，這個碼表可以用一個碼長序列表示，根據(jù)這個碼長序列可以得到碼表。于是接下來我們把后面的18*3=54個比特拷貝出來，上面的碼流目前解析為下面的結(jié)果：101(Header)01000(HLIT)01010(HDIST)0111(HCLEN)000101110110000000000010000010000110000101000101000101(CCL)00000000000110101010000000100000000000100000010標準的CCL長度為19(回憶一下：CCL范圍為0-18，按照整數(shù)大小排序記錄各自的碼字長度)，因此最后一個補0。得到序列：000101110110000000000010000010000110000101000101000101000其長度分別為(低位在前)：0、5、3、3、0、0、0、2、0、2、0、3、0、5、0、5、0、5、0前面巳經(jīng)分析過，這個CCL序列實際上是經(jīng)過一次置換操作得到的，需要進行相反的置換，置換后為：3、5、5、5、3、2、2、0、0、0、0、0、0、0、0、0、0、5、3這個就是對應于0-18的碼字長度序列。根據(jù)Deflate樹的構(gòu)造方式，得到下面的碼表(Huffman碼表3)：TOC\o"1-5"\h\z00<-->501<-->6<-->0<-->4110<-->18<-->1<-->2<-->3<-->17接下來就是CL1序列，按照前面的指示，一共有259個，分別對應于literal/length：0-258對應的碼字長度序列，我們隊跟著CCL后面的比特按照上面獲得的碼表進行逐步解碼，在解碼之前，實際上并不知道CL1的比特流長度有多少，需要根據(jù)259這個數(shù)字來判定，解完了259個整數(shù)，表明解析CL1完畢：101(Header)01000(HLIT)01010(HDIST)0111(HCLEN)000101110110000000000010000010000110000101000101000101(CCL)110(18)1010100(7比特，記錄連續(xù)的11-138個0，此處一共0010101b=21，即記錄21+11=32個0)11110(3)110(18)0000000(7比特，記錄連續(xù)的11-138個0，此處為全0，即記錄0+11=11個0)01(6)100(0)01(6)110(18)1110000(7比特，記錄連續(xù)的11-138個0，此處為111b=7,即記錄7+11=18個0)01(6)110(18)0010100(7比特，記錄連續(xù)的11-138個0，此處為10100b=20，即記錄20+11=31個0)101(4)01(6)01(6)00(5)11110(3)01(6)100(0)00(5)00(5)100(0)01(6)101(4)00(5)101(4)00(5)100(0)100(0)00(5)101(4)101(4)01(6)01(6)01(6)100(0)00(5)110(18)1101111(7比特，記錄連續(xù)的11-138個0，此處為1111011b=123，即記錄123+11=134個0)統(tǒng)計一下，上面巳經(jīng)解了32+11+18+31+134+30=256個數(shù)了，因為總共259個，還差三個：01(6)00(5)01(6)好了，CL1比特流解析完畢了，得到的CL1碼長序列為：TOC\o"1-5"\h\z0000000000000000000000000000000030000000000060600000000000000000060000000000000000000000000000000466536055064545005446660500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000656總共259個，每行40個。根據(jù)這個序列，同樣按照Deflate樹構(gòu)造方法，得到literal/length碼表(Huffman碼表1)為：000-->(System.Char)(看前面的CL1序列，空格對應的ASCII為0x20=32,碼字長度3，即上面序列中第一個3)001-->e(System.Char)0100-->a(System.Char)0101-->l(System.Char)0110-->n(System.Char)0111-->s(System.Char)1000-->t(System.Char)-->d(System.Char)-->h(System.Char)10100-->i(System.Char)10101-->m(System.Char)-->o(System.Char)-->r(System.Char)-->y(System.Char)->3(System.Int32)(看前面的CL1序列，對應257，碼字長度5)110100-->,(System.Char)110101-->.(System.Char)110110-->A(System.Char)110111-->b(System.Char)111000-->c(System.Char)111001-->f(System.Char)111010-->k(System.Char)111011-->u(System.Char)111100-->v(System.Char)111101-->w(System.Char)111110->-1(System.Int32)(看前面的CL1序列，對應256,碼字長度6)111111->4(System.Int32)(看前面的CL1序列，對應258，碼字長度6)可以看出，碼表里存在兩個重復字符串長度3和4，當解碼結(jié)果為-1(上面進行了處理，即256)，或者說遇到111110的時候，表示Deflate碼流結(jié)束。按照同樣的道理，對CL2序列進行解析，前面巳經(jīng)知道HDIST=10，即有11個CL2整數(shù)序列：11111(17)000(3比特，記錄連續(xù)的3-10個0，此處為0，即記錄3個0)11101(2)11111(17)100(3比特，記錄連續(xù)的3-10個0，此處為001b=1，即記錄4個0)11100(1)100(0)11101(2)巳經(jīng)結(jié)束，總共11個。于是CL2序列為：00020000102分別記錄的是distance碼為0-10的碼字長度，根據(jù)下面的對應關系，需要進行擴展：比如，第1個碼長2記錄的是Code=3的長度，即Distance=4對應的碼字為：10-->4(System.Int32)第1個碼長1記錄的是Code=8的長度(碼字為0，擴展三位000-111)，即Distance=17-24對應的碼字為(注意，低比特優(yōu)先)：0000-->17(System.Int32)0100-->18(System.Int32)0010-->19(System.Int32)0110-->20(System.Int32)0001-->21(System.Int32)0101-->22(System.Int32)0011-->23(System.Int32)0111-->24(System.Int32)注意，擴展的時候還是低比特優(yōu)先。最后1個碼長2記錄的是Code=10的長度（其實是碼字：11，擴展四位0000-1111），即Distance=33-48對應的碼字為：110000-->33（System.Int32）111000-->34（System.Int32）110100-->35（System.Int32）111100-->36（System.Int32）110010-->37（System.Int32）111010-->38（System.Int32）110110-->39（System.Int32）111110-->40（System.Int32）110001-->41（System.Int32）111001-->42（System.Int32）110101-->43（System.Int32）111101-->44（System.Int32）110011-->45（System.Int32）111011-->46（System.Int32）110111-->47（System.Int32）111111-->48（System.Int32）至此為止，Huffman碼表1>Huffman碼表2巳經(jīng)還原出來，接下來是對LZ壓縮所得到的literal、distance、length進行解碼，目前剩余的比特流如下，先按照Huffman碼表1解碼，如果解碼結(jié)果是長度（>256），則接下來按照Huffman碼表2解碼，逐步解碼即可：[As]：110110（A）0111（s）000（空格）[mentioned]：10101（m）001（e）0110（n）1000（t）10100（i）10110（o）0110（n）001（e）10010（d）000（空格）[above,]：0100（a）110111（b）