ZIP壓縮的原理

接著上一篇，我們學會了用vs2013將zlib.h頭文件載入了vs2013，我們可以調用壓縮和解壓函數來實現這些操作，今天我們來一起學習下zip壓縮的原理。

zip壓縮的原理分為以下步驟：

1，將數據進行LZ壓縮：我們以一個非常金典的例子來說明：生，容易。活，容易。生活，不容易。所謂LZ壓縮就是當掃描到了某一個數據是，回過頭來看前面掃描的數據中有沒有出現這個數據，如果出現了就用這個數據與前面出現的數據的距離distance和重復的字符數長度lenght來表示，而沒有重復的數據用literal表示，下圖給出的例子就非常清晰：

更具上圖，滑動窗口的大小決定著壓縮的程度，越大壓縮的越嚴重，但是滑動窗口的大小越大，壓縮的速度也就越慢，在速度和壓縮程度上我們合理分配權重，最后取32KB是最合適的。

2，下面就到了Zlib壓縮的核心，主要是對 distance，lenght/literal進行再壓縮，這里先講對 distance的操作。

假如對一個文件進行LZ壓縮后，得到的distance值為：

3、6、4、3、4、3、4、3、5

這個例子里，3出現了4次，4出現了3次，5出現了1次，6出現了1次。當然，不同的文件得到的結果不同，這里只是舉一個典型的例子，因為只有4種值，所以我們沒有必要對其它整數編碼。只需要對這4個整數進行編碼即可。而編碼的規則是小的值就用較少比特表示，大的值就用較多比特表示。我們不妨用固定2個字節表示：

00-->3； 01-->4； 10-->5;? 11-->6

00、01這種編碼結果稱為碼字，碼字的平均長度是2。上面這個對應關系即為碼表，在壓縮時，需要將碼表放在最前面，后面的數字就用碼字表示，解碼時，先把碼表記錄在內存里，比如用一個哈希表記錄下來，解壓縮時，遇到00，就解碼為3等等。

但是，前面說了編碼的規則是小的值就用較少比特表示，大的值就用較多比特表示，所以這里用如下的方法表示為：

0-->3；10-->4；110-->5；111-->6

這樣的編碼思想和Huffman編碼的方法非常相似，同時需要注意的一個原則是一個碼字不能是另一個碼字的前綴！

上面的結果可以用一顆二叉樹表示為下圖：

理解了Huffman編碼的思想，我們來看看distance的實際情況。ZIP中滑動窗口大小固定為32KB，也就是說，distance的值范圍是1-32768。那么，通過上面的方式，統計頻率后，就得到32768個碼字，按照上面這種方式可以構建出來。于是我們會遇到一個最大的問題，那就是這棵樹太大了，怎么記錄呢？

ZIP中Huffman碼樹的記錄方式：

在這里zlib用一個非常巧妙的辦法，它規定了Huffman碼樹的格式，都為如上圖所示的。那么就只需要記錄碼字長度即可，上面的碼表可以用下面的方式來記錄：

3　　4　　5　　6

1　　2　　3　　3

我們知道每個distance肯定對應唯一一個碼字，使用Huffman編碼可以得到所有碼字，但是因為distance可能非常多，雖然一般不會有32768這么多，但對一個大些的文件進行LZ編碼，distance上千還是很正常的，所以這棵樹很大。實際上，考慮壓縮效率的原因，我們把 distance劃分成30個區間如下圖

那么也許有人會問，當distance為19怎么辦？在回答這個問題之前我先介紹一下上面的表的結構：

其中，左邊的Code表示區間的編號，是0-29，共30個區間，這只是個編號，沒有特別的含義，但Huffman就是對0-29這30個Code進行編碼的，得到區間的碼字；

bits表示distance的碼字需要在Code的碼字基礎上擴展幾位，比如0就表示不擴展，最大的13表示要擴展13位，因此，最大的區間包含的distance數量為8192個。

Distance一列則表示這個區間涵蓋的distance范圍。

解決辦法是這樣的：distance為19在17-24這個區間，比如，17-24這個區間的Huffman碼字是110，因為17-24這個區間有8個整數，于是按照下面的規則即可獲得其distance對應的碼字：

17-->110 000

18-->110 001

19-->110 010

20-->110 011

21-->110 100

22-->110 101

23-->110 110

24-->110 111

所以可以非常明確的知道19對應的數值是 110 010。

3，ZIP中literal和length的壓縮方式

literal和length也是類似于distance的方式進行壓縮。

literal表示未匹配的字符，它實際上是針對字節作為基本字符來編碼的，所以一個literal至多有256種可能。而length表示重復字符串長度，length=1當然不會出現，因為一個字符不值得用distance+length去記錄，重復字符串當然越長越好，zlib中把length最小值認為是3，必須3個以上字符的字符串出現重復才用distance+length記錄。同時把length的范圍做了限制，限定length的個數跟literal一樣，也只有256個。

literal用整數0-255表示，256是一個結束標志，解碼以后結果是256表示解碼結束；從257開始表示length，所以257這個數表示length=3，258這個數表示length=4等等，但zlib也不是一直這么一一對應，和distance一樣，也是把length（總共256個值）劃分為29個區間，其結果如下圖：

Huffman碼樹用一個碼字長度序列表示，稱為CL（Code Length），記錄兩個碼表的碼字長度序列分別記為CL1、CL2。碼樹記錄下來，對literal/length的編碼比特流稱為LIT比特流；對distance的編碼比特流稱為DIST比特流。按照上面的方法，LZ的編碼結果就變成四塊：CL1、CL2、LIT比特流、DIST比特流。CL1、CL2是碼字長度的序列，這個序列說白了就是一堆正整數，因此，zlib繼續深挖，認為這個序列還應該繼續壓縮，也就是說，對碼表進行壓縮

4,ZIP中對CL進行再次壓縮的方法

這里仍然沿用Huffman的想法，因為CL也是一堆整數，那么當然可以再次應用Huffman編碼。不過在這之前，zlib對CL序列進行了一點處理。這個處理也是很精巧的。

這個處理叫游程處理。

什么叫游程呢？就是一段完全相同的數的序列。什么叫游程編碼呢？說起來原理更簡單，就是對一段連續相同的數，記錄這個數一次，緊接著記錄出現了多少個即可。為什么在這里引入游程處理了，是因為CL序列表示一系列整數對應的碼字長度，對于literal/length來說，總共有0-285這么多符號，所以這個序列長度為286，每個符號都有一個碼字長度，當然，這里面可能會出現大段連續的0，因為某些字符或長度不存在，尤其是對英文文本編碼的時候，非ASCII字符就根本不會出現，length較大的值出現概率也很小，所以出現大段的0是很正常的；對于distance也類似，也可能出現大段的0。

下面通過一個例子來具體解說。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
那么，游程編碼的結果為：

4, 16, 01（二進制）, 3, 3, 3, 6, 16, 11（二進制）, 16, 00（二進制）, 17,011（二進制）, 2, 16, 00（二進制）
這是什么意思呢？因為CL的范圍是0-15，PK認為重復出現2次太短就不用游程編碼了，所以游程長度從3開始。用16這個特殊的數表示重復出現3、4、5、6個這樣一個游程，分別后面跟著00、01、10、11表示（實際存儲的時候需要低比特優先存儲，需要把比特倒序來存，博文的一些例子有時候會忽略這點，實際寫程序的時候一定要注意，否則會得到錯誤結果）。于是4,4,4,4,4,這段游程記錄為4,16,01，也就是說，4這個數，后面還會連續出現了4次。6,16,11,16,00表示6后面還連續跟著6個6，再跟著3個6；因為連續的0出現的可能很多，所以用17、18這兩個特殊的數專門表示0游程，17后面跟著3個比特分別記錄長度為3-10（總共8種可能）的游程；18后面跟著7個比特表示11-138（總共128種可能）的游程。17,011（二進制）表示連續出現6個0；18,0111110（二進制）表示連續出現62個0。總之記住，0-15是CL可能出現的值，16表示除了0以外的其它游程；17、18表示0游程。因為二進制實際上也是個整數，所以上面的序列用整數表示為：

4, 16, 1, 3, 3, 3, 6, 16, 3, 16, 0, 17, 3, 2, 16, 0

我們又看到了一串整數，這串整數的值的范圍是0-18。這個序列稱為SQ（Sequence的意思）。因為有兩個CL1、CL2，所以對應的有兩個SQ1、SQ2。

針對SQ1、SQ2，PK用了第三個Huffman碼表來對這兩個序列進行編碼。通過統計各個整數（0-18范圍內）的出現次數，按照相同的思路，對SQ1和SQ2進行了Huffman編碼，得到的碼流記為SQ1 bits和SQ2 bits。同時，這里又需要記錄第三個碼表，稱為Huffman碼表3。同理，這個碼表也用相同的方法記錄，也等效為一個碼長序列，稱為CCL，因為至多有0-18個，zlib認為樹的深度至多為7，于是CCL的范圍是0-7。

就在大家都認為結束了的時候，zlib進行了置換CCL序列的操作。zlib認為CL序列里面CL范圍為0-15，特殊的幾個值是16、17、18，如果把CCL序列位置置換一下，把16、17、18這些放前面，那么這個CCL序列就很可能最后面跟著一串0（因為CL=14,15這些很可能沒有），所以最后還引入了一個置換，其示意圖如下，分別表示置換前的CCL序列和置換后的CCL。

到此為止，ZIP壓縮算法的結果已經完畢。這個算法命名為Deflate算法。總結一下其編碼流程為：這個圖是精髓

總結

以上是生活随笔為你收集整理的ZIP压缩的原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。