簡述
壓縮可以分為無損壓縮和有損壓縮，有損，指的是壓縮之後就無法完整還原原始信息，但是壓縮率可以很高，主要應用於視頻、話音等數據的壓縮，因為損失了一點信息，人是很難察覺的，或者說，也沒必要那麼清晰照樣可以看可以聽；無損壓縮則用於文件等等必須完整還原信息的場合，ZIP自然就是一種無損壓縮，在通信原理中介紹數據壓縮的時候，往往是從信息論的角度出發，引出香農所定義的熵的概念，這方面的介紹實在太多，這裡換一種思路，從最原始的思想出發，為了達到壓縮的目的，需要怎麼去設計算法。而ZIP為我們提供了相當好的案例。
原理
有兩種形式的重複存在於計算機數據中，zip 就是對這兩種重複進行了壓縮。
一種是短語形式的重複短語形式的重複，即三個字節以上的重複，對於這種重複，zip用兩個數字：1.重複位置距當前壓縮位置的距離；2.重複的長度，來表示這個重複，假設這兩個數字各佔一個字節，於是數據便得到了壓縮。
第二種重複為單字節的重複，一個字節只有256種可能的取值，所以這種重複是必然的。其中，某些字節出現次數可能較多，另一些則較少，在統計上有分佈不均勻的傾向，這是容易理解的，比如一個 ASCII 文本文件中，某些符號可能很少用到，而字母和數字則使用較多，各字母的使用頻率也是不一樣的，據說字母 e 的使用概率最高；許多圖片呈現深色調或淺色調，深色（或淺色）的像素使用較多（這裡順便提一下：png 圖片格式是一種無損壓縮，其核心算法就是 zip 算法，它和 zip 格式的文件的主要區別在於：作為一種圖片格式，它在文件頭處存放了圖片的大小、使用的顏色數等信息）；上面提到的短語式壓縮的結果也有這種傾向：重複傾向於出現在離當前壓縮位置較近的地方，重複長度傾向於比較短（20字節以內）。這樣，就有了壓縮的可能：給 256 種字節取值重新編碼，使出現較多的字節使用較短的編碼，出現較少的字節使用較長的編碼，這樣一來，變短的字節相對於變長的字節更多，文件的總長度就會減少，並且，字節使用比例越不均勻，壓縮比例就越大。
實例
- ZIP中對CL進行再次壓縮的方法
CL序列表示一系列整數對應的碼字長度，對於literal/length來說，總共有0-285這麼多符號，所以這個序列長度為286，每個符號都有一個碼字長度，當然，這裡面可能會出現大段連續的0，因為某些字符或長度不存在，尤其是對英文文本編碼的時候，非ASCII字符就根本不會出現，length較大的值出現概率也很小，所以出現大段的0是很正常的；對於distance也類似，也可能出現大段的0。PK於是先進行了一下游程編碼。在說什麼是遊程編碼之前，我們談談PK對CL序列的認識。
literal/length的編碼符號總共286個，distance的編碼符號總共30個，所以這顆碼樹不會特別深，Huffman編碼後的碼字長度不會特別長，PK認為最長不會超過15，也就是樹的深度不會超過15，這個是否是理論證明我還沒有分析，有興趣的同學可以分析一下。因此，CL1和CL2這兩個序列的任意整數值的範圍是0-15。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的遊程；18後面跟著7個比特表示11-138的遊程。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。因為有兩個CL1、CL2，所以對應的有兩個SQ1、SQ2。
針對SQ1、SQ2，PK用了第三個Huffman碼錶來對這兩個序列進行編碼。通過統計各個整數的出現次數，按照相同的思路，對SQ1和SQ2進行了Huffman編碼，得到的碼流記為SQ1 bits和SQ2 bits。同時，這裡又需要記錄第三個碼錶，稱為Huffman碼錶3。同理，這個碼錶也用相同的方法記錄，也等效為一個碼長序列，稱為CCL，因為至多有0-18個，PK認為樹的深度至多為7，於是CCL的範圍是0-7。
當得到了CCL序列後，PK決定不再折騰，對這個序列用普通的3比特定長編碼記錄下來即可，即000代表0,111代表7。但實際上還有一點小折騰，就是最後這個序列如果全部記錄，那就需要19*3=57個比特，PK認為CL序列裡面CL範圍為0-15，特殊的幾個值是16、17、18，如果把CCL序列位置置換一下，把16、17、18這些放前面，那麼這個CCL序列就很可能最後面跟著一串0，所以最後還引入了一個置換，其示意圖如下，分別表示置換前的CCL序列和置換後的CCL。可以看出，16、17、18對應的CCL被放到了前面，這樣如果尾部出現了一些0，就只需要記錄CCL長度即可，後面的0不記錄。可以繼續節省一些比特，不過這個例子尾部置換後只有1個0：
不過粗看起來，這個置換效果並不好，我一開始接觸這個置換的時候，我覺得應該按照16、17、18、0、1、2、3、。。。這樣的順序來存儲，如果按照我理解的，那麼置換後的結果如下：
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和中間的值出現得比較多，但CL比較小的和比較大的出現得比較少，在文件比較小的時候，這種方法效果不算好，上面就是一個典型的例子，但文件比較大了以後，CL1、CL2碼樹比較大，碼字長度普遍比較長，大部分很可能接近於中間值，那麼這個時候PK的方法可能就體現出優勢了。不得不說，對一個算法或者數據結構的優化程度，簡直完全取決於程序員對那個東西細節的理解的深度。
閱讀更多 咱小二 的文章
