一 壓縮算法的原理
最近自己實現(xiàn)了一個ZIP壓縮數(shù)據(jù)的解壓程序，覺得有必要把ZIP壓縮格式進(jìn)行一下詳細(xì)總結(jié)蚓庭，數(shù)據(jù)壓縮是一門通信原理和計算機(jī)科學(xué)都會涉及到的學(xué)科致讥，在通信原理中，一般稱為信源編碼器赞，在計算機(jī)科學(xué)里拄踪，一般稱為數(shù)據(jù)壓縮，兩者本質(zhì)上沒啥區(qū)別拳魁，在數(shù)學(xué)家看來惶桐，都是映射。一方面在進(jìn)行通信的時候潘懊，有必要將待傳輸?shù)臄?shù)據(jù)進(jìn)行壓縮姚糊，以減少帶寬需求；另一方面授舟，計算機(jī)存儲數(shù)據(jù)的時候救恨，為了減少磁盤容量需求，也會將文件進(jìn)行壓縮释树，盡管現(xiàn)在的網(wǎng)絡(luò)帶寬越來越高肠槽，壓縮已經(jīng)不像90年代初那個時候那么迫切，但在很多場合下仍然需要奢啥，其中一個原因是壓縮后的數(shù)據(jù)容量減小后秸仙，磁盤訪問IO的時間也縮短，盡管壓縮和解壓縮過程會消耗CPU資源桩盲，但是CPU計算資源增長得很快寂纪，但是磁盤IO資源卻變化得很慢，比如目前主流的SATA硬盤仍然是7200轉(zhuǎn)赌结，如果把磁盤的IO壓力轉(zhuǎn)化到CPU上捞蛋，總體上能夠提升系統(tǒng)運(yùn)行速度。壓縮作為一種非常典型的技術(shù)柬姚，會應(yīng)用到很多很多場合下拟杉，比如文件系統(tǒng)、數(shù)據(jù)庫量承、消息傳輸搬设、網(wǎng)頁傳輸?shù)鹊雀黝悎龊咸淙尽Ａ硗猓疚纳婕暗膲嚎s算法非常主流并且十分精巧焕梅，其實現(xiàn)涉及桶排序、靜態(tài)鏈表卦洽、Huffman樹等數(shù)據(jù)結(jié)構(gòu)內(nèi)容贞言，理解了ZIP的壓縮過程，對理解其它相關(guān)的壓縮算法應(yīng)該就比較容易了阀蒂。
1 引子
壓縮可以分為無損壓縮和有損壓縮该窗，有損，指的是壓縮之后就無法完整還原原始信息蚤霞，但是壓縮率可以很高酗失，主要應(yīng)用于視頻、話音等數(shù)據(jù)的壓縮昧绣，因為損失了一點信息规肴，人是很難察覺的，或者說夜畴，也沒必要那么清晰照樣可以看可以聽拖刃；無損壓縮則用于文件等等必須完整還原信息的場合，ZIP自然就是一種無損壓縮贪绘，在通信原理中介紹數(shù)據(jù)壓縮的時候兑牡，往往是從信息論的角度出發(fā)，引出香農(nóng)所定義的熵的概念税灌，這方面的介紹實在太多均函，這里換一種思路，從最原始的思想出發(fā)菱涤，為了達(dá)到壓縮的目的苞也，需要怎么去設(shè)計算法。而ZIP為我們提供了相當(dāng)好的案例粘秆。
盡管我們不去探討信息論里面那些復(fù)雜的概念墩朦，不過我們首先還是要從兩位信息論大牛談起。因為是他們奠基了今天大多數(shù)無損數(shù)據(jù)壓縮的核心翻擒，包括ZIP氓涣、RAR、GZIP陋气、GIF劳吠、PNG等等大部分無損壓縮格式。這兩位大牛的名字分別是Jacob Ziv和Abraham Lempel巩趁，是兩位以色列人痒玩，在1977年的時候發(fā)表了一篇論文《A Universal Algorithm for Sequential Data Compression》淳附，從名字可以看出，這是一種通用壓縮算法蠢古，所謂通用壓縮算法奴曙，指的是這種壓縮算法沒有對數(shù)據(jù)的類型有什么限定。它的思想還是很簡單的草讶，之所以看起來復(fù)雜洽糟，主要是因為IEEE的某些雜志就是這個特點，需要從數(shù)學(xué)上去證明堕战，這種壓縮算法到底有多優(yōu)坤溃，比如針對一個各態(tài)歷經(jīng)的隨機(jī)序列，經(jīng)過這樣的壓縮算法后嘱丢，是否可以接近信息論里面的極限（也就是前面說的熵的概念）等等薪介，不過在理解其思想之前，個人認(rèn)為沒必要深究這些東西越驻，除非你要發(fā)論文汁政。這兩位大牛提出的這個算法稱為LZ77，兩位大牛過了一年又提了一個類似的算法缀旁，稱為LZ78烂完，思想類似，ZIP這個算法就是基于LZ77的思想演變過來的诵棵，但ZIP對LZ77編碼之后的結(jié)果又繼續(xù)進(jìn)行壓縮抠蚣，直到難以壓縮為止。除了LZ77履澳、LZ78嘶窄，還有很多變種的算法，基本都以LZ開頭距贷，如LZW柄冲、LZO、LZMA忠蝗、LZSS现横、LZR、LZB阁最、LZH戒祠、LZC、LZT速种、LZMW姜盈、LZJ、LZFG等等配阵，非常多馏颂，LZW也比較流行示血，GIF那個動畫格式記得用了LZW。我也寫過解碼程序救拉，以后有時間可以再寫一篇难审，但感覺跟LZ77這些類似，寫的必要性不大亿絮。
ZIP的作者是一個叫Phil Katz的人告喊，這個人算是開源界的一個具有悲劇色彩的傳奇人物。雖然二三十年前壹无，開源這個詞還沒有現(xiàn)在這樣風(fēng)起云涌，但是總有一些具有黑客精神的牛人感帅，內(nèi)心里面充滿了自由斗锭，無論他處于哪個時代。Phil Katz這個人是個牛逼程序員失球，成名于DOS時代岖是，我個人也沒有經(jīng)歷過那個時代，我是從Windows98開始接觸電腦的实苞，只是從書籍中得知豺撑，那個時代網(wǎng)速很慢，撥號使用的是只有幾十Kb（比特不是字節(jié)）的貓黔牵，56Kb實際上是這種貓的最高速度聪轿，在ADSL出現(xiàn)之后，這種技術(shù)被迅速淘汰猾浦。Phil Katz上網(wǎng)的時候還不到1990年陆错，WWW實際上就沒出現(xiàn)，瀏覽器當(dāng)然是沒有的金赦，當(dāng)時上網(wǎng)干嘛呢音瓷？基本就是類似于網(wǎng)管敲各種命令，這樣實際上也可以聊天夹抗、上論壇不是嗎绳慎，傳個文件不壓縮的話肯定死慢死慢的，所以壓縮在那個時代很重要漠烧。當(dāng)時有個商業(yè)公司提供了一種稱為ARC的壓縮軟件杏愤，可以讓你在那個時代聊天更快，當(dāng)然是要付費(fèi)的已脓，Phil Katz就感覺到不爽声邦，于是寫了一個PKARC，免費(fèi)的摆舟，看名字知道是兼容ARC的亥曹，于是網(wǎng)友都用PKARC了邓了，ARC那個公司自然就不爽，把哥們告上了法庭媳瞪，說牽涉了知識產(chǎn)權(quán)等等骗炉，結(jié)果Phil Katz坐牢了......牛人就是牛人， 在牢里面冥思苦想蛇受，決定整一個超越ARC的牛逼算法出來句葵，牢里面就是適合思考，用了兩周就整出來的兢仰，稱為PKZIP乍丈，不僅免費(fèi)，而且這次還開源了把将，直接公布源代碼轻专，因為算法都不一樣了，也就不涉及到知識產(chǎn)權(quán)了察蹲，于是ZIP流行開來请垛，不過Phil Katz這個人沒有從里面賺到一分錢，還是窮困潦倒洽议，因為喝酒過多等眾多原因宗收，2000年的時候死在一個汽車旅館里。英雄逝去亚兄，精神永存混稽，現(xiàn)在我們用UE打開ZIP文件，我們能看到開頭的兩個字節(jié)就是PK兩個字符的ASCII碼审胚。
2 一個案例的入門思考
好了荚坞，Phil Katz在牢里面到底思考了什么？用什么樣的算法來壓縮數(shù)據(jù)呢菲盾？我們想一個簡單的例子：
生颓影，容易±良活诡挂，容易。生活临谱，不容易璃俗。
上面這句話假如不壓縮，一共有17個字符（包括標(biāo)點符號）悉默，如果用普通Unicode表示城豁，一共是17*2=34字節(jié)〕危可不可以壓縮呢唱星？所有人一眼都可以看出里面出現(xiàn)了很多重復(fù)的字符雳旅，比如里面出現(xiàn)了好多次容易（實際上是容易加句號三個字符）這個詞，第一次出現(xiàn)的時候用普通的Unicode间聊，第二次出現(xiàn)的“容易攒盈。”則可以用（距離哎榴、長度）表示型豁，距離的意思是接下來的字符離前面重復(fù)的字符隔了幾個，長度則表示有幾個重復(fù)字符尚蝌，上面的例子的第二個“容易迎变。”就表示為（5,3）飘言，就是距離為5個字符衣形，長度是3，在解壓縮的時候热凹，解到這個地方的時候泵喘，往前跳5個字符泪电，把這個位置的連續(xù)3個字符拷貝過來就完成了解壓縮般妙，這實際上不就是指針的概念？沒有錯相速，跟指針很類似碟渺，不過在數(shù)據(jù)壓縮領(lǐng)域，一般稱為字典編碼突诬，為什么叫字典呢苫拍，當(dāng)我們?nèi)ゲ橐粋€字的時候，我們總是先去目錄查找這個字在哪一頁旺隙，再翻到那一頁去看绒极，指針不也是這樣，指針不就是內(nèi)存的地址蔬捷，要對一個內(nèi)存進(jìn)行操作垄提，我們先拿到指針，然后去那塊內(nèi)存去操作周拐。所謂的指針铡俐、字典、索引妥粟、目錄等等術(shù)語审丘，不同的背景可能稱呼不同埃元，但我們要理解他們的本質(zhì)勘天。如果使用（5,3）這種表示方法缸濒，原來需要用6個字節(jié)表示妇拯，現(xiàn)在只需要記錄5和3即可。那么露泊，5和3怎么記錄呢喉镰？一種方法自然還是可以用Unicode，那么就相當(dāng)于節(jié)省了2個字節(jié)惭笑，但是有兩個問題侣姆，第一個問題是解壓縮的時候怎么知道是正常的5和3這兩個字符，還是這只是一個特殊標(biāo)記呢沉噩？所以前面還得加一個標(biāo)志來區(qū)分一下捺宗，到底接下來的Unicode碼是指普通字符，還是指距離和長度川蒙，如果是普通Unicode蚜厉，則直接查Unicode碼表，如果是距離和長度畜眨，則往前面移動一段距離昼牛，拷貝即可。第二個問題康聂，還是壓縮程度不行贰健，這么一弄，感覺壓縮不了多少恬汁，如果重復(fù)字符比較長那倒是比較劃算伶椿，因為反正“距離+長度”就夠了，但比如這個例子氓侧，如果5和3前面加一個特殊字節(jié)脊另，豈不是又是3個字節(jié)，那還不如不壓縮约巷。咋辦呢偎痛？能不能對（5,3）這種整數(shù)進(jìn)行再次壓縮？這里就利用了我們前面說的一個基本原則：出現(xiàn)的少的整數(shù)多編一些比特独郎，出現(xiàn)的多的整數(shù)少編一些比特踩麦。那么，比如3囚聚、4靖榕、5、6顽铸、7茁计、8、9這些距離誰出現(xiàn)得多？誰出現(xiàn)的少呢星压？誰知道践剂？
壓縮之前當(dāng)然不知道，不過掃描一遍不就知道了娜膘？比如逊脯，后面那個重復(fù)的字符串“容易】⑻埃”按照前面的規(guī)則可以表示為（7,3）,即離前面重復(fù)的字符串距離為7军洼，長度為3。（7,3）指著前面跟自己一樣那個字符串演怎。那么匕争，為什么不指著第一個“容易∫”要指著第二個“容易甘桑。”呢歹叮？如果指著第一個跑杭，那就不是（7,3）了，就是（12咆耿，3）了德谅。當(dāng)然，表示為（12,3）也可以解壓縮票灰，但是有一個問題女阀，就是12這個值比7大宅荤，大了又怎么了屑迂？我們在生活中會發(fā)現(xiàn)一些普遍規(guī)律，重復(fù)現(xiàn)象往往具有局部性冯键。比如惹盼，你跟一個人說話，你說了一句話以后惫确，往往很快會重復(fù)一遍手报，但是你不會隔了5個小時又重復(fù)這句話，這種特點在文件里面也存在著改化，到處都是這種例子掩蛤，比如你在編程的時候，你定義了一個變量int nCount陈肛，這個nCount一般你很快就會用到揍鸟，不會離得很遠(yuǎn)。我們前面所說的距離代表了你隔了多久再說這句話句旱，這個距離一般不大阳藻，既然如此晰奖，應(yīng)該以離當(dāng)前字符串距離最近的那個作為記錄的依據(jù)（也就是指向離自己最近那個重復(fù)字符串），這樣的話腥泥，所有的標(biāo)記都是一些短距離匾南，比如都是3、4蛔外、5蛆楞、6、7而不會是3夹厌、5臊岸、78、965等等尊流，如果大多數(shù)都是一些短距離帅戒，那么這些短距離就可以用短一些的比特表示，長一些的距離不太常見崖技，則用一些長一些的比特表示逻住。這樣， 總體的表示長度就會減少迎献。好了瞎访，我們前面得到了（5,3）、（7吁恍、3）這種記錄重復(fù)的表示扒秸，距離有兩種：5、7冀瓦；長度只有1種：3伴奥。咋編碼？越短越好翼闽。
既然表示的比特越短越好拾徙，3表示為0、5表示為10感局、7表示為11尼啡，行不行？這樣（5,3）,（7,3）就只需要表示為100询微、110崖瞭，這樣豈不是很短？貌似可以撑毛，貌似很高效书聚。
但解壓縮遇到10這兩個比特的時候，怎么知道10表示5呢？這種表示方法是一個映射表寺惫，稱為碼表疹吃。我們設(shè)計的上面這個例子的碼表如下：
3-->0
5-->10
7-->11
這個碼表也得傳過去或者記錄在壓縮文件里才行啊，否則無法解壓縮西雀，但會不會記錄了碼表以后整體空間又變大了萨驶，會不會起不到壓縮的作用？而且一個碼表怎么記錄艇肴？碼表記錄下來也是一堆數(shù)據(jù)腔呜，是不是也需要編碼？碼表是否可以繼續(xù)壓縮再悼？那豈不是又需要新的碼表核畴？壓縮會不會是一個永無止境的過程？作為一個入門級的同學(xué)冲九，大概想到這兒就不容易想下去了谤草。
3 LZ編碼思想
上面我們說的重復(fù)字符串用指針標(biāo)記記錄下來，這種方法就是LZ這兩個人提出來的莺奸，理解起來比較簡單丑孩。后面分析（5,3）這種指針標(biāo)記應(yīng)該怎么編碼的時候，就涉及到一種非常廣泛的編碼方式灭贷，Huffman編碼温学，Huffman大致和香農(nóng)是一個時代的人，這種編碼方式是他在MIT讀書的時候提出來的甚疟。接下來仗岖，我們來看看ZIP是怎么做的。
以上面的例子览妖，一個很簡單的示意圖如下：
可以看出轧拄，ZIP中使用的LZ77算法和前面分析的類似，當(dāng)然黄痪，如果仔細(xì)對比的話紧帕，ZIP中使用的算法和LZ提出來的LZ77算法其實還是有差異的盔然，不過我建議不用仔細(xì)去扣里面的差異桅打，思想基本是相同的，我們后面會簡要分析一下兩者的差異愈案。LZ77算法一般稱為“滑動窗口壓縮”挺尾，我們前面說過，該算法的核心是在前面的歷史數(shù)據(jù)中尋找重復(fù)字符串站绪，但如果要壓縮的文件有100MB遭铺，是不是從文件頭開始找？不是，這里就涉及前面提過的一個規(guī)律魂挂，重復(fù)現(xiàn)象是具有局部性的甫题，它的基本假設(shè)是，如果一個字符串要重復(fù)涂召，那么也是在附近重復(fù)坠非，遠(yuǎn)的地方就不用找了，因此設(shè)置了一個滑動窗口果正，ZIP中設(shè)置的滑動窗口是32KB炎码，那么就是往前面32KB的數(shù)據(jù)中去找，這個32KB隨著編碼不斷進(jìn)行而往前滑動秋泳。當(dāng)然潦闲，理論上講，把滑動窗口設(shè)置得很大迫皱，那樣就有更大的概率找到重復(fù)的字符串歉闰，壓縮率不就更高了？初看起來如此卓起，找的范圍越大新娜，重復(fù)概率越大，不過仔細(xì)想想既绩，可能會有問題概龄，一方面，找的范圍越大饲握，計算量會增大私杜，不顧一切地增大滑動窗口，甚至不設(shè)置滑動窗口救欧，那樣的軟件可能不可用衰粹，你想想，現(xiàn)在這種方式笆怠，我們在壓縮一個大文件的時候铝耻，速度都已經(jīng)很慢了，如果增大滑動窗口蹬刷，速度就更慢瓢捉，從工程實現(xiàn)角度來說，設(shè)置滑動窗口是必須的办成；另一方面泡态，找的范圍越大，距離越遠(yuǎn)迂卢，出現(xiàn)的距離很多某弦，也不利于對距離進(jìn)行進(jìn)一步壓縮吧桐汤，我們前面說過，距離和長度最好出現(xiàn)的值越少越好靶壮，那樣更好壓縮怔毛，如果出現(xiàn)的很多，如何記錄距離和長度可能也存在問題腾降。不過馆截，我相信滑動窗口設(shè)置得越大，最終的結(jié)果應(yīng)該越好一些蜂莉，不過應(yīng)該不會起到特別大的作用蜡娶，比如壓縮率提高了5%，但計算量增加了10倍映穗，這顯然有些得不償失窖张。
在第一個圖中，“容易蚁滋∷藿樱”是一個重復(fù)字符串，距離distance=5辕录，字符串長度length=3睦霎。當(dāng)對這三個字符壓縮完畢后，接下來滑動窗口向前移動3個字符走诞，要壓縮的是“我...”這個字符串副女，但這個串在滑動窗口內(nèi)沒找到，所以無法使用distance+length的方式記錄蚣旱。這種結(jié)果稱為literal碑幅。literal的中文含義是原義的意思，表示沒有使用distance+length的方式記錄的那些普通字符塞绿。literal是不是就用原始的編碼方式沟涨，比如Unicode方式表示？ZIP里不是這么做的异吻，ZIP把literal認(rèn)為也是一個數(shù)裹赴，盡管不能用distance+length表示，但不代表不可以繼續(xù)壓縮诀浪。另外棋返，如果“我”出現(xiàn)在了滑動窗口內(nèi)，是不是就可以用distance+length的方式表示笋妥？也不是懊昨，因為一個字出現(xiàn)重復(fù)，不值得用這種方式表示春宣，兩個字呢酵颁？distance+length就是兩個整數(shù)，看起來也不一定值得月帝，ZIP中確實認(rèn)為2個字節(jié)如果在滑動窗口內(nèi)找到重復(fù)躏惋，也不管，只有3個字節(jié)以上的重復(fù)字符串嚷辅，才會用distance+length表示簿姨，重復(fù)字符串的長度越長越好，因為不管多長簸搞，都用distance+length表示就行了扁位。
這樣的話，一段字符串最終就可以表示成literal趁俊、distance+length這兩種形式了域仇。LZ系列算法的作用到此為止，下面寺擂，Phil Katz考慮使用Huffman對上面的這些LZ壓縮后的結(jié)果進(jìn)行二次壓縮暇务。個人認(rèn)為接下來的過程才是ZIP的核心，所以我們要熟悉一下Huffman編碼怔软。
4 Huffman編碼思想
上面LZ壓縮結(jié)果有三類（literal垦细、distance、length）挡逼，我們拿出distance一類來舉例括改。distance代表重復(fù)字符串離前一個一模一樣的字符串之間的距離，是一個大于0的整數(shù)家坎。如何對一個整數(shù)進(jìn)行編碼呢叹谁？一種方法是直接用固定長度表示，比如采用計算機(jī)里面描述一個4字節(jié)整數(shù)那樣去記錄乘盖，這也是可以的焰檩，主要問題當(dāng)然是浪費(fèi)存儲空間，在ZIP中订框，distance這個數(shù)表示的是重復(fù)字符串之間的距離析苫，顯然，一般而言穿扳，越小的距離衩侥，出現(xiàn)的數(shù)量可能越多，而越大的距離矛物，出現(xiàn)的數(shù)量可能越少茫死，那么，按照我們前面所說的原則履羞，小的值就用較少比特表示峦萎，大的值就用較多比特表示屡久，在我們這個場景里，distance當(dāng)然也不會無限大爱榔，比如不會超過滑動窗口的最大長度被环，假如對一個文件進(jìn)行LZ壓縮后，得到的distance值為：
這個例子里详幽，3出現(xiàn)了4次筛欢，4出現(xiàn)了3次，5出現(xiàn)了1次唇聘，6出現(xiàn)了1次版姑。當(dāng)然，不同的文件得到的結(jié)果不同迟郎，這里只是舉一個典型的例子剥险，因為只有4種值，所以我們沒有必要對其它整數(shù)編碼谎亩。只需要對這4個整數(shù)進(jìn)行編碼即可（此時需要動態(tài)Huffman編碼）炒嘲。
那么，怎么設(shè)計一個算法匈庭，符合3的編碼長度最短夫凸？6的編碼長度最長這種直觀上可行的原則（我們并沒有說這是理論上最優(yōu)的方式）呢？
看起來似乎很難想出來阱持。我們先來簡化一下夭拌，用固定長度表示。這里有4個整數(shù)衷咽，只要使用2個比特表示即可鸽扁。于是這樣表示就很簡單：
00-->3； 01-->4镶骗； 10-->5; 11-->6桶现。
00、01這種編碼結(jié)果稱為碼字鼎姊，碼字的平均長度是2骡和。上面這個對應(yīng)關(guān)系即為碼表，在壓縮時相寇，需要將碼表放在最前面慰于，后面的數(shù)字就用碼字表示，解碼時唤衫，先把碼表記錄在內(nèi)存里婆赠，比如用一個哈希表記錄下來，解壓縮時佳励，遇到00休里，就解碼為3等等蛆挫。
因為出現(xiàn)了9個數(shù)，所以全部碼字總長度為18個比特份帐。（我們暫時不考慮記錄碼表到底要占多少空間）
想要編碼結(jié)果更短璃吧，因為3出現(xiàn)的最多楣导，所以考慮把3的碼字縮短點废境，比如3是不是可以用1個比特表示，這樣才算縮短吧筒繁，因為0和1只是二進(jìn)制的一個標(biāo)志噩凹，所以用0還是1沒有本質(zhì)區(qū)別，那么毡咏，我們暫定把3用比特0表示驮宴。那么，4、5、6還能用0開頭的碼字表示呢史飞？
這樣會存在問題冬竟，因為4、5杠愧、6的編碼結(jié)果如果以0開頭，那么，在解壓縮的時候纹安，遇到比特0，就不知道是表示3還是表示4砂豌、5厢岂、6了，就無法解碼阳距，當(dāng)然塔粒，似乎理論上也不是不可以，比如可以往后解解看筐摘，比如假定0表示3的條件下往后解卒茬，如果無效則說明這個假設(shè)不對，但這種方式很容易出現(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應(yīng)該以11開頭凶异，就定為11行不行呢蜀撑？也不行，因為6就不知道怎么編碼了酷麦，6也不能以0開頭，也不能以10襟衰、11開頭贴铜，那就無法表示了，所以瀑晒，迫不得已绍坝，我們必須把5擴(kuò)展一位，比如110苔悦，那么轩褐，6顯然就可以用111表示了，反正也沒有其他數(shù)了玖详。于是我們得到了最終的碼表：
0-->3把介；10-->4；110-->5蟋座；111-->6拗踢。
看起來，編碼結(jié)果只能是這樣了向臀，我們來算一下巢墅，碼字的總長度減少了沒有，原來的9個數(shù)是3、6君纫、4驯遇、3、4蓄髓、3叉庐、4、3会喝、5陡叠，分別對應(yīng)的碼字是：
這棵樹也稱為碼樹逢艘，其實就是碼表的一種形式化描述，每個節(jié)點（除了葉子節(jié)點）都會分出兩個分支骤菠，左分支代表比特0它改，右邊分支代表1，從根節(jié)點到葉子節(jié)點的一個比特序列就是碼字商乎。因為只有葉子節(jié)點可以是碼字央拖，所以這樣也符合一個碼字不能是另一個碼字的前綴這一原則。說到這里，可以說一下另一個話題爬泥，就是一個映射表map在內(nèi)存中怎么存儲柬讨，沒有相關(guān)經(jīng)驗的可以跳過，map實現(xiàn)的是key-->value這樣的一個表袍啡，map的存儲一般有哈希表和樹形存儲兩類踩官，樹形存儲就可以采用上面這棵樹，樹的中間節(jié)點并沒有什么含義境输，葉子節(jié)點的值表示value蔗牡，從根節(jié)點到葉子節(jié)點上分支的值就是key，這樣比較適合存儲那些key由多個不等長字符組成的場合嗅剖，比如key如果是字符串辩越，那么把二叉樹的分支擴(kuò)展很多，成為多叉樹信粮，每個分支就是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)建出來痴柔。于是我們會遇到一個最大的問題，那就是這棵樹太大了疫向，怎么記錄呢咳蔚？
好了，個人認(rèn)為到了ZIP的核心了搔驼，那就是碼樹應(yīng)該怎么縮小谈火，以及碼樹怎么記錄的問題。
5 Huffman碼樹的記錄方式
分析上面的例子舌涨，看看這個碼表：
0-->3糯耍；10-->4；110-->5；111-->6温技。
我們之前提過革为，0和1就是二進(jìn)制的一個標(biāo)志，互換一下其實根本不影響編碼長度舵鳞，所以震檩，下面的碼表其實是一樣的：
1-->3；00-->4蜓堕；010-->5抛虏；011-->6。
1-->3套才；01-->4迂猴；000-->5；001-->6背伴。
0-->3沸毁；11-->4；100-->5挂据；101-->6以清。
。崎逃。。眉孩。个绍。
這些都可以，而且編碼長度完全一樣浪汪，只是碼字不同而已巴柿。
對比一下第一個和第二個例子，對應(yīng)的碼樹是這個樣子：
也就是說死遭，我們把碼樹的任意節(jié)點的左右分支旋轉(zhuǎn)（0广恢、1互換），也可以稱為樹的左右互換呀潭，其實不影響編碼長度钉迷，也就是說，這些碼表其實都是一樣好的钠署，使用哪個都可以糠聪。
這個規(guī)律暗示了什么信息呢？暗示了碼表可以怎么記錄呢谐鼎？Phil Katz當(dāng)年在牢里也深深地思考了這一問題舰蟆。
為了體會Phil Katz當(dāng)時的心情，我們有必要盯著這兩棵樹思考幾分鐘：怎么把一顆樹用最少的比特記錄下來？
Phil Katz當(dāng)時思考的邏輯我猜是這樣的身害，既然這些樹的壓縮程度都一樣味悄，那干脆使用最特殊的那棵樹，反正壓縮程度都一樣塌鸯，只要ZIP規(guī)定了這棵樹的特殊性傍菇，那么我記錄的信息就可以最少，這種特殊化的思想在后面還會看到界赔。不同的樹當(dāng)然有不同的特點丢习，比如數(shù)據(jù)結(jié)構(gòu)里面常見的平衡樹也是一類特殊的樹，他選的樹就是左邊那棵淮悼，這棵樹有一個特點咐低，越靠左邊越淺，越往右邊越深袜腥，是這些樹中最不平衡的樹见擦。ZIP里的壓縮算法稱為Deflate算法，這棵樹也稱為Deflate樹羹令，對應(yīng)的解壓縮算法稱為Inflate鲤屡，Deflate的大致意思是把輪胎放氣了，意為壓縮福侈；Inflate是給輪胎打氣的意思酒来，意為解壓。那么肪凛，Deflate樹的特殊性又帶來什么了堰汉？
揭曉答案吧，Phil Katz認(rèn)為換來換去只有碼字長度不變伟墙，如果規(guī)定了一類特殊的樹翘鸭，那么就只需要記錄碼字長度即可。比如戳葵，一個有效的碼表是0-->3就乓；10-->4；110-->5拱烁；111-->6生蚁。但只需要記錄這個對應(yīng)關(guān)系即可：
3 4 5 6
1 2 3 3
也就是說，把1邻梆、2守伸、3、3記錄下來浦妄，解壓一邊照著左邊那棵樹的形狀構(gòu)造一顆樹尼摹，然后只需要1见芹、2、3蠢涝、3這個信息自然就知道是0玄呛、10、110和二、111徘铝。這就是Phil Katz想出來的ZIP最核心的一點：這棵碼樹用碼字長度序列記錄下來即可。
當(dāng)然惯吕，只把1惕它、2、3废登、3這個序列記錄下來還不行淹魄，比如不知道111對應(yīng)5還是對應(yīng)6？
所以堡距，構(gòu)造出樹來只是知道了有哪些碼字了甲锡，但是這些碼字到底對應(yīng)哪些整數(shù)還是不知道。
Phil Katz于是又出現(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)造出了碼字，這些碼字對應(yīng)的整數(shù)一個比一個大祝高，假如我們知道編碼前的整數(shù)就是3栗弟、4、5褂策、6這四個數(shù)横腿，那就能對應(yīng)起來了，不過到底是哪四個還是不知道敖锛拧耿焊？這個整數(shù)可以表示距離啊，距離不知道怎么去解碼LZ遍搞？
Phil Katz又想了罗侯，既然distance的范圍是1-32768，那么就按照這個順序記錄溪猿。上面的例子1和2沒有钩杰，那就記錄長度0。所以記錄下來的碼字長度序列為：
0诊县、0讲弄、1、2依痊、3避除、3、0胸嘁、0瓶摆、0、0性宏、0群井、............
這樣就知道構(gòu)造出來的碼字對應(yīng)哪個整數(shù)了吧，但因為distance可能的值很多（32768個）毫胜，但實際出現(xiàn)的往往不多书斜，中間會出現(xiàn)很多0（也就是根本就沒出現(xiàn)這個距離）诬辈，不過這個問題倒是可以對連續(xù)的0做個特殊標(biāo)記，這樣是不是就行了呢菩佑？還有什么問題自晰？
我們還是要站在時代的高度來看待這個問題。我們明白稍坯，每個distance肯定對應(yīng)唯一一個碼字酬荞，使用Huffman編碼可以得到所有碼字，但是因為distance可能非常多瞧哟，雖然一般不會有32768這么多混巧，但對一個大些的文件進(jìn)行LZ編碼，distance上千還是很正常的勤揩，所以這棵樹很大咧党，計算量、消耗的內(nèi)存都容易超越了那個時代的硬件條件陨亡，那么怎么辦呢傍衡？這里再次體現(xiàn)了Phil Katz對Huffman編碼掌握的深度，他把distance劃分成多個區(qū)間负蠕，每個區(qū)間當(dāng)做一個整數(shù)來看蛙埂，這個整數(shù)稱為Distance Code。當(dāng)一個distance落到某個區(qū)間遮糖，則相當(dāng)于是出現(xiàn)了那個Code绣的，多個distance對應(yīng)于一個Distance Code，Distance雖然很多欲账，但Distance Code可以劃分得很少屡江，只要我們對Code進(jìn)行Huffman編碼，得到Code的編碼后赛不，Distance Code再根據(jù)一定規(guī)則擴(kuò)展出來惩嘉。那么，劃分多少個區(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)頻率越高鄙皇，所以距離值小的時候芜赌，劃分密一些，這樣相當(dāng)于一個放大鏡，可以對小的距離進(jìn)行更精細(xì)地編碼鼻种，使得其編碼長度與其出現(xiàn)次數(shù)盡量匹配鲤看；對于距離較大那些，因為出現(xiàn)頻率低博烂，所以可以適當(dāng)放寬一些。另一個原因是漱竖，只要知道這個區(qū)間Code的碼字禽篱，那么對于這個區(qū)間里面的所有distance，后面追加相應(yīng)的多個比特即可馍惹，比如躺率，17-24這個區(qū)間的Huffman碼字是110，因為17-24這個區(qū)間有8個整數(shù)万矾，于是按照下面的規(guī)則即可獲得其distance對應(yīng)的碼字：
17-->110 000
18-->110 001
19-->110 010
20-->110 011
21-->110 100
22-->110 101
23-->110 110
24-->110 111
這樣計算復(fù)雜度和內(nèi)存消耗是不是很小了悼吱，因為需要進(jìn)行Huffman編碼的整數(shù)一下字變少了，這棵樹不會多大良狈，計算起來時間和空間復(fù)雜度降低后添，擴(kuò)展起來也比較簡單。當(dāng)然薪丁，從理論上來說遇西，這樣的編碼方式實際上將編碼過程分為了兩級馅精，并不是理論上最優(yōu)的，把所有distance當(dāng)作一個大空間去編碼才可能得到最優(yōu)結(jié)果粱檀，不過還是那句話洲敢，工程實現(xiàn)的限制，在壓縮軟件實現(xiàn)上茄蚯，我們不能用壓縮率作為衡量一個算法優(yōu)劣的唯一指標(biāo)压彭，其實耗費(fèi)的時間和空間同樣是指標(biāo)，所以需要看綜合指標(biāo)第队。很多其他軟件也一樣哮塞，擴(kuò)展性、時間空間復(fù)雜度凳谦、穩(wěn)定性忆畅、移植性、維護(hù)的方便性等等是工程上很重要的東西尸执。我沒有看過RAR是如何壓縮的家凯，有可能是在類似的地方進(jìn)行了改進(jìn)，如果如此如失，那也是站在巨人的肩膀上绊诲，而且硬件條件不同，進(jìn)行一些改進(jìn)也并不奇怪褪贵。
具體來說掂之，Phil Katz把distance劃分為30個區(qū)間，如下圖：
個圖是我從David Salomon的《Data Compression The Complete Reference》這本書（第四版）中拷貝出來的脆丁，下面的有些圖也是世舰，如果需要對數(shù)據(jù)壓縮進(jìn)行全面的了解，這本書幾乎是最全的了槽卫，強(qiáng)烈推薦跟压。
當(dāng)然，你要問為什么是30個區(qū)間歼培，我也沒分析過震蒋，也許是復(fù)雜度和壓縮率經(jīng)過試驗之后的一種折中吧。
其中躲庄，左邊的Code表示區(qū)間的編號查剖，是0-29，共30個區(qū)間噪窘，這只是個編號梗搅，沒有特別的含義，但Huffman就是對0-29這30個Code進(jìn)行編碼的，得到區(qū)間的碼字无切；
Extra bits表示distance的碼字需要在Code的碼字基礎(chǔ)上擴(kuò)展幾位，比如0就表示不擴(kuò)展丐枉，最大的13表示要擴(kuò)展13位哆键，因此，最大的區(qū)間包含的distance數(shù)量為8192個瘦锹。
Distance一列則表示這個區(qū)間涵蓋的distance范圍籍嘹。
理解了碼樹如何有效記錄，以及如何縮小碼樹的過程弯院，我覺得就理解了ZIP的精髓辱士。
6 literal和length的壓縮方式
說完了distance，LZ編碼結(jié)果還有兩類：literal和length听绳。這兩類也利用了類似于distance的方式進(jìn)行壓縮颂碘。
前面分析過，literal表示未匹配的字符椅挣，我們前面之所以拿漢字來舉例头岔，完全是為了便于理解，ZIP之所以是通用壓縮鼠证，它實際上是針對字節(jié)作為基本字符來編碼的峡竣，所以一個literal至多有256種可能。
length表示重復(fù)字符串長度量九，length=1當(dāng)然不會出現(xiàn)适掰，因為一個字符不值得用distance+length去記錄，重復(fù)字符串當(dāng)然越長越好荠列，Phil Katz（下面還是簡稱PK了类浪，拷貝太麻煩）認(rèn)為，length=2也不值得用這種方式記錄弯予，還是太短了戚宦，所以PK把length最小值認(rèn)為是3，必須3個以上字符的字符串出現(xiàn)重復(fù)才用distance+length記錄锈嫩。那么受楼，最大的length是多少呢？理論上當(dāng)然可以很長很長呼寸，比如一個文件就是連續(xù)的0艳汽，這個重復(fù)字符串長度其實接近于這個文件的實際長度。但是PK把length的范圍做了限制对雪，限定length的個數(shù)跟literal一樣河狐，也只有256個，因為PK認(rèn)為，一個重復(fù)字符串達(dá)到了256個已經(jīng)很長了馋艺，概率非常姓じ伞；另外捐祠，其實哪怕超過了256碱鳞，我還是認(rèn)為是一段256再加上另外一段，增加一個distance+length就行了嘛踱蛀，并不影響結(jié)果窿给。而且這樣做，我想同樣也考慮了硬件條件吧率拒。
初看有點奇怪的在于崩泡，將literal和length二者合二為一，什么意思呢猬膨？就是對這兩種整數(shù)（literal本質(zhì)上是一個字節(jié)）共用一個Huffman碼表角撞，一會兒解釋為什么。PK對Huffman的理解我覺得達(dá)到了爐火純青的地步寥掐，前面已經(jīng)看到靴寂，后面還會看到。他認(rèn)為Huffman編碼的輸入反正說白了就是一個集合的元素就行召耘，無論這個元素是啥百炬，所以多個集合看做一個集合當(dāng)作Huffman編碼的輸入沒啥問題。literal用整數(shù)0-255表示污它，256是一個結(jié)束標(biāo)志剖踊，解碼以后結(jié)果是256表示解碼結(jié)束；從257開始表示length衫贬，所以257這個數(shù)表示length=3德澈，258這個數(shù)表示length=4等等，但PK也不是一直這么一一對應(yīng)固惯，和distance一樣梆造，也是把length（總共256個值）劃分為29個區(qū)間，其結(jié)果如下圖：
其中的含義和distance類似葬毫，不再贅述镇辉，所以literal/length這個Huffman編碼的輸入元素一共285個，其中256表示解碼結(jié)束標(biāo)志贴捡。為什么要把二者合二為一呢忽肛？因為當(dāng)解碼器接收到一個比特流的時候，首先可以按照literal/length這個碼表來解碼烂斋，如果解出來是0-255屹逛，就表示未匹配字符础废，如果是256，那自然就結(jié)束罕模，如果是257-285之間评腺，則表示length，把后面擴(kuò)展比特加上形成length后手销，后面的比特流肯定就表示distance歇僧，因此，實際上通過一個Huffman碼表锋拖，對各類情況進(jìn)行了統(tǒng)一，而不是通過加一個什么標(biāo)志來區(qū)分到底是literal還是重復(fù)字符串祸轮。
好了兽埃，理解了上面的過程，就理解了ZIP壓縮的第二步适袜，第一步是LZ編碼柄错，第二步是對LZ編碼后結(jié)果（literal、distance苦酱、length）進(jìn)行的再編碼售貌，因為literal/length是一個碼表，我稱其為Huffman碼表1疫萤，distance那個碼表稱為Huffman碼表2颂跨。前面我們已經(jīng)分析了，Huffman碼樹用一個碼字長度序列表示扯饶，稱為CL（Code Length）恒削，記錄兩個碼表的碼字長度序列分別記為CL1、CL2尾序。碼樹記錄下來钓丰，對literal/length的編碼比特流稱為LIT比特流；對distance的編碼比特流稱為DIST比特流每币。
按照上面的方法携丁，LZ的編碼結(jié)果就變成四塊：CL1、CL2兰怠、LIT比特流梦鉴、DIST比特流。CL1痕慢、CL2是碼字長度的序列尚揣，這個序列說白了就是一堆正整數(shù)，因此掖举，PK繼續(xù)深挖快骗，認(rèn)為這個序列還應(yīng)該繼續(xù)壓縮，也就是說，對碼表進(jìn)行壓縮方篮。
7 對CL進(jìn)行再次壓縮的方法
這里仍然沿用Huffman的想法名秀，因為CL也是一堆整數(shù)，那么當(dāng)然可以再次應(yīng)用Huffman編碼藕溅。不過在這之前匕得，PK對CL序列進(jìn)行了一點處理。這個處理也是很精巧的巾表。
CL序列表示一系列整數(shù)對應(yīng)的碼字長度汁掠，對于literal/length來說，總共有0-285這么多符號集币，所以這個序列長度為286考阱，每個符號都有一個碼字長度，當(dāng)然鞠苟，這里面可能會出現(xiàn)大段連續(xù)的0乞榨，因為某些字符或長度不存在，尤其是對英文文本編碼的時候当娱，非ASCII字符就根本不會出現(xiàn)吃既，length較大的值出現(xiàn)概率也很小，所以出現(xiàn)大段的0是很正常的跨细；對于distance也類似鹦倚，也可能出現(xiàn)大段的0。PK于是先進(jìn)行了一下游程編碼扼鞋。在說什么是游程編碼之前申鱼，我們談?wù)凱K對CL序列的認(rèn)識。
literal/length的編碼符號總共286個（回憶：256個Literal+1個結(jié)束標(biāo)志+29個length區(qū)間）云头，distance的編碼符號總共30個（回憶：30個區(qū)間）捐友，所以這顆碼樹不會特別深，Huffman編碼后的碼字長度不會特別長溃槐，PK認(rèn)為最長不會超過15匣砖，也就是樹的深度不會超過15，這個是否是理論證明我還沒有分析昏滴，有興趣的同學(xué)可以分析一下猴鲫。因此，CL1和CL2這兩個序列的任意整數(shù)值的范圍是0-15谣殊。0表示某個整數(shù)沒有出現(xiàn)（比如literal=0x12, length Code=8, distance Code=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（二進(jìn)制）, 3, 3, 3, 6, 16, 11（二進(jìn)制）, 16, 00（二進(jìn)制）, 17,011（二進(jìn)制）, 2, 16, 00（二進(jìn)制）這是什么意思呢回溺？因為CL的范圍是0-15，PK認(rèn)為重復(fù)出現(xiàn)2次太短就不用游程編碼了混萝，所以游程長度從3開始遗遵。用16這個特殊的數(shù)表示重復(fù)出現(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（二進(jìn)制）表示連續(xù)出現(xiàn)6個0；18,0111110（二進(jìn)制）表示連續(xù)出現(xiàn)62個0驰怎〔玻總之記住，0-15是CL可能出現(xiàn)的值县忌，16表示除了0以外的其它游程掂榔；17继效、18表示0游程。因為二進(jìn)制實際上也是個整數(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，所以對應(yīng)的有兩個SQ1绩郎、SQ2潘鲫。
針對SQ1、SQ2肋杖，PK用了第三個Huffman碼表來對這兩個序列進(jìn)行編碼溉仑。通過統(tǒng)計各個整數(shù)（0-18范圍內(nèi)）的出現(xiàn)次數(shù)，按照相同的思路状植，對SQ1和SQ2進(jìn)行了Huffman編碼浊竟，得到的碼流記為SQ1 bits和SQ2 bits。同時津畸，這里又需要記錄第三個碼表振定，稱為Huffman碼表3。同理肉拓，這個碼表也用相同的方法記錄后频，也等效為一個碼長序列，稱為CCL暖途，因為至多有0-18個卑惜，PK認(rèn)為樹的深度至多為7，于是CCL的范圍是0-7驻售。
當(dāng)?shù)玫搅薈CL序列后露久，PK決定不再折騰，對這個序列用普通的3比特定長編碼記錄下來即可芋浮，即000代表0,111代表7抱环。但實際上還有一點小折騰，就是最后這個序列如果全部記錄纸巷，那就需要19*3=57個比特镇草，PK認(rèn)為CL序列里面CL范圍為0-15，特殊的幾個值是16瘤旨、17梯啤、18，如果把CCL序列位置置換一下存哲，把16因宇、17七婴、18這些放前面，那么這個CCL序列就很可能最后面跟著一串0（因為CL=14,15這些很可能沒有）察滑，所以最后還引入了一個置換打厘，其示意圖如下，分別表示置換前的CCL序列和置換后的CCL贺辰』Фⅲ可以看出，16饲化、17莽鸭、18對應(yīng)的CCL被放到了前面，這樣如果尾部出現(xiàn)了一些0吃靠，就只需要記錄CCL長度即可硫眨，后面的0不記錄〕部椋可以繼續(xù)節(jié)省一些比特礁阁，不過這個例子尾部置換后只有1個0：
不過粗看起來，這個置換效果并不好族奢，我一開始接觸這個置換的時候氮兵，我覺得應(yīng)該按照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卻按照上面的順序罩驻。我總是認(rèn)為，我覺得牛人可能出錯了的時候护赊，往往是我自己錯了惠遏，所以我又仔細(xì)想了一下，上面的順序特點比較明顯骏啰，直觀上看节吮，PK認(rèn)為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)化程度呜师，簡直完全取決于程序員對那個東西細(xì)節(jié)的理解的深度。當(dāng)我仔細(xì)研究了ZIP壓縮算法的過程之后贾节，我對PK這種深夜埋頭冥思苦想的大牛佩服得五體投地汁汗。
8 Deflate壓縮數(shù)據(jù)格式
ZIP的格式實際上就是Deflate壓縮碼流外面套了一層文件相關(guān)的信息，這里先介紹Deflate壓縮碼流格式角寸。其格式為：
Header：3個比特菩混，第一個比特如果是1，表示此部分為最后一個壓縮數(shù)據(jù)塊扁藕；否則表示這是.ZIP文件的某個中間壓縮數(shù)據(jù)塊沮峡，但后面還有其他數(shù)據(jù)塊。這是ZIP中使用分塊壓縮的標(biāo)志之一亿柑；第2邢疙、3比特表示3個選擇：壓縮數(shù)據(jù)中沒有使用Huffman、使用靜態(tài)Huffman望薄、使用動態(tài)Huffman疟游，這是對LZ77編碼后的literal/length/distance進(jìn)行進(jìn)一步編碼的標(biāo)志。我們前面分析的都是動態(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個重復(fù)字符串喘沿，distance都為0也是一個CL闸度。
HCLEN：4比特，記錄Huffman碼表3中碼長序列（CCL）個數(shù)的一個變量蚜印。后面CCL個數(shù)等于HCLEN+4莺禁。PK認(rèn)為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é)束標(biāo)志，即literal/length這個碼表輸入符號位256的編碼比特峭竣。對倒數(shù)第1塘辅、2內(nèi)容塊進(jìn)行解碼時，首先利用Huffman碼表1進(jìn)行解碼皆撩，如果解碼所得整數(shù)位于0-255之間扣墩，表示literal未匹配字符，接下來仍然利用Huffman碼表1解碼扛吞；如果位于257-285之間呻惕，表示length匹配長度，之后需要利用Huffman碼表2進(jìn)行解碼得到distance偏移距離滥比；如果等于256亚脆，表示數(shù)據(jù)塊解碼結(jié)束。
9 ZIP文件格式解析
上面各節(jié)對ZIP的原理進(jìn)行了分析盲泛，這一節(jié)我們來看一個實際的例子濒持，為了更好地描述，我們盡量把這個例子舉得簡單一些寺滚。下面是我隨便從一本書拷貝出來的一段較短的待壓縮的英文文本數(shù)據(jù)：
As mentioned above,there are many kinds of wireless systems other than cellular.
這段英文文本長度為80字節(jié)柑营。經(jīng)過ZIP壓縮后，其內(nèi)容如下：
可以看到村视，第1官套、2字節(jié)就是PK。看著怎么比原文還長奶赔，這怎么叫壓縮惋嚎？實際上，這里面大部分內(nèi)容是ZIP的文件標(biāo)記開銷纺阔，真正壓縮的內(nèi)容（也就是我們前面提到的Deflate數(shù)據(jù)瘸彤，劃線部分都是ZIP文件開銷）其實肯定要比原文短（否則ZIP不會啟用壓縮），我們這個例子是個短文本笛钝，但對于更長的文本而言质况，那ZIP文件總體長度肯定是要短于原始文本的。上面的這個ZIP文件玻靡，可以看到好幾個以PK開頭的區(qū)域结榄，也就是不同顏色的劃線區(qū)域，這些其實都是ZIP文件本身的開銷囤捻。
所以臼朗，我們首先來看一看ZIP的格式，其格式定義為：
[local file header 1][file data 1][data descriptor 1]..........[local file header n][file data n][data descriptor n][archive decryption header] [archive extra data record] [central directory][zip64 end of central directory record][zip64 end of central directory locator] [end of central directory record]local file header+file data+data descriptor這是一段ZIP壓縮數(shù)據(jù)蝎土，在一個ZIP文件里视哑，至少有一段，至多那就不好說了誊涯，假如你要壓縮的文件一共有10個挡毅，那這個地方至少會有10段，ZIP對每個文件進(jìn)行了獨立壓縮暴构，RAR在此進(jìn)行了改進(jìn)跪呈，將多個文件聯(lián)合起來進(jìn)行壓縮，提高了壓縮率取逾。local file header的格式如下：
4+2+2+2+4+2+2+n+17 = 35+len(filename)
可見耗绿，起始的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ù)晶丘，上面這個例子包含了central directory和end of central directory record，一般這兩部分也是必須的。central directory以0x50浅浮、0x4B沫浆、0x01、0x02開頭滚秩；end of central directory record以0x50专执、0x4B、0x05郁油、0x06開頭本股，其含義比較簡單，分別對應(yīng)于上面ZIP數(shù)據(jù)那個圖的藍(lán)色和綠色部分桐腌，下面是兩者的格式：
約42個字節(jié)
end of central directory record格式：
19個字節(jié)
這幾張圖是我從網(wǎng)上找的拄显，寫得比較清晰。對于其中的含義案站，解釋起來也比較簡單躬审，我分析的結(jié)果如下：注意ZIP采用的低字節(jié)優(yōu)先，在一個字節(jié)里面低位優(yōu)先蟆盐，需要反過來看承边。
Local File Header: (38B,304b)00001010 11010010 11000000 00100000 (signature)00000000 00010100 (version:20)00000000 00000000 (generalBitFlag)00000000 00001000 (compressionMethod:8)01001101 10001110 (lastModTime:19854)01000101 00100101 (lastModDate:17701)01010100101011010100001100111100 (CRC32)00000000 00000000 00000000 01001000 (compressedSize:72)00000000 00000000 00000000 01010000 (uncompressedSize:80)00000000 00001000 (filenameLength:8)00000000 00000000 (extraFieldLength:0)0010101010100110110011100010111001110100001011100001111000101110 (fileName:Test.txt) (extraField)Central File Header: (54B,432b)00001010110100101000000001000000 (signature)0000000000010100 (versionMadeBy:20)0000000000010100 (versionNeeded:20)0000000000000000 (generalBitFlag)0000000000001000 (compressionMethod:8)0100110110001110 (lastModTime:19854)0100010100100101 (lastModDate:17701)01010100101011010100001100111100 (CRC32)00000000000000000000000001001000 (compressedSize:72)00000000000000000000000001010000 (uncompressedSize:80)0000000000001000 (filenameLength:8)0000000000000000 (extraFieldLength:0)0000000000000000 (fileCommenLength:0)0000000000000000 (diskNumberStart)0000000000000001 (internalFileAttr)10000001100000000000000000100000 (externalFileAttr)00000000000000000000000000000000 (relativeOffsetLocalHeader)0010101010100110110011100010111001110100001011100001111000101110 (fileName:Test.txt) (extraField) (fileComment)end of Central Directory Record: (22B,176b)00001010110100101010000001100000 (signature)0000000000000000 (numberOfThisDisk:0)0000000000000000 (numberDiskCentralDirectory:0)0000000000000001 (EntriesCentralDirectDisk:1)0000000000000001 (EntriesCentralDirect:1)00000000000000000000000000110110 (sizeCentralDirectory:54)00000000000000000000000001101110 (offsetStartCentralDirectory:110)0000000000000000 (fileCommentLength:0) (fileComment)Local File Header Length:304Central File Header Length:432End Central Directory Record Length:176
可見，開銷總的長度為38+54+22=114字節(jié)石挂，整個文件長度為186字節(jié)博助，因此Deflate壓縮數(shù)據(jù)長度為72字節(jié)（576比特）。盡管這里看起來只是從80字節(jié)壓縮到72字節(jié)誊稚，那是因為這是一段短文本翔始，重復(fù)字符串出現(xiàn)較少，但如果文本較長里伯，那壓縮率就會增加城瞎，這里只是舉個例子。
下面對其中的關(guān)鍵部分疾瓮，也就是Deflate壓縮數(shù)據(jù)進(jìn)行解析脖镀。
10 Deflate解碼過程實例分析
我們按照ZIP格式把Deflate壓縮數(shù)據(jù)（72字節(jié)）提取出來，如下（每行8字節(jié)）：
101010000101001110001011101100000000000100000100001100001010001010001011101010100111101100000000011000111011100000111000101001010101001111001100000010001101001010010010000101101010101100001101101111010001111110001110111111100111001001110111011001110001010100101101000101001011001100011001000001001101111011011110000111010010001001100110111001000010011001101010101000110110000001110101010001101001001110001011011100100011110110100101110010101001011101110000111110000111100000110101110010110111111111001000100010011010001100001110000010101010111101101010100101111101011111100000
Deflate格式除了上面的介紹狼电，也可以參考RFC1951蜒灰，解析如下：
Header:101, 第一個比特是1，表示此部分為最后一個壓縮數(shù)據(jù)塊肩碟；后面的兩個比特01表示采用動態(tài)哈夫曼强窖、靜態(tài)哈夫曼、或者沒有編碼的標(biāo)志削祈，01表示采用動態(tài)Huffman翅溺；在RFC1951里面是這么說明的：
00 - no compression
01 - compressed with fixed Huffman codes
10 - compressed with dynamic Huffman codes
11 - reserved (error)
注意脑漫，這里需要按照低比特在先的方式去看，否則會誤以為是靜態(tài)Huffman咙崎。
接下來：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)了兩種重復(fù)字符串的長度，即3和4燥撞∽回顧這個圖可以更清楚：
繼續(xù)：HDIST:01010,記錄distance碼樹中碼長序列個數(shù)的一個變量，表示HDIST=10物舒，說明后面存在HDIST+1=11個CL2色洞，CL2即Distance Code=0-10被編碼的長度。
繼續(xù)：
HCLEN:0111,記錄Huffman碼樹3中碼長序列個數(shù)的一個變量冠胯，表示HCLEN=14（1110二進(jìn)制）火诸，即說明緊接著跟著HCLEN+4=18個CCL，前面已經(jīng)分析過荠察，CCL記錄了一個Huffman碼表置蜀，這個碼表可以用一個碼長序列表示，根據(jù)這個碼長序列可以得到碼表悉盆。于是接下來我們把后面的18*3=54個比特拷貝出來盯荤，上面的碼流目前解析為下面的結(jié)果：
101(Header) 01000(HLIT) 01010(HDIST) 0111(HCLEN) 000 101 110 110 000 000 000 010 000 010 000 110 000 101 000 101 000 101 (CCL)1101010100111101100000000011000111011100000111000101001010101001111001100000010001101001010010010000101101010101100001101101111010001111110001110111111100111001001110111011001110001010100101101000101001011001100011001000001001101111011011110000111010010001001100110111001000010011001101010101000110110000001110101010001101001001110001011011100100011110110100101110010101001011101110000111110000111100000110101110010110111111111001000100010011010001100001110000010101010111101101010100101111101011111100000
標(biāo)準(zhǔn)的CCL長度為19（回憶一下：CCL范圍為0-18，按照整數(shù)大小排序記錄各自的碼字長度）焕盟，因此最后一個補(bǔ)0秋秤。得到序列：
000 101 110 110 000 000 000 010 000 010 000 110 000 101 000 101 000 101 000
其長度分別為（低位在前）：0、5脚翘、3灼卢、3、0来农、0鞋真、0、2沃于、0涩咖、2赶袄、0、3抠藕、0、5蒋困、0盾似、5、0雪标、5零院、0前面已經(jīng)分析過，這個CCL序列實際上是經(jīng)過一次置換操作得到的村刨，需要進(jìn)行相反的置換告抄，置換后為：
3、5嵌牺、5打洼、5、3逆粹、2募疮、2、0僻弹、0阿浓、0、0蹋绽、0芭毙、0、0卸耘、0退敦、0、0鹊奖、5苛聘、3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18這個就是對應(yīng)于0-18的碼字長度序列。根據(jù)Deflate樹的構(gòu)造方式忠聚，得到下面的碼表（Huffman碼表3）：
00 <--> 501 <--> 6100 <--> 0101 <--> 4110 <--> 1811100 <--> 111101 <--> 211110 <--> 311111 <--> 17
接下來就是CL1序列设哗，按照前面的指示，一共有259個两蟀，分別對應(yīng)于literal/length：0-258對應(yīng)的碼字長度序列网梢，我們隊跟著CCL后面的比特按照上面獲得的碼表進(jìn)行逐步解碼，在解碼之前赂毯，實際上并不知道CL1的比特流長度有多少战虏，需要根據(jù)259這個數(shù)字來判定拣宰，解完了259個整數(shù)，表明解析CL1完畢：
101(Header) 01000(HLIT) 01010(HDIST) 0111(HCLEN) 000 101 110 110 000 000 000 010 000 010 000 110 000 101 000 101 000 101 (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碼長序列為：
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 6 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 6 6 5 3 6 0 5 5 0 6 4 5 4 5 0 0 5 4 4 6 6 6 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 5 6
總共259個，每行40個饲鄙。根據(jù)這個序列凄诞，同樣按照Deflate樹構(gòu)造方法，得到literal/length碼表（Huffman碼表1）為：
000 --> (System.Char)（看前面的CL1序列忍级，空格對應(yīng)的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)10010 -->d(System.Char)10011 -->h(System.Char)10100 -->i(System.Char)10101 -->m(System.Char)10110 -->o(System.Char)10111 -->r(System.Char)11000 -->y(System.Char)11001 -->3(System.Int32)（看前面的CL1序列轴咱，對應(yīng)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序列，對應(yīng)256朴肺，碼字長度6）111111 -->4(System.Int32)（看前面的CL1序列窖剑，對應(yīng)258，碼字長度6）
可以看出戈稿，碼表里存在兩個重復(fù)字符串長度3和4西土，當(dāng)解碼結(jié)果為-1（上面進(jìn)行了處理，即256）鞍盗，或者說遇到111110的時候需了，表示Deflate碼流結(jié)束跳昼。
按照同樣的道理，對CL2序列進(jìn)行解析肋乍，前面已經(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序列為：
0 0 0 2 0 0 0 0 1 0 2
分別記錄的是distance碼為0-10的碼字長度，根據(jù)下面的對應(yīng)關(guān)系禽拔，需要進(jìn)行擴(kuò)展
比如刘离，第1個碼長2記錄的是Code=3的長度，即Distance=4對應(yīng)的碼字為：
10 -->4(System.Int32)
第1個碼長1記錄的是Code=8的長度（碼字為0睹栖，擴(kuò)展三位000-111）硫惕，即Distance=17-24對應(yīng)的碼字為（注意，低比特優(yōu)先）：
0 000 -->17(System.Int32)0 100 -->18(System.Int32)0 010 -->19(System.Int32)0 110 -->20(System.Int32)0 001 -->21(System.Int32)0 101 -->22(System.Int32)0 011 -->23(System.Int32)0 111 -->24(System.Int32)
注意野来，擴(kuò)展的時候還是低比特優(yōu)先恼除。
最后1個碼長2記錄的是Code=10的長度（其實是碼字：11，擴(kuò)展四位0000-1111）曼氛，即Distance=33-48對應(yīng)的碼字為：
11 0000 -->33(System.Int32)11 1000 -->34(System.Int32)11 0100 -->35(System.Int32)11 1100 -->36(System.Int32)11 0010 -->37(System.Int32)11 1010 -->38(System.Int32)11 0110 -->39(System.Int32)11 1110 -->40(System.Int32)11 0001 -->41(System.Int32)11 1001 -->42(System.Int32)11 0101 -->43(System.Int32)11 1101 -->44(System.Int32)11 0011 -->45(System.Int32)11 1011 -->46(System.Int32)11 0111 -->47(System.Int32)11 1111 -->48(System.Int32)
至此為止豁辉，Huffman碼表1、Huffman碼表2已經(jīng)還原出來舀患，接下來是對LZ壓縮所得到的literal徽级、distance、length進(jìn)行解碼聊浅，目前剩余的比特流如下餐抢，先按照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）10110（o）111100（v）001（e）110100（,）
[there ]：1000（t）10011（h）001（e）10111（r）001（e）000（空格）
[are ]：0100（a）11001（長度3，表示下一個需要用Huffman解碼）10（Distance=4顽冶，即重復(fù)字符串為re空格）
[many ]：10101（m）0100（a）0110（n）11000（y）000（空格）
[kinds ]：111010（k）10100（i）0110（n）10010（d）0111（s）000（空格）
[of ]：10110（o）111001（f）000（空格）
[wireless ]：111101（w）10100（i）10111（r）001（e）0101（l）001（e）0111（s）0111（s）000（空格）
[systems o]：0111（s）11000（y）0111（s）1000（t）001（e）10101（m）11001（長度指示=3苦蒿，接下來根據(jù)distance解碼）0110（Distance=20,即重復(fù)字符串為s o）
[ther ]：111111（長度指示=4，接下來根據(jù)distance解碼）111001（Distance=42,即重復(fù)字符串為ther）000（空格）
[than ]：1000（t）10011（h）0100（a）0110（n）000（空格）
[cellular.]：111000（c）001（e）0101（l）0101（l）111011（u）0101（l）0100（a）10111（r）110101（.）
[256渗稍，結(jié)束標(biāo)志]111110（結(jié)束標(biāo)志）0000（字節(jié)補(bǔ)齊的0）
于是解壓縮結(jié)果為：
As mentioned above,there are many kinds of wireless systems other than cellular.
再來回顧我們的解碼過程：
譯碼過程：1佩迟、根據(jù)HCLEN得到截尾信息团滥，并參照固定置換表，根據(jù)CCL比特流得到CCL整數(shù)序列报强；2灸姊、根據(jù)CCL整數(shù)序列構(gòu)造出等價于CCL的二級Huffman碼表3；3秉溉、根據(jù)二級Huffman碼表3對CL1力惯、CL2比特流進(jìn)行解碼，得到SQ1整數(shù)序列,SQ2整數(shù)序列召嘶；4父晶、根據(jù)SQ1整數(shù)序列,SQ2整數(shù)序列,利用游程編碼規(guī)則得到等價的CL1整數(shù)序列、CL2整數(shù)序列弄跌；5甲喝、根據(jù)CL1整數(shù)序列、CL2整數(shù)序列分別構(gòu)造兩個一級Huffman碼表：literal/length碼表铛只、distance碼表埠胖；6、根據(jù)兩個一級Huffman碼表對后面的LZ壓縮數(shù)據(jù)進(jìn)行解碼得到literal/length/distance流淳玩；7直撤、根據(jù)literal/length/distance流按照LZ規(guī)則進(jìn)行解碼。
Deflate碼流長度總共為72字節(jié)=576比特蜕着，其中：
3比特Header谋竖；
5比特HLIT；
5比特HDIST承匣；
4比特HCLEN圈盔；
54比特CCL序列碼流；
133比特CL1序列碼流悄雅；
34比特CL2序列碼流驱敲；
338比特LZ壓縮后的literal/length/distance碼流。
11 ZIP的其它說明
上面各個環(huán)節(jié)已經(jīng)詳細(xì)分析了ZIP壓縮的過程以及解碼流程宽闲，通過對一個實例的解壓縮過程分析众眨，可以徹底地掌握ZIP壓縮和解壓縮的原理和過程。還有一些情況需要說明：
（1）上面的算法復(fù)雜度主要在于壓縮一端容诬，因為需要統(tǒng)計literal/length/distance娩梨，創(chuàng)建動態(tài)Huffman碼表，相反解壓只需要還原碼表后览徒，逐比特解析即可狈定，這也是壓縮軟件的一個典型特點，解壓速度遠(yuǎn)快于壓縮速度。
（2）上面我們分析了動態(tài)Huffman纽什，對于LZ壓縮后的literal/length/distance措嵌，也可以采用靜態(tài)Huffman編碼，這主要取決于ZIP在壓縮中看哪種方式更節(jié)省空間芦缰，靜態(tài)Huffman編碼不需要記錄碼表企巢，因為這個碼表是固定的，在RFC1951里面也有說明让蕾。對于literal/length碼表來說浪规，需要對0-285進(jìn)行編碼，其碼表為：
對于Distance來說探孝，需要對Code=0-29的數(shù)進(jìn)行編碼笋婿，則直接采用5比特表示。Distance和動態(tài)Huffman一樣顿颅，在此基礎(chǔ)上進(jìn)行擴(kuò)展缸濒。
（3）ZIP中使用的LZ77算法是一種改進(jìn)的LZ77。主要區(qū)別有兩點：
1）標(biāo)準(zhǔn)LZ77在找到重復(fù)字符串時輸出三元組(length, distance, 下一個未匹配的字符)（有興趣可以關(guān)注LZ77那篇論文）元镀；Deflate在找到重復(fù)字符串時僅輸出雙元組(length, distance)。2）標(biāo)準(zhǔn)LZ77使用”貪婪“的方式解析霎桅，尋找的都是最長匹配字符串栖疑。Deflate中不完全如此。David Salomon的書里給了一個例子：
對于上面這個例子滔驶，標(biāo)準(zhǔn)LZ77在滑動窗口中查找最長匹配字符串遇革，找到的是"the"與前面的there的前三個字符匹配，這種貪婪解析方式邏輯簡單揭糕，但編碼效率不一定最高萝快。Deflate則不急于輸出，跳過t繼續(xù)往后查看著角，發(fā)現(xiàn)"th ne"這5個字符存在重復(fù)字符串揪漩，因此，Deflate算法會選擇將t作為未匹配字符輸出吏口，而對后面的匹配字符串用(length, distance)編碼輸出奄容。顯然，這樣就提高了壓縮效率产徊，因為標(biāo)準(zhǔn)的LZ77找到的重復(fù)字符串長度為3昂勒，而Deflate找到的是5。換句話說舟铜，Deflate算法并不是簡單的尋找最長匹配后輸出戈盈，而是會權(quán)衡幾種可行的編碼方式，用其中最高效的方式輸出谆刨。
12 總結(jié)**
本篇博文對ZIP中使用的壓縮算法進(jìn)行了詳細(xì)分析塘娶，從一個簡單地例子出發(fā)归斤，一步步地分析了PK設(shè)計Deflate算法的思路。最后血柳，通過一個實際例子官册，分析了其解壓縮流程∧寻疲總的來看膝宁，ZIP的核心在于如何對LZ壓縮后的literal、length根吁、distance進(jìn)行Huffman編碼员淫，以及如何以最小空間記錄Huffman碼表。整個過程充滿了對數(shù)據(jù)結(jié)構(gòu)尤其是樹的深入優(yōu)化利用击敌。按照上面的分析介返，如果要對ZIP進(jìn)行進(jìn)一步改進(jìn)，可以考慮的地方也有不少沃斤，典型的有：
（1）擴(kuò)大LZ編碼的滑動窗口的大惺バ；
（2）將Huffman編碼改進(jìn)為算術(shù)編碼等壓縮率更高的方法衡瓶，畢竟徘公，Huffman的碼字長度必須為整數(shù)，這就從理論上限制了它的壓縮率只能接近于理論極限哮针，但難以達(dá)到关面。我記得在JPEG圖像編碼領(lǐng)域，以前的JPEG采用了DCT變換編碼+Huffman的方式十厢，現(xiàn)在JPEG2000將其改為小波變換+算數(shù)編碼等太，所以數(shù)據(jù)壓縮也可以嘗試類似的思路；
（3）將多個文件進(jìn)行合并壓縮蛮放，ZIP中缩抡，不同的文件壓縮過程沒有關(guān)系，獨立進(jìn)行包颁，如果將它們合并起來一起進(jìn)行壓縮缝其，壓縮率可以得到進(jìn)一步提高。
描述分析有誤的地方徘六，敬請指正内边。針對數(shù)據(jù)壓縮相關(guān)的話題，后續(xù)會對HBase列壓縮等等進(jìn)行分析待锈，看看ZIP這種文件壓縮和HBase這種數(shù)據(jù)庫數(shù)據(jù)壓縮的區(qū)別和聯(lián)系漠其。
gzip 、zlib以及圖形格式png，使用的壓縮算法都是deflate算法和屎。從gzip的源碼中拴驮，我們了解到了defalte算法的原理和實現(xiàn)。我閱讀的gzip版本為 gzip-1.2.4柴信。下面我們將要對deflate算法做一個分析和說明套啤。首先簡單介紹一下基本原理，然后詳細(xì)的介紹實現(xiàn)随常。
