半 年前，苦熬過初學(xué) vc 時(shí)那段艱難的學(xué)習(xí)曲線的我，對(duì) MFC、SDK 開始失望和不滿，這些雖然不算易學(xué)，但和 DHTML 沒有實(shí)質(zhì)上的區(qū)別，都是調(diào)用微軟提供的各種各樣的函數(shù)，不需要你自己去創(chuàng)建一個(gè)窗口，多線程編程時(shí)，也不需要你自己去分配 CPU 時(shí)間。我也做過驅(qū)動(dòng)，同樣，有DDK（微軟驅(qū)動(dòng)開發(fā)包），當(dāng)然，也有 DDK 的“參考手冊(cè)”，連一個(gè)最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)都不需要你自己做，一切都是函數(shù)、函數(shù)……
微軟的高級(jí)程序員編寫了函數(shù)讓我們這些搞應(yīng)用的去調(diào)用，我不想在這里貶低搞應(yīng)用的人，正是這些應(yīng)用工程師連接起了科學(xué)和社會(huì)之間的橋梁，將來(lái)可以做銷售，做管理，用自己逐漸積累起來(lái)的智慧和經(jīng)驗(yàn)在社會(huì)上打拼。
但 是，在技術(shù)上來(lái)說，誠(chéng)實(shí)地說，這并不高深，不是嗎？第一流的公司如微軟、Sybase、Oracle 等總是面向社會(huì)大眾的，這樣才能有巨大的市場(chǎng)。但是他們往往也是站在社會(huì)的最頂層的：操作系統(tǒng)、編譯器、數(shù)據(jù)庫(kù)都值得一代代的專家去不斷研究。這些帝國(guó)般 的企業(yè)之所以偉大，恐怕不是“有經(jīng)驗(yàn)”、“能吃苦”這些中國(guó)特色的概念所能涵蓋的，艱深的技術(shù)體系、現(xiàn)代的管理哲學(xué)、強(qiáng)大的市場(chǎng)能力都是缺一不可的吧。我 們既然有志于技術(shù)，并且正在起步階段，何必急不可耐地要轉(zhuǎn)去做“管理”，做“青年才俊”，那些所謂的“成功人士”的根底能有幾何，這樣子浮躁，胸中的規(guī)模 和格局能有多大？

在我發(fā)現(xiàn)vc只是一個(gè)用途廣泛的編程工具，并不能代表“知識(shí)”、“技術(shù)”的時(shí)候，我有些失落，無(wú)所不能的不是我，而是 MFC、SDK、DDK，是微軟的工程師，他們做的，正是我想做的，或者說，我也想成為那種層次的人，現(xiàn)在我知道了，他們是專家，但這不會(huì)是一個(gè)夢(mèng)，有一 天我會(huì)做到的，為什么不能說出我的想法呢。
那時(shí)公司做的系統(tǒng)里有一個(gè)壓縮模塊，領(lǐng)導(dǎo)找了一個(gè) zlib 庫(kù)，不讓我自己做壓縮算法，站在公司的立場(chǎng)上，我很理解，真的很理解，自己做算法要多久啊。但那時(shí)自己心中隱藏的一份倔強(qiáng)驅(qū)使我去尋找壓縮原理的資料，我 完全沒有意識(shí)到，我即將打開一扇大門，進(jìn)入一個(gè)神奇的“數(shù)據(jù)結(jié)構(gòu)”的世界。“計(jì)算機(jī)藝術(shù)”的第一線陽(yáng)光，居然也照到了我這樣一個(gè)平凡的人的身上。

上面說到“計(jì)算機(jī)藝術(shù)”，或者進(jìn)一步細(xì)化說“計(jì)算機(jī)編程藝術(shù)”，聽起來(lái)很深?yuàn)W，很高雅，但是在將要進(jìn)入專業(yè)的壓縮算法的研究時(shí)，我要請(qǐng)大家做的第一 件事情是：忘掉自己的年齡、學(xué)歷，忘掉自己的社會(huì)身份，忘掉編程語(yǔ)言，忘掉“面向?qū)ο蟆薄ⅰ叭龑蛹軜?gòu)”等一切術(shù)語(yǔ)。把自己當(dāng)作一個(gè)小孩，有一雙求知的眼 睛，對(duì)世界充滿不倦的、單純的好奇，唯一的前提是一個(gè)正常的具有人類理性思維能力的大腦。
下面就讓我們開始一段神奇的壓縮算法之旅吧：


1. 原理部分：
　　有兩種形式的重復(fù)存在于計(jì)算機(jī)數(shù)據(jù)中，zip 就是對(duì)這兩種重復(fù)進(jìn)行了壓縮。
　　一種是短語(yǔ)形式的重復(fù)，即三個(gè)字節(jié)以上的重復(fù)，對(duì)于這種重復(fù)，zip用兩個(gè)數(shù)字：1.重復(fù)位置距當(dāng)前壓縮位置的距離；2.重復(fù)的長(zhǎng)度，來(lái)表示這個(gè)重復(fù)，假設(shè)這兩個(gè)數(shù)字各占一個(gè)字節(jié)，于是數(shù)據(jù)便得到了壓縮，這很容易理解。
　 　一個(gè)字節(jié)有 0 - 255 共 256 種可能的取值，三個(gè)字節(jié)有 256 * 256 * 256 共一千六百多萬(wàn)種可能的情況，更長(zhǎng)的短語(yǔ)取值的可能情況以指數(shù)方式增長(zhǎng)，出現(xiàn)重復(fù)的概率似乎極低，實(shí)則不然，各種類型的數(shù)據(jù)都有出現(xiàn)重復(fù)的傾向，一篇論文 中，為數(shù)不多的術(shù)語(yǔ)傾向于重復(fù)出現(xiàn)；一篇小說，人名和地名會(huì)重復(fù)出現(xiàn)；一張上下漸變的背景圖片，水平方向上的像素會(huì)重復(fù)出現(xiàn)；程序的源文件中，語(yǔ)法關(guān)鍵字 會(huì)重復(fù)出現(xiàn)（我們寫程序時(shí)，多少次前后copy、paste？），以幾十 K 為單位的非壓縮格式的數(shù)據(jù)中，傾向于大量出現(xiàn)短語(yǔ)式的重復(fù)。經(jīng)過上面提到的方式進(jìn)行壓縮后，短語(yǔ)式重復(fù)的傾向被完全破壞，所以在壓縮的結(jié)果上進(jìn)行第二次短 語(yǔ)式壓縮一般是沒有效果的。
　　第二種重復(fù)為單字節(jié)的重復(fù)，一個(gè)字節(jié)只有256種可能的取值，所以這種重復(fù)是必然的。其中，某些字節(jié)出現(xiàn)次數(shù)可能 較多，另一些則較少，在統(tǒng)計(jì)上有分布不均勻的傾向，這是容易理解的，比如一個(gè) ASCII 文本文件中，某些符號(hào)可能很少用到，而字母和數(shù)字則使用較多，各字母的使用頻率也是不一樣的，據(jù)說字母 e 的使用概率最高；許多圖片呈現(xiàn)深色調(diào)或淺色調(diào)，深色（或淺色）的像素使用較多（這里順便提一下：png 圖片格式是一種無(wú)損壓縮，其核心算法就是 zip 算法，它和 zip 格式的文件的主要區(qū)別在于：作為一種圖片格式，它在文件頭處存放了圖片的大小、使用的顏色數(shù)等信息）；上面提到的短語(yǔ)式壓縮的結(jié)果也有這種傾向：重復(fù)傾向 于出現(xiàn)在離當(dāng)前壓縮位置較近的地方，重復(fù)長(zhǎng)度傾向于比較短（20字節(jié)以內(nèi)）。這樣，就有了壓縮的可能：給 256 種字節(jié)取值重新編碼，使出現(xiàn)較多的字節(jié)使用較短的編碼，出現(xiàn)較少的字節(jié)使用較長(zhǎng)的編碼，這樣一來(lái)，變短的字節(jié)相對(duì)于變長(zhǎng)的字節(jié)更多，文件的總長(zhǎng)度就會(huì)減 少，并且，字節(jié)使用比例越不均勻，壓縮比例就越大。
　　在進(jìn)一步討論編碼的要求以及辦法前，先提一下：編碼式壓縮必須在短語(yǔ)式壓縮之后進(jìn)行，因?yàn)? 編碼式壓縮后，原先八位二進(jìn)制值的字節(jié)就被破壞了，這樣文件中短語(yǔ)式重復(fù)的傾向也會(huì)被破壞（除非先進(jìn)行解碼）。另外，短語(yǔ)式壓縮后的結(jié)果：那些剩下的未被 匹配的單、雙字節(jié)和得到匹配的距離、長(zhǎng)度值仍然具有取值分布不均勻性，因此，兩種壓縮方式的順序不能變。
　　在編碼式壓縮后，以連續(xù)的八位作為一 個(gè)字節(jié)，原先未壓縮文件中所具有的字節(jié)取值不均勻的傾向被徹底破壞，成為隨機(jī)性取值，根據(jù)統(tǒng)計(jì)學(xué)知識(shí)，隨機(jī)性取值具有均勻性的傾向（比如拋硬幣試驗(yàn)，拋一 千次，正反面朝上的次數(shù)都接近于 500 次）。因此，編碼式壓縮后的結(jié)果無(wú)法再進(jìn)行編碼式壓縮。
　　短語(yǔ)式壓縮和編碼式壓縮是目前計(jì)算機(jī)科學(xué)界研究出的僅有的兩種無(wú)損壓縮方法，它們都無(wú)法重復(fù)進(jìn)行，所以，壓縮文件無(wú)法再次壓縮（實(shí)際上，能反復(fù)進(jìn)行的壓縮算法是不可想象的，因?yàn)樽罱K會(huì)壓縮到 0 字節(jié)）。
=====================================

（補(bǔ)充）

壓縮文件無(wú)法再次壓縮是因?yàn)椋?br />1. 短語(yǔ)式壓縮去掉了三個(gè)字節(jié)以上的重復(fù)，壓縮后的結(jié)果中包含的是未匹配的單雙字節(jié)，和匹配距離、長(zhǎng)度的組合。這個(gè)結(jié)果當(dāng)然仍然可能包含三個(gè)字節(jié)以上的重復(fù)， 但是概率極低。因?yàn)槿齻€(gè)字節(jié)有 256 * 256 * 256 共一千六百多萬(wàn)種可能的情況，一千六百萬(wàn)分之一的概率導(dǎo)致匹配的距離很長(zhǎng)，需要二進(jìn)制數(shù)24位來(lái)表示這個(gè)匹配距離，再加上匹配長(zhǎng)度就超過了三個(gè)字節(jié)，得不 償失。所以只能壓縮掉原始文件中“自然存在的，并非隨機(jī)的短語(yǔ)式重復(fù)傾向”。
2.編碼式壓縮利用各個(gè)單字節(jié)使用頻率不一樣的傾向，使定長(zhǎng)編碼變?yōu)? 不定長(zhǎng)編碼，給使用頻率高的字節(jié)更短的編碼，使用頻率低的字節(jié)更長(zhǎng)的編碼，起到壓縮的效果。如果把編碼式壓縮的“結(jié)果”按照8位作為1字節(jié)，重新統(tǒng)計(jì)各字 節(jié)的使用頻率，應(yīng)該是大致相等的。因?yàn)樾碌淖止?jié)使用頻率是隨機(jī)的。相等的頻率再去變換字節(jié)長(zhǎng)短是沒有意義的，因?yàn)樽兌痰淖止?jié)沒有比變長(zhǎng)的字節(jié)更多。

=======================================

　　短語(yǔ)式重復(fù)的傾向和字節(jié)取值分布不均勻的傾向是可以壓縮的基礎(chǔ)，兩種壓縮的順序不能互換的原因也說了，下面我們來(lái)看編碼式壓縮的要求及方法：

首先，為了使用不定長(zhǎng)的編碼表示單個(gè)字符，編碼必須符合“前綴編碼”的要求，即較短的編碼決不能是較長(zhǎng)編碼的前綴，反過來(lái)說就是，任何一個(gè)字符的編碼，都不是由另一個(gè)字符的編碼加上若干位 0 或 1 組成，否則解壓縮程序?qū)o(wú)法解碼。
看一下前綴編碼的一個(gè)最簡(jiǎn)單的例子：


符號(hào) 編碼
A 0
B 10
C 110
D 1110
E 11110

有了上面的碼表，你一定可以輕松地從下面這串二進(jìn)制流中分辨出真正的信息內(nèi)容了：

1110010101110110111100010 - DABBDCEAAB

要構(gòu)造符合這一要求的二進(jìn)制編碼體系，二叉樹是最理想的選擇。考察下面這棵二叉樹：

　　　　　　　　根(root)
　　　　　　 0　　|　　 1
　　　　 　 +-------+--------+
　　　　0　 |　1　　 0 　|　 1
　 　 +-----+------+　　+----+----+
　 　 |　　　　　|　|　 　　 |
　 　 a　　 　　 |　d 　　　 e
　　　　　0　　|　　1
　　　　　+-----+-----+
　　　　　|　　　　 |
　　　　　b　　 　　c

要編碼的字符總是出現(xiàn)在樹葉上，假定從根向樹葉行走的過程中，左轉(zhuǎn)為0，右轉(zhuǎn)為1，則一個(gè)字符的編碼就是從根走到該字符所在樹葉的路徑。正因?yàn)樽址荒艹霈F(xiàn)在樹葉上，任何一個(gè)字符的路徑都不會(huì)是另一字符路徑的前綴路徑，符合要求的前綴編碼也就構(gòu)造成功了：

a - 00 b - 010 c - 011 d - 10 e - 11


接下來(lái)來(lái)看編碼式壓縮的過程：
為了簡(jiǎn)化問題，假定一個(gè)文件中只出現(xiàn)了 a，b，c，d ，e五種字符，它們的出現(xiàn)次數(shù)分別是
a : 6次
b : 15次
c : 2次
d : 9次
e : 1次
如果用定長(zhǎng)的編碼方式為這四種字符編碼： a : 000 b : 001 c : 010 d : 011 e : 100
那么整個(gè)文件的長(zhǎng)度是 3*6 + 3*15 + 3*2 + 3*9 + 3*1 = 99

用二叉樹表示這四種編碼(其中葉子節(jié)點(diǎn)上的數(shù)字是其使用次數(shù)，非葉子節(jié)點(diǎn)上的數(shù)字是其左右孩子使用次數(shù)之和):

　　　　　　　　 　根
　　　　　　　　 　 |
　　　　　　+---------33---------+
　　　　　　|　　　　　　 　|
　　 +----32---+　　　　　 +----1---+
　　 |　　　　|　 　　　|　　　 |
+-21-+ 　　 +-11-+ 　 　+--1--+　　
|　　 | 　 |　　 | 　 　|　　 |
6　 　15 　2　　9 　 　1　　　

（如果某個(gè)節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，可以去掉這個(gè)子節(jié)點(diǎn)。）

　　　　　　　　 根
　　　　　　　　　|
　 　 　　　 +------33------+
　　　　　　 |　　　　　|
　 　 +-----32----+ 　 　 1
　 　 |　　　 　 |
　 +--21--+ 　+--11--+
　 |　　　|　 |　　　|
　 6 　　15　2　 　 9

現(xiàn)在的編碼是： a : 000 b : 001 c : 010 d : 011 e : 1 仍然符合“前綴編碼”的要求。

第一步：如果發(fā)現(xiàn)下層節(jié)點(diǎn)的數(shù)字大于上層節(jié)點(diǎn)的數(shù)字，就交換它們的位置，并重新計(jì)算非葉子節(jié)點(diǎn)的值。
先交換11和1，由于11個(gè)字節(jié)縮短了一位，1個(gè)字節(jié)增長(zhǎng)了一位，總文件縮短了10位。

　　　　　　　　　　 根
　 　 　　　　　　　　|
　　　　　　 +----------33---------+
　　　　　　 |　　　　　　　　|
　　 +-----22----+　　　　　+----11----+
　　 | 　　 　|　　　　　|　　　　 |
+--21--+　　　 1　 　 　　2　　　　 9
| 　 　 |
6　　 15

再交換15和1、6和2，最終得到這樣的樹：

　　　　　　　　　　 根
　　　　　 　　　　 　|
　　　　　　 +----------33---------+
　　　　　　 |　　　　　　　　|
　　 　 +-----18----+　　　 +----15----+
　　　 | 　　 　　|　　　 |　　　　 |
　　+--3--+ 　 　15　　　6　　　　 9
　　|　 　|
　　2　　 1

這時(shí)所有上層節(jié)點(diǎn)的數(shù)值都大于下層節(jié)點(diǎn)的數(shù)值，似乎無(wú)法再進(jìn)一步壓縮了。但是我們把每一層的最小的兩個(gè)節(jié)點(diǎn)結(jié)合起來(lái)，常會(huì)發(fā)現(xiàn)仍有壓縮余地。

第二步：把每一層的最小的兩個(gè)節(jié)點(diǎn)結(jié)合起來(lái)，重新計(jì)算相關(guān)節(jié)點(diǎn)的值。

在上面的樹中，第一、二、四三層都只有一或二個(gè)節(jié)點(diǎn)，無(wú)法重新組合，但第三層上有四個(gè)節(jié)點(diǎn)，我們把最小的3和6結(jié)合起來(lái)，并重新計(jì)算相關(guān)節(jié)點(diǎn)的值，成為下面這棵樹。

　　　　　　　　　　 根
　　　　　 　　　　 　|
　　　　　　 +----------33---------+
　　　　　　 | 　　　　　　　 |
　　　 +------9-----+　　　 +----24----+
　　　 |　 　　 　|　　　 |　　　　 |
　　 +--3--+　 　 6　　　15　　　　9
　　 |　　 |
　　2　　1

然后，再重復(fù)做第一步。
這時(shí)第二層的9小于第三層的15，于是可以互換，有9個(gè)字節(jié)增長(zhǎng)了一位，15個(gè)字節(jié)縮短了一位，文件總長(zhǎng)度又縮短了6位。然后重新計(jì)算相關(guān)節(jié)點(diǎn)的值。

　　　　　　　　　　 根
　　　　 　　　　　　 |
　　　　　　 +----------33---------+
　　　　　　 |　　　　　　　　|
　　　　　　 15　　　　 +----18----+　
　　　　　　　　　　　　|　　　　|
　　　　　　　　　+------9-----+　　 9
　　　　　　　　　|　 　　　 |
　 　　　　　 　+--3--+　　　6
　　 　　　　 　|　　 |
　　　　 　　　 2　　1

這時(shí)發(fā)現(xiàn)所有的上層節(jié)點(diǎn)都大于下層節(jié)點(diǎn)，每一層上最小的兩個(gè)節(jié)點(diǎn)被并在了一起，也不可能再產(chǎn)生比同層其他節(jié)點(diǎn)更小的父節(jié)點(diǎn)了。

這時(shí)整個(gè)文件的長(zhǎng)度是 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63

這時(shí)可以看出編碼式壓縮的一個(gè)基本前提：各節(jié)點(diǎn)之間的值要相差比較懸殊，以使某兩個(gè)節(jié)點(diǎn)的和小于同層或下層的另一個(gè)節(jié)點(diǎn)，這樣，交換節(jié)點(diǎn)才有利益。
所以歸根結(jié)底，原始文件中的字節(jié)使用頻率必須相差較大，否則將沒有兩個(gè)節(jié)點(diǎn)的頻率之和小于同層或下層其他節(jié)點(diǎn)的頻率，也就無(wú)法壓縮。反之，相差得越懸殊，兩個(gè)節(jié)點(diǎn)的頻率之和比同層或下層節(jié)點(diǎn)的頻率小得越多，交換節(jié)點(diǎn)之后的利益也越大。

在這個(gè)例子中，經(jīng)過上面兩步不斷重復(fù)，得到了最優(yōu)的二叉樹，但不能保證在所有情況下，都能通過這兩步的重復(fù)得到最優(yōu)二叉樹，下面來(lái)看另一個(gè)例子：

　　　　　　　　　　　　　　　　　　　　　　　　　根
　　　　　　　　　　　　　　　　　　　　　　　　　｜
　　　　　　　　　　　　　　＋－－－－－－－－－１９－－－－－－－－＋
　　　　　　　　　　　　　　｜　　　　　　　　　　　　　　　　　　　｜
　　　　　　＋－－－－－－１２－－－－－－＋　　　　　　　　　　　　７
　　　　　　｜　　　　　　　　　　　　　　｜
　　＋－－－５－－－＋　　　　　　＋－－－７－－－＋
　　｜　　　　　　　｜　　　　　　｜　　　　　　　｜
＋－２－＋　　　＋－３－＋　　＋－３－＋　　　＋－４－＋
｜　　　｜　　　｜　　　｜　　｜　　　｜　　　｜　　　｜
１　　　１　　　１　　　２　　１　　　２　　　２　　　２

這個(gè)例子中，所有上層節(jié)點(diǎn)都大于等于下層節(jié)點(diǎn)，每一層最小的兩個(gè)節(jié)點(diǎn)結(jié)合在了一起，但仍然可以進(jìn)一步優(yōu)化：


　　　　　　　　　　　　　　　　　　　　　　　　　根
　　　　　　　　　　　　　　　　　　　　　　　　　｜
　　　　　　　　　　　　　　＋－－－－－－－－－１９－－－－－－－－＋
　　　　　　　　　　　　　　｜　　　　　　　　　　　　　　　　　　　｜
　　　　　　＋－－－－－－１２－－－－－－＋　　　　　　　　　　　　７
　　　　　　｜　　　　　　　　　　　　　　｜
　　＋－－－４－－－＋　　　　　　＋－－－８－－－＋
　　｜　　　　　　　｜　　　　　　｜　　　　　　　｜
＋－２－＋　　　＋－２－＋　　＋－４－＋　　　＋－４－＋
｜　　　｜　　　｜　　　｜　　｜　　　｜　　　｜　　　｜
１　　　１　　　１　　　１　　２　　　２　　　２　　　２

通過最低一層的第４第５個(gè)節(jié)點(diǎn)對(duì)換，第３層的８大于第２層的７。
到這里，我們得出這樣一個(gè)結(jié)論：一棵最優(yōu)二叉編碼樹（所有上層節(jié)點(diǎn)都無(wú)法和下層節(jié)點(diǎn)交換），必須符合這樣兩個(gè)條件：
１．所有上層節(jié)點(diǎn)都大于等于下層節(jié)點(diǎn)。
２．某節(jié)點(diǎn)，設(shè)其較大的子節(jié)點(diǎn)為ｍ，較小的子節(jié)點(diǎn)為ｎ，ｍ下的任一層的所有節(jié)點(diǎn)都應(yīng)大于等于ｎ下的該層的所有節(jié)點(diǎn)。

當(dāng)符合這兩個(gè)條件時(shí)，任一層都無(wú)法產(chǎn)生更小的節(jié)點(diǎn)去和下層節(jié)點(diǎn)交換，也無(wú)法產(chǎn)生更大的節(jié)點(diǎn)去和上層節(jié)點(diǎn)交換。

上 面的兩個(gè)例子是比較簡(jiǎn)單的，實(shí)際的文件中，一個(gè)字節(jié)有256種可能的取值，所以二叉樹的葉子節(jié)點(diǎn)多達(dá)256個(gè)，需要不斷的調(diào)整樹形，最終的樹形可能非常復(fù) 雜，有一種非常精巧的算法可以快速地建起一棵最優(yōu)二叉樹，這種算法由D.Huffman（戴·霍夫曼）提出，下面我們先來(lái)介紹霍夫曼算法的步驟，然后再來(lái) 證明通過這么簡(jiǎn)單的步驟得出的樹形確實(shí)是一棵最優(yōu)二叉樹。

霍夫曼算法的步驟是這樣的：

·從各個(gè)節(jié)點(diǎn)中找出最小的兩個(gè)節(jié)點(diǎn)，給它們建一個(gè)父節(jié)點(diǎn)，值為這兩個(gè)節(jié)點(diǎn)之和。
·然后從節(jié)點(diǎn)序列中去除這兩個(gè)節(jié)點(diǎn)，加入它們的父節(jié)點(diǎn)到序列中。

重復(fù)上面兩個(gè)步驟，直到節(jié)點(diǎn)序列中只剩下唯一一個(gè)節(jié)點(diǎn)。這時(shí)一棵最優(yōu)二叉樹就已經(jīng)建成了，它的根就是剩下的這個(gè)節(jié)點(diǎn)。

仍以上面的例子來(lái)看霍夫曼樹的建立過程。
最初的節(jié)點(diǎn)序列是這樣的：
a(6) 　b(15) 　c(2) 　d(9) 　e(1)

把最小的c和e結(jié)合起來(lái)
　　　　　　　　　　　　 　　 　 　| (3)
a(6) 　　b(15) 　　d(9)　　　　+------+------+
　　　　　　　　　　　　　　|　　 　　　|
　　　　　　　　　　　　　　c　　　　　e

不斷重復(fù)，最終得到的樹是這樣的：

　　 　　　 根
　 　 　　　 |
　 　　+-----33-----+
　　　|　　　　　|
　　　15　　 +----18----+　　　
　　　　　　 | 　 　 　 |
　　　　　　 9　 +------9-----+
　 　　 　　　　　|　　 　 　 |
　　　　　　　　 6 　　 　+--3--+
　　 　　　　　　　　　 　|　　 |
　　　　 　　　 　　　　　2　　1

這時(shí)各個(gè)字符的編碼長(zhǎng)度和前面我們說過的方法得到的編碼長(zhǎng)度是相同的，因而文件的總長(zhǎng)度也是相同的： 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63

考察霍夫曼樹的建立過程中的每一步的節(jié)點(diǎn)序列的變化：

6 　15　2　9　1
6　 15　9　3
15　9　 9
15　18
33

下面我們用逆推法來(lái)證明對(duì)于各種不同的節(jié)點(diǎn)序列，用霍夫曼算法建立起來(lái)的樹總是一棵最優(yōu)二叉樹：

對(duì)霍夫曼樹的建立過程運(yùn)用逆推法：
當(dāng)這個(gè)過程中的節(jié)點(diǎn)序列只有兩個(gè)節(jié)點(diǎn)時(shí)（比如前例中的15和18），肯定是一棵最優(yōu)二叉樹，一個(gè)編碼為0，另一個(gè)編碼為1，無(wú)法再進(jìn)一步優(yōu)化。
然后往前步進(jìn)，節(jié)點(diǎn)序列中不斷地減少一個(gè)節(jié)點(diǎn)，增加兩個(gè)節(jié)點(diǎn)，在步進(jìn)過程中將始終保持是一棵最優(yōu)二叉樹，這是因?yàn)椋?br />1. 按照霍夫曼樹的建立過程，新增的兩個(gè)節(jié)點(diǎn)是當(dāng)前節(jié)點(diǎn)序列中最小的兩個(gè)，其他的任何兩個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)都大于（或等于）這兩個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，只要前一步是最優(yōu) 二叉樹，其他的任何兩個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)就一定都處在它們的父節(jié)點(diǎn)的上層或同層，所以這兩個(gè)節(jié)點(diǎn)一定處在當(dāng)前二叉樹的最低一層。
2.這兩個(gè)新增的節(jié)點(diǎn)是最小的，所以無(wú)法和其他上層節(jié)點(diǎn)對(duì)換。符合我們前面說的最優(yōu)二叉樹的第一個(gè)條件。
3. 只要前一步是最優(yōu)二叉樹，由于這兩個(gè)新增的節(jié)點(diǎn)是最小的，即使同層有其他節(jié)點(diǎn)，也無(wú)法和同層其他節(jié)點(diǎn)重新結(jié)合，產(chǎn)生比它們的父節(jié)點(diǎn)更小的上層節(jié)點(diǎn)來(lái)和同層 的其他節(jié)點(diǎn)對(duì)換。它們的父節(jié)點(diǎn)小于其他節(jié)點(diǎn)的父節(jié)點(diǎn)，它們又小于其他所有節(jié)點(diǎn)，只要前一步符合最優(yōu)二叉樹的第二個(gè)條件，到這一步仍將符合。

這樣一步步逆推下去，在這個(gè)過程中霍夫曼樹每一步都始終保持著是一棵最優(yōu)二叉樹。

由于每一步都從節(jié)點(diǎn)序列中刪除兩個(gè)節(jié)點(diǎn)，新增一個(gè)節(jié)點(diǎn)，霍夫曼樹的建立過程共需 (原始節(jié)點(diǎn)數(shù) - 1) 步，所以霍夫曼算法不失為一種精巧的編碼式壓縮算法。


附：對(duì)于 huffman 樹，《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》中有完全不同的證明，大意是這樣的：
１．二叉編碼樹的內(nèi)部節(jié)點(diǎn)（非葉子節(jié)點(diǎn)）數(shù)等于外部節(jié)點(diǎn)（葉子節(jié)點(diǎn)）數(shù)減１。
２．二叉編碼樹的外部節(jié)點(diǎn)的加權(quán)路徑長(zhǎng)度（值乘以路徑長(zhǎng)度）之和，等于所有內(nèi)部節(jié)點(diǎn)值之和。（這兩條都可以通過對(duì)節(jié)點(diǎn)數(shù)運(yùn)用數(shù)學(xué)歸納法來(lái)證明，留給大家做練習(xí)。）
３．對(duì) huffman 樹的建立過程運(yùn)用逆推，當(dāng)只有一個(gè)內(nèi)部節(jié)點(diǎn)時(shí)，肯定是一棵最優(yōu)二叉樹。
４． 往前步進(jìn)，新增兩個(gè)最小的外部節(jié)點(diǎn)，它們結(jié)合在一起產(chǎn)生一個(gè)新的內(nèi)部節(jié)點(diǎn)，當(dāng)且僅當(dāng)原先的內(nèi)部節(jié)點(diǎn)集合是極小化的，加入這個(gè)新的內(nèi)部節(jié)點(diǎn)后仍是極小化的。 （因?yàn)樽钚〉膬蓚€(gè)節(jié)點(diǎn)結(jié)合在一起，并處于最低層，相對(duì)于它們分別和其他同層或上層節(jié)點(diǎn)結(jié)合在一起，至少不會(huì)增加加權(quán)路徑長(zhǎng)度。）
５．隨著內(nèi)部節(jié)點(diǎn)數(shù)逐個(gè)增加，內(nèi)部節(jié)點(diǎn)集合總維持極小化。




２．實(shí)現(xiàn)部分
　 　如果世界上從沒有一個(gè)壓縮程序，我們看了前面的壓縮原理，將有信心一定能作出一個(gè)可以壓縮大多數(shù)格式、內(nèi)容的數(shù)據(jù)的程序，當(dāng)我們著手要做這樣一個(gè)程序的 時(shí)候，會(huì)發(fā)現(xiàn)有很多的難題需要我們?nèi)ヒ粋€(gè)個(gè)解決，下面將逐個(gè)描述這些難題，并詳細(xì)分析 zip 算法是如何解決這些難題的，其中很多問題帶有普遍意義，比如查找匹配，比如數(shù)組排序等等，這些都是說不盡的話題，讓我們深入其中，做一番思考。

我們前面說過，對(duì)于短語(yǔ)式重復(fù)，我們用“重復(fù)距當(dāng)前位置的距離”和“重復(fù)的長(zhǎng)度”這兩個(gè)數(shù)字來(lái)表示這一段重復(fù)，以實(shí)現(xiàn)壓縮，現(xiàn)在問題來(lái)了，一個(gè)字節(jié) 能表示的數(shù)字大小為 0 －255，然而重復(fù)出現(xiàn)的位置和重復(fù)的長(zhǎng)度都可能超過 255，事實(shí)上，二進(jìn)制數(shù)的位數(shù)確定下來(lái)后，所能表示的數(shù)字大小的范圍是有限的，ｎ位的二進(jìn)制數(shù)能表示的最大值是２的ｎ次方減１，如果位數(shù)取得太大，對(duì)于 大量的短匹配，可能不但起不到壓縮作用，反而增大了最終的結(jié)果。針對(duì)這種情況，有兩種不同的算法來(lái)解決這個(gè)問題，它們是兩種不同的思路。一種稱為 lz77 算法，這是一種很自然的思路：限制這兩個(gè)數(shù)字的大小，以取得折衷的壓縮效果。例如距離取 15 位，長(zhǎng)度取 8 位，這樣，距離的最大取值為 32 k - 1，長(zhǎng)度的最大取值為 255，這兩個(gè)數(shù)字占 23 位，比三個(gè)字節(jié)少一位，是符合壓縮的要求的。讓我們?cè)陬^腦中想象一下 lz77 算法壓縮進(jìn)行時(shí)的情況，會(huì)出現(xiàn)有意思的模型：

　　　最遠(yuǎn)匹配位置－＞　　　　　　　　　　當(dāng)前處理位置－＞
───┸─────────────────╂─────────────＞壓縮進(jìn)行方向
　　　已壓縮部分　　　　　　　　　　　　　┃　　　　未壓縮部分

　　在最遠(yuǎn)匹配位置和當(dāng)前處理位置之間是可以用來(lái)查找匹配的“字典”區(qū)域，隨著壓縮的進(jìn)行，“字典”區(qū)域從待壓縮文件的頭部不斷地向后滑動(dòng)，直到達(dá)到文件的尾部，短語(yǔ)式壓縮也就結(jié)束了。
　　解壓縮也非常簡(jiǎn)單：

　　　　　　　　　┎────────拷貝────────┒
　匹配位置　　　　┃　　　　　　　　　　當(dāng)前處理位置　　┃
　　　┃＜──匹配長(zhǎng)度──＞┃　　　　　　　┠─────∨────┨
───┸──────────┸───────╂──────────┸─＞解壓進(jìn)行方向
　　　已解壓部分　　　　　　　　　　　　　　┃　　　　未解壓部分

　　不斷地從壓縮文件中讀出匹配位置值和匹配長(zhǎng)度值，把已解壓部分的匹配內(nèi)容拷貝到解壓文件尾部，遇到壓縮文件中那些壓縮時(shí)未能得到匹配，而是直接保存的單、雙字節(jié)，解壓時(shí)只要直接拷貝到文件尾部即可，直到整個(gè)壓縮文件處理完畢。
　　lz77算法模型也被稱為“滑動(dòng)字典”模型或“滑動(dòng)窗口”模型。
　　另有一種lzw算法對(duì)待壓縮文件中存在大量簡(jiǎn)單匹配的情況進(jìn)行了完全不同的算法設(shè)計(jì)，它只用一個(gè)數(shù)字來(lái)表示一段短語(yǔ)，下面來(lái)描述一下lzw的壓縮解壓過程，然后來(lái)綜合比較兩者的適用情況。
　　lzw的壓縮過程：
1) 初始化一個(gè)指定大小的字典，把 256 種字節(jié)取值加入字典。
2) 在待壓縮文件的當(dāng)前處理位置尋找在字典中出現(xiàn)的最長(zhǎng)匹配，輸出該匹配在字典中的序號(hào)。
3) 如果字典沒有達(dá)到最大容量，把該匹配加上它在待壓縮文件中的下一個(gè)字節(jié)加入字典。
4) 把當(dāng)前處理位置移到該匹配后。
5) 重復(fù) 2、3、4 直到文件輸出完畢。

　　lzw 的解壓過程：
1) 初始化一個(gè)指定大小的字典，把 256 種字節(jié)取值加入字典。
2) 從壓縮文件中順序讀出一個(gè)字典序號(hào)，根據(jù)該序號(hào)，把字典中相應(yīng)的數(shù)據(jù)拷貝到解壓文件尾部。
3) 如果字典沒有達(dá)到最大容量，把前一個(gè)匹配內(nèi)容加上當(dāng)前匹配的第一個(gè)字節(jié)加入字典。
4) 重復(fù) 2、3 兩步直到壓縮文件處理完畢。

　　從 lzw 的壓縮過程，我們可以歸納出它不同于 lz77 算法的一些主要特點(diǎn)：
1) 對(duì)于一段短語(yǔ)，它只輸出一個(gè)數(shù)字，即字典中的序號(hào)。（這個(gè)數(shù)字的位數(shù)決定了字典的最大容量，當(dāng)它的位數(shù)取得太大時(shí)，比如 24 位以上，對(duì)于短匹配占多數(shù)的情況，壓縮率可能很低。取得太小時(shí)，比如 8 位，字典的容量受到限制。所以同樣需要取舍。）
2) 對(duì)于一個(gè)短語(yǔ)，比如 abcd ，當(dāng)它在待壓縮文件中第一次出現(xiàn)時(shí)，ab 被加入字典，第二次出現(xiàn)時(shí)，abc 被加入字典，第三次出現(xiàn)時(shí)，abcd 才會(huì)被加入字典，對(duì)于一些長(zhǎng)匹配，它必須高頻率地出現(xiàn)，并且字典有較大的容量，才會(huì)被最終完整地加入字典。相應(yīng)地，lz77 只要匹配在“字典區(qū)域”中存在，馬上就可以直接使用。
3) 設(shè) lzw 的“字典序號(hào)”取 n 位，它的最大長(zhǎng)度可以達(dá)到 2 的 n 次方；設(shè) lz77 的“匹配長(zhǎng)度”取 n 位，“匹配距離”取 d 位，它的最大長(zhǎng)度也是 2 的 n 次方，但還要多輸出 d 位（d 至少不小于 n），從理論上說 lzw 每輸出一個(gè)匹配只要 n 位，不管是長(zhǎng)匹配還是短匹配，壓縮率要比 lz77 高至少一倍，但實(shí)際上，lzw 的字典中的匹配長(zhǎng)度的增長(zhǎng)由于各匹配互相打斷，很難達(dá)到最大值。而且雖然 lz77 每一個(gè)匹配都要多輸出 d 位，但 lzw 每一個(gè)匹配都要從單字節(jié)開始增長(zhǎng)起，對(duì)于種類繁多的匹配，lzw 居于劣勢(shì)。
　　可以看出，在多數(shù)情況下，lz77 擁有更高的壓縮率，而在待壓縮文件中占絕大多數(shù)的是些簡(jiǎn)單的匹配時(shí)，lzw 更具優(yōu)勢(shì)，GIF 就是采用了 lzw 算法來(lái)壓縮背景單一、圖形簡(jiǎn)單的圖片。zip 是用來(lái)壓縮通用文件的，這就是它采用對(duì)大多數(shù)文件有更高壓縮率的 lz77 算法的原因。

　　接下來(lái) zip 算法將要解決在“字典區(qū)域”中如何高速查找最長(zhǎng)匹配的問題。

（注：以下關(guān)于技術(shù)細(xì)節(jié)的描述是以 gzip 的公開源代碼為基礎(chǔ)的，如果需要完整的代碼，可以在 gzip 的官方網(wǎng)站 www.gzip.org 下載。下面提到的每一個(gè)問題，都首先介紹最直觀簡(jiǎn)單的解決方法，然后指出這種方法的弊端所在，最后介紹 gzip 采用的做法，這樣也許能使讀者對(duì) gzip 看似復(fù)雜、不直觀的做法的意義有更好的理解。）
最 直觀的搜索方式是順序搜索：以待壓縮部分的第一個(gè)字節(jié)與窗口中的每一個(gè)字節(jié)依次比較，當(dāng)找到一個(gè)相等的字節(jié)時(shí)，再比較后續(xù)的字節(jié)…… 遍歷了窗口后得出最長(zhǎng)匹配。gzip 用的是被稱作“哈希表”的方法來(lái)實(shí)現(xiàn)較高效的搜索。“哈希（hash）”是分散的意思，把待搜索的數(shù)據(jù)按照字節(jié)值分散到一個(gè)個(gè)“桶”中，搜索時(shí)再根據(jù)字節(jié) 值到相應(yīng)的“桶”中去尋找。短語(yǔ)式壓縮的最短匹配為 3 個(gè)字節(jié)，gzip 以 3 個(gè)字節(jié)的值作為哈希表的索引，但 3 個(gè)字節(jié)共有 2 的 24 次方種取值，需要 16M 個(gè)桶，桶里存放的是窗口中的位置值，窗口的大小為 32K，所以每個(gè)桶至少要有大于兩個(gè)字節(jié)的空間，哈希表將大于 32M，作為 90 年代開發(fā)的程序，這個(gè)要求是太大了，而且隨著窗口的移動(dòng)，哈希表里的數(shù)據(jù)會(huì)不斷過時(shí)，維護(hù)這么大的表，會(huì)降低程序的效率，gzip 定義哈希表為 2 的 15 次方（32K）個(gè)桶，并設(shè)計(jì)了一個(gè)哈希函數(shù)把 16M 種取值對(duì)應(yīng)到 32K 個(gè)桶中，不同的值被對(duì)應(yīng)到相同的桶中是不可避免的，哈希函數(shù)的任務(wù)是 1.使各種取值盡可能均勻地分布到各個(gè)桶中，避免許多不同的值集中到某些桶中，而另一些是空桶，使搜索的效率降低。2.函數(shù)的計(jì)算盡可能地簡(jiǎn)單，因?yàn)槊看? “插入”和“搜尋”哈希表都要執(zhí)行哈希函數(shù)，哈希函數(shù)的復(fù)雜度直接影響程序的執(zhí)行效率，容易想到的哈希函數(shù)是取 3 個(gè)字節(jié)的左邊（或右邊）15 位二進(jìn)制值，但這樣只要左邊（或右邊）2 個(gè)字節(jié)相同，就會(huì)被放到同一個(gè)桶中，而 2 個(gè)字節(jié)相同的概率是比較高的，不符合“平均分布”的要求。gzip 采用的算法是：A(4,5) + A(6,7,8) ^ B(1,2,3) + B(4,5) + B(6,7,8) ^ C(1,2,3) + C(4,5,6,7,8) （說明：A 指 3 個(gè)字節(jié)中的第 1 個(gè)字節(jié)，B 指第 2 個(gè)字節(jié)，C 指第 3 個(gè)字節(jié)，A(4,5) 指第一個(gè)字節(jié)的第 4,5 位二進(jìn)制碼，“^”是二進(jìn)制位的異或操作，“+”是“連接”而不是“加”，“^”優(yōu)先于“+”）這樣使 3 個(gè)字節(jié)都盡量“參與”到最后的結(jié)果中來(lái)，而且每個(gè)結(jié)果值 h 都等于 ((前1個(gè)h << 5) ^ c)取右 15 位，計(jì)算也還簡(jiǎn)單。
哈希表的具體實(shí)現(xiàn)也值得探討,因?yàn)闊o(wú)法預(yù)先知道每一個(gè)“桶”會(huì)存放多少個(gè)元素，所以最簡(jiǎn)單的，會(huì)想到用鏈表來(lái)實(shí)現(xiàn)：哈希表里存放著每個(gè)桶的第一個(gè) 元素，每個(gè)元素除了存放著自身的值，還存放著一個(gè)指針，指向同一個(gè)桶中的下一個(gè)元素，可以順著指針鏈來(lái)遍歷該桶中的每一個(gè)元素，插入元素時(shí)，先用哈希函數(shù) 算出該放到第幾個(gè)桶中，再把它掛到相應(yīng)鏈表的最后。這個(gè)方案的缺點(diǎn)是頻繁地申請(qǐng)和釋放內(nèi)存會(huì)降低運(yùn)行速度；內(nèi)存指針的存放占據(jù)了額外的內(nèi)存開銷。有更少內(nèi) 存開銷和更快速的方法來(lái)實(shí)現(xiàn)哈希表，并且不需要頻繁的內(nèi)存申請(qǐng)和釋放：gzip 在內(nèi)存中申請(qǐng)了兩個(gè)數(shù)組，一個(gè)叫 head[]，一個(gè)叫 pre[]，大小都為 32K，根據(jù)當(dāng)前位置 strstart 開始的 3 個(gè)字節(jié)，用哈希函數(shù)計(jì)算出在 head[] 中的位置 ins_h，然后把 head[ins_h] 中的值記入 pre[strstart]，再把當(dāng)前位置 strstart 記入 head[ins_h]。隨著壓縮的進(jìn)行，head[]里記載著最近的可能的匹配的位置（如果有匹配的話，head[ins_h]不為 0），pre[]中的所有位置與原始數(shù)據(jù)的位置相對(duì)應(yīng)，但每一個(gè)位置保存的值是前一個(gè)最近的可能的匹配的位置。（“可能的匹配”是指哈希函數(shù)計(jì)算出的 ins_h 相同。）順著 pre[] 中的指示找下去，直到遇到 0，可以得到所有匹配在原始數(shù)據(jù)中的位置，0 表示不再有更遠(yuǎn)的匹配。
　　接下來(lái)很自然地要觀察 gzip 具體是如何判斷哈希表中數(shù)據(jù)的過時(shí)，如何清理哈希表的，因?yàn)?pre[] 里只能存放 32K 個(gè)元素，所以這項(xiàng)工作是必須要做的。
　 　gzip 從原始文件中讀出兩個(gè)窗口大小的內(nèi)容（共 64K 字節(jié)）到一塊內(nèi)存中，這塊內(nèi)存也是一個(gè)數(shù)組，稱作 Window[]；申請(qǐng) head[]、pre[] 并清零；strstart 置為 0。然后 gzip 邊搜索邊插入，搜索時(shí)通過計(jì)算 ins_h，檢查 head[] 中是否有匹配，如果有匹配，判斷 strstart 減 head[] 中的位置是否大于 1 個(gè)窗口的大小，如果大于 1 個(gè)窗口的大小，就不到 pre[] 中去搜索了，因?yàn)?pre[] 中保存的位置更遠(yuǎn)了，如果不大于，就順著 pre[] 的指示到 Window[] 中逐個(gè)匹配位置開始，逐個(gè)字節(jié)與當(dāng)前位置的數(shù)據(jù)比較，以找出最長(zhǎng)匹配，pre[] 中的位置也要判斷是否超出一個(gè)窗口，如遇到超出一個(gè)窗口的位置或者 0 就不再找下去，找不到匹配就輸出當(dāng)前位置的單個(gè)字節(jié)到另外的內(nèi)存（輸出方法在后文中會(huì)介紹），并把 strstart 插入哈希表，strstart 遞增，如果找到了匹配，就輸出匹配位置和匹配長(zhǎng)度這兩個(gè)數(shù)字到另外的內(nèi)存中，并把 strstart 開始的，直到 strstart + 匹配長(zhǎng)度 為止的所有位置都插入哈希表，strstart += 匹配長(zhǎng)度。插入哈希表的方法為：
pre[strstart % 32K] = head[ins_h];
head[ins_h] = strstart;
可 以看出，pre[] 是循環(huán)利用的，所有的位置都在一個(gè)窗口以內(nèi)，但每一個(gè)位置保存的值不一定是一個(gè)窗口以內(nèi)的。在搜索時(shí)，head[] 和 pre[] 中的位置值對(duì)應(yīng)到 pre[] 時(shí)也要 % 32K。當(dāng) Window[] 中的原始數(shù)據(jù)將要處理完畢時(shí)，要把 Window[] 中后一窗的數(shù)據(jù)復(fù)制到前一窗，再讀取 32K 字節(jié)的數(shù)據(jù)到后一窗，strstart -= 32K，遍歷 head[]，值小于等于 32K 的，置為 0，大于 32K 的，-= 32K；pre[] 同 head[] 一樣處理。然后同前面一樣處理新一窗的數(shù)據(jù)。
　　分析：現(xiàn)在可以 看到，雖然 3 個(gè)字節(jié)有 16M 種取值，但實(shí)際上一個(gè)窗口只有 32K 個(gè)取值需要插入哈希表，由于短語(yǔ)式重復(fù)的存在，實(shí)際只有 < 32K 種取值插入哈希表的 32K 個(gè)“桶”中，而且哈希函數(shù)又符合“平均分布”的要求，所以哈希表中實(shí)際存在的“沖突”一般不會(huì)多，對(duì)搜索效率的影響不大。可以預(yù)計(jì)，在“一般情況”下，每 個(gè)“桶”中存放的數(shù)據(jù)，正是我們要找的。哈希表在各種搜索算法中，實(shí)現(xiàn)相對(duì)的比較簡(jiǎn)單，容易理解，“平均搜索速度”最快，哈希函數(shù)的設(shè)計(jì)是搜索速度的關(guān) 鍵，只要符合“平均分布”和“計(jì)算簡(jiǎn)單”，就常常能成為諸種搜索算法中的首選，所以哈希表是最流行的一種搜索算法。但在某些特殊情況下，它也有缺點(diǎn)，比 如：1.當(dāng)鍵碼 k 不存在時(shí)，要求找出小于 k 的最大鍵碼或大于 k 的最小鍵碼，哈希表無(wú)法有效率地滿足這種要求。2.哈希表的“平均搜索速度”是建立在概率論的基礎(chǔ)上的，因?yàn)槭孪炔荒茴A(yù)知待搜索的數(shù)據(jù)集合，我們只能“信 賴”搜索速度的“平均值”，而不能“保證”搜索速度的“上限”。在同人類性命攸關(guān)的應(yīng)用中（如醫(yī)療或宇航領(lǐng)域），將是不合適的。這些情況及其他一些特殊情 況下，我們必須求助其他“平均速度”較低，但能滿足相應(yīng)的特殊要求的算法。（見《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》第3卷 排序與查找）。幸而“在窗口中搜索匹配字節(jié)串”不屬于特殊情況。

時(shí)間與壓縮率的平衡：
gzip 定義了幾種可供選擇的 level，越低的 level 壓縮時(shí)間越快但壓縮率越低，越高的 level 壓縮時(shí)間越慢但壓縮率越高。
不同的 level 對(duì)下面四個(gè)變量有不同的取值：

nice_length
max_chain
max_lazy
good_length

nice_length： 前面說過，搜索匹配時(shí)，順著 pre[] 的指示到 Window[] 中逐個(gè)匹配位置開始，找出最長(zhǎng)匹配，但在這過程中，如果遇到一個(gè)匹配的長(zhǎng)度達(dá)到或超過 nice_length，就不再試圖尋找更長(zhǎng)的匹配。最低的 level 定義 nice_length 為 8，最高的 level 定義 nice_length 為 258（即一個(gè)字節(jié)能表示的最大短語(yǔ)匹配長(zhǎng)度 3 + 255）。

max_chain：這個(gè)值規(guī)定了順著 pre[] 的指示往前回溯的最大次數(shù)。最低的 level 定義 max_chain 為 4，最高的 level 定義 max_chain 為 4096。當(dāng) max_chain 和 nice_length 有沖突時(shí)，以先達(dá)到的為準(zhǔn)。

max_lazy：這里有一個(gè)懶惰匹配（lazy match）的概念，在輸出當(dāng)前位置（strstart）的匹配之前，gzip 會(huì)去找下一個(gè)位置（strstart + 1）的匹配，如果下一個(gè)匹配的長(zhǎng)度比當(dāng)前匹配的長(zhǎng)度更長(zhǎng)，gzip 就放棄當(dāng)前匹配，只輸出當(dāng)前位置處的首個(gè)字節(jié)，然后再查找 strstart + 2 處的匹配，這樣的方式一直往后找，如果后一個(gè)匹配比前一個(gè)匹配更長(zhǎng)，就只輸出前一個(gè)匹配的首字節(jié)，直到遇到前一個(gè)匹配長(zhǎng)于后一個(gè)匹配，才輸出前一個(gè)匹配。
gzip 作者的思路是，如果后一個(gè)匹配比前一個(gè)匹配更長(zhǎng)，就犧牲前一個(gè)匹配的首字節(jié)來(lái)?yè)Q取后面的大于等于1的額外的匹配長(zhǎng)度。
max_lazy 規(guī)定了，如果匹配的長(zhǎng)度達(dá)到或超過了這個(gè)值，就直接輸出，不再管后一個(gè)匹配是否更長(zhǎng)。最低的4級(jí) level 不做懶惰匹配，第5級(jí) level 定義 max_lazy 為 4，最高的 level 定義 max_lazy 為 258。

good_length： 這個(gè)值也和懶惰匹配有關(guān)，如果前一個(gè)匹配長(zhǎng)度達(dá)到或超過 good_length，那在尋找當(dāng)前的懶惰匹配時(shí)，回溯的最大次數(shù)減小到 max_chain 的 1/4，以減少當(dāng)前的懶惰匹配花費(fèi)的時(shí)間。第5級(jí) level 定義 good_length 為 4（這一級(jí)等于忽略了 good_length），最高的 level 定義 good_length 為 32。

分析：懶惰匹配有必要嗎？可以改進(jìn)嗎？
gzip 的作者是無(wú)損壓縮方面的專家，但是世界上沒有絕對(duì)的權(quán)威，吾愛吾師，更愛真理。我覺得 gzip 的作者對(duì)懶惰匹配的考慮確實(shí)不夠周詳。只要是進(jìn)行了認(rèn)真客觀的分析，誰(shuí)都有權(quán)利提出自己的觀點(diǎn)。
采用懶惰匹配，需要對(duì)原始文件的更多的位置查找匹配，時(shí)間肯定增加了許多倍，但壓縮率的提高在總體上十分有限。在幾種情況下，它反而增長(zhǎng)了短語(yǔ)壓縮的結(jié)果，所以如果一定要用懶惰匹配，也應(yīng)該改進(jìn)一下算法，下面是具體的分析。
1. 連續(xù)3次以上找到了更長(zhǎng)的匹配，就不應(yīng)該單個(gè)輸出前面的那些字節(jié)，而應(yīng)該作為匹配輸出。
2. 于是，如果連續(xù)找到更長(zhǎng)的匹配的次數(shù)大于第一個(gè)匹配的長(zhǎng)度，對(duì)于第一個(gè)匹配，相當(dāng)于沒有做懶惰匹配。
3. 如果小于第一個(gè)匹配的長(zhǎng)度但大于2，就沒有必要作懶惰匹配，因?yàn)檩敵龅目偸莾蓚€(gè)匹配。
4. 所以找到一個(gè)匹配后，最多只需要向后做 2 次懶惰匹配，就可以決定是輸出第一個(gè)匹配，還是輸出1（或 2）個(gè)首字節(jié)加后面的匹配了。
5. 于是，對(duì)于一段原始字節(jié)串，如果不做懶惰匹配時(shí)輸出兩個(gè)匹配（對(duì)于每個(gè)匹配，距離占15位二進(jìn)制數(shù)，長(zhǎng)度占8位二進(jìn)制數(shù)，加起來(lái)約占3字節(jié)，輸出兩個(gè)匹配 約需要6字節(jié)），做了懶惰匹配如果有改進(jìn)的話，將是輸出1或2個(gè)單字節(jié)加上1個(gè)匹配（也就是約4或5字節(jié)）。這樣，懶惰匹配可以使某些短語(yǔ)壓縮的結(jié)果再縮 短1/3到1/6。
6. 再觀察這樣一個(gè)例子：
1232345145678[當(dāng)前位置]12345678
不用懶惰匹配，約輸出6字節(jié)，用懶惰匹配，約輸出7字節(jié)，由于使用了懶惰匹配，把更后面的一個(gè)匹配拆成了兩個(gè)匹配。（如果 678 正好能歸入再后面的一個(gè)匹配，那懶惰匹配可能是有益的。）
7. 綜合考慮各種因素（匹配數(shù)和未匹配的單雙字節(jié)在原始文件中所占的比例，后一個(gè)匹配長(zhǎng)度大于前一個(gè)匹配長(zhǎng)度的概率，等等），經(jīng)過改進(jìn)的懶惰匹配算法，對(duì)總的 壓縮率即使有貢獻(xiàn)，也仍是很小的，而且也仍然很有可能會(huì)降低壓縮率。再考慮到時(shí)間的確定的明顯的增加與壓縮率的不確定的微弱的增益，也許最好的改進(jìn)是果斷 地放棄懶惰匹配。

gzip 在完成短語(yǔ)式壓縮后，將轉(zhuǎn)入編碼式壓縮的階段。這個(gè)階段的實(shí)現(xiàn)是很復(fù)雜的，對(duì)最終的壓縮率至關(guān)重要，我會(huì)詳細(xì)解說 gzip 的做法。gzip 是開放源代碼的無(wú)損壓縮程序中最著名的，其中的種種技巧很有啟發(fā)意義，但是他是比較早期的程序，現(xiàn)在有很多的程序已經(jīng)在壓縮率上超過了它，所以我會(huì)根據(jù)自 己對(duì)無(wú)損壓縮的基本規(guī)律的理解提出對(duì)它的改進(jìn)。

編碼式壓縮的幾點(diǎn)考慮：
1. huffman 算法壓縮率的關(guān)鍵是各節(jié)點(diǎn)值的差異要大，這樣就要求分段編碼輸出。因?yàn)槟承┒温渲心承┕?jié)點(diǎn)的出現(xiàn)頻率較高，另一些段落中這些節(jié)點(diǎn)出現(xiàn)頻率較低，如果不分段輸出，頻率的差異會(huì)被彼此抵消，而不同段落中，節(jié)點(diǎn)的出現(xiàn)頻率不同是常有的。
　　要決定分段的大小，必須解決一對(duì)矛盾：上面的分析似乎要求段落越小越好，但由于要保存碼表以對(duì) huffman 壓縮結(jié)果進(jìn)行解壓，每個(gè)段落都要保存一份不同的碼表，所以段落取得太小，保存了碼表后得不償失，這樣，似乎又要求段落要盡量大，使碼表的保存份數(shù)盡量少。
　 　gzip 采取了這樣的策略來(lái)確定段落的大小：lz77 壓縮每產(chǎn)生 4k（小）的數(shù)據(jù)，就判斷現(xiàn)在對(duì)未編碼部分進(jìn)行編碼輸出是否合適，最多積壓到 32k（大）的時(shí)候，必定進(jìn)行強(qiáng)制輸出，因?yàn)槠接沟臄?shù)據(jù)積壓得太多，后面即使有好的數(shù)據(jù)，頻率統(tǒng)計(jì)在一起，也會(huì)被平庸化。
　　判斷當(dāng)前輸出合適與 否的條件是：1)用預(yù)先設(shè)定好的各節(jié)點(diǎn)長(zhǎng)度和各節(jié)點(diǎn)實(shí)際的出現(xiàn)次數(shù)，計(jì)算壓縮結(jié)果的大概值，看這個(gè)值是否小于未壓縮時(shí)的 1/2。2)看目前為止的匹配數(shù)是否小于未匹配的字節(jié)數(shù)，因?yàn)?lz77 壓縮產(chǎn)生的數(shù)據(jù)包括“匹配”和“未匹配的原始字節(jié)”，段落間的節(jié)點(diǎn)頻率差異主要體現(xiàn)在“未匹配的原始字節(jié)”中。
　　上面的判斷只是一種“猜測(cè)”，真正的精確的計(jì)算需要花費(fèi)更多的時(shí)間。
　 　我覺得 gzip 的策略可以改進(jìn)，我的策略是：1)輸出的時(shí)機(jī)是壓縮率的關(guān)鍵之一，現(xiàn)在計(jì)算機(jī)的速度和九十年代時(shí)已經(jīng)今非昔比，現(xiàn)在完全有條件采用真正的建 huffman 樹的方法得到各節(jié)點(diǎn)的碼長(zhǎng)，作精確的判斷。2)不應(yīng)該與未壓縮的原始數(shù)據(jù)比較，而應(yīng)該與 lz77 輸出的數(shù)據(jù)比較，否則計(jì)算出的壓縮比很大一部分是短語(yǔ)式壓縮的功勞。3)由于采用了真正的建 huffman 樹的方法，不用再去做匹配數(shù)與未匹配的字節(jié)數(shù)的比較，因?yàn)槟侵皇且环N猜測(cè)。4)每 4k 的數(shù)據(jù)都單獨(dú)統(tǒng)計(jì)頻率，如果是合適的，就先輸出之前的積壓（如果有的話），再輸出當(dāng)前的 4k，這樣可以避免當(dāng)前的數(shù)據(jù)被積壓的數(shù)據(jù)平庸化。如果不合適，就把當(dāng)前的頻率歸入到積壓的數(shù)據(jù)（如果有）的頻率中，再判斷是否合適，如仍不合適就暫緩輸 出，否則一起輸出，這和 gzip 的作法是一樣的。說明：幾段差的數(shù)據(jù)積壓到一起仍有可能成為好的數(shù)據(jù)，比如 01、 02、……積壓在一起，0 的頻率逐漸高出了其他字節(jié)。5)如果愿意付出更多的時(shí)間，在把當(dāng)前的頻率歸入之前的頻率時(shí)，可以先和之前 4k 的頻率合并，如果不合適，和之前 8k 的頻率合并，這樣逐漸往前合并 4k，避免前面不好的數(shù)據(jù)拖累合并后的好的數(shù)據(jù)。6)有了前面的機(jī)制，32k 的強(qiáng)制輸出點(diǎn)可以取消。7)進(jìn)一步的改進(jìn)：當(dāng)要輸出時(shí)，只輸出積壓的不好的部分，好的數(shù)據(jù)先留著，等后面的 4k，如果新的加入后，仍是好的數(shù)據(jù)，就再等，如果會(huì)降低壓縮率，才輸出好的部分。這樣，讓好的數(shù)據(jù)大段的輸出，可以減少碼表的保存份數(shù)。8)再進(jìn)一步的 改進(jìn)：壞的數(shù)據(jù)放在一起可能會(huì)提高壓縮率，好的數(shù)據(jù)放在一起也可能更好，當(dāng)然，兩種情況也都有可能降低壓縮率，所以前面判斷“好”還是“不好”，“合適” 還是“不合適”的標(biāo)準(zhǔn)應(yīng)該從某一個(gè)固定的壓縮率標(biāo)準(zhǔn)改變?yōu)椋禾岣吡藟嚎s率還是降低了壓縮率。（提高的幅度應(yīng)該至少抵消多保存一份碼表的損失；降低的幅度也 應(yīng)該至少抵消少保存一份碼表的得益）9)綜合前面的分析，確定分段大小的策略最終調(diào)整為：當(dāng)新的數(shù)據(jù)和前面的未切分?jǐn)?shù)據(jù)放在一起時(shí)，兩者中任何一方受到損 失，都應(yīng)該設(shè)置切分點(diǎn)，積累了兩個(gè)分段后，通過計(jì)算，當(dāng)切分帶來(lái)的收益大于少保存一份碼表時(shí)，才輸出前一段，否則取消它們之間的切分點(diǎn)。這個(gè)策略實(shí)際上可 以涵蓋前面提到的所有改進(jìn)，因?yàn)槊總€(gè)實(shí)際的分段之中的數(shù)據(jù)或者相互促進(jìn)，或者彼此稍有妨害，但好過多保存一份碼表；而每?jī)蓚€(gè)相鄰的分段之間的數(shù)據(jù)彼此妨 害，抵消了少保存一份碼表的收益。這個(gè)策略簡(jiǎn)單直觀地體現(xiàn)了我們?cè)O(shè)置分段的初衷：就是分段輸出必須能提高壓縮率。

2. 如果不考慮碼表，huffman 算法能得到最短的編碼式壓縮結(jié)果，但是這種算法必須保存碼表以便解壓縮，所以不能保證結(jié)果是最佳的。gzip 預(yù)先擬定了一套通用的靜態(tài)的編碼，當(dāng)要輸出一個(gè)段落時(shí)，比較 huffman 壓縮結(jié)果加碼表的長(zhǎng)度和靜態(tài)編碼的壓縮結(jié)果長(zhǎng)度，再?zèng)Q定用哪種方法輸出這個(gè)段落。靜態(tài)編碼不需要建樹，計(jì)算壓縮結(jié)果長(zhǎng)度時(shí)耗時(shí)很少。如果各節(jié)點(diǎn)的頻率的差 異很小，huffman 壓縮結(jié)果加碼表反而增大了結(jié)果，靜態(tài)編碼也不合適，同樣增大了結(jié)果，gzip 就直接保存 lz77 的原始輸出。由于輸出一個(gè)段落時(shí)，增加了靜態(tài)編碼的方案，使輸出的實(shí)際長(zhǎng)度和之前確定分段點(diǎn)時(shí)計(jì)算的值可能不同，那么前面計(jì)算出的這個(gè)分段點(diǎn)是否仍是正確 的？前面的分段策略是否需要調(diào)整？
　　分析：1)靜態(tài)編碼的各節(jié)點(diǎn)編碼是不變的，對(duì)于段落的合并是無(wú)所謂的，兩個(gè)連續(xù)段落即使都采用靜態(tài)編碼，也 不用合并，因?yàn)楹喜⒑蠼Y(jié)果長(zhǎng)度是不會(huì)變的。2)所以只對(duì)一種情況可能有影響：一個(gè)段落中拆分出一些部分用 huffman 編碼，另一些部分用靜態(tài)編碼，壓縮結(jié)果更好。當(dāng)這種情況發(fā)生時(shí)，則必有一些部分的優(yōu)勢(shì)節(jié)點(diǎn)（頻率高的節(jié)點(diǎn)）與靜態(tài)編碼預(yù)先擬定的優(yōu)勢(shì)節(jié)點(diǎn)相近，采用靜態(tài)編 碼后有稍許改善，其他部分則與靜態(tài)編碼預(yù)先擬定的優(yōu)勢(shì)節(jié)點(diǎn)有一定分歧，采用靜態(tài)編碼后會(huì)有稍許不利。之所以說“稍許”，是因?yàn)槲覀円阎粋€(gè)段落里的各部 分?jǐn)?shù)據(jù)或者互相促進(jìn)，或者僅有稍許妨害，說明它們的優(yōu)勢(shì)節(jié)點(diǎn)是大致趨同的。考慮到拆分后可能要多保存幾份碼表，拆分帶來(lái)收益的可能性和程度是很小的，而且 計(jì)算的復(fù)雜度較大，所以前面的拆分策略可以不作調(diào)整。
　　至于直接保存 lz77 的原始輸出，可以看作靜態(tài)編碼的一種特殊形式，只不過它假定各節(jié)點(diǎn)的頻率相近，沒有優(yōu)勢(shì)節(jié)點(diǎn)。它可以套用靜態(tài)編碼的分析，來(lái)證明不影響前面已經(jīng)制定的分段策略。

3.采用 huffman 編碼，必須深入研究碼表的保存方式。
　　只要計(jì)算一下采用簡(jiǎn)單的方式來(lái)保存碼表，需要多大的空間，就知道這是一個(gè)挑戰(zhàn)。
　 　簡(jiǎn)單地保存碼表的方法是順序地保存每一個(gè)值的碼長(zhǎng)和編碼。之所以要保存碼長(zhǎng)，是因?yàn)榫幋a是不定長(zhǎng)的，沒有碼長(zhǎng)，解壓時(shí)無(wú)法正確讀取編碼。碼長(zhǎng)必須是定長(zhǎng) 的，也就是說必須限制 huffman 樹的最大層數(shù)，使碼長(zhǎng)的位數(shù)能恰好表示這個(gè)層數(shù)。限制 huffman 樹的最大層數(shù)的方法是：如果規(guī)定的最大層數(shù)為 n，則在 n - 1 層找到一個(gè)葉子節(jié)點(diǎn) a（如果 n - 1 層沒有葉子節(jié)點(diǎn)，就逐層地往上尋找，直到找到一個(gè)葉子節(jié)點(diǎn)），在節(jié)點(diǎn) a 的位置放一個(gè)非葉子節(jié)點(diǎn) A，使 a 成為 A 的子節(jié)點(diǎn)，把某個(gè)超過 n 層的葉子節(jié)點(diǎn) b 提上來(lái)作為 A 的另一個(gè)子節(jié)點(diǎn)，此時(shí) b 的父節(jié)點(diǎn) B 只剩下一個(gè)子節(jié)點(diǎn) c，取消 B，把 c 放在 B 的位置，重復(fù)這樣的過程，直到所有 n 層以下的節(jié)點(diǎn)都被提上來(lái)。之所以要從 n - 1 層開始逐層往上找，是因?yàn)橄聦拥墓?jié)點(diǎn)頻率小，碼長(zhǎng)變化后的影響小。假設(shè)每一層節(jié)點(diǎn)的頻率相近，那么上層父節(jié)點(diǎn)的頻率是其下層子節(jié)點(diǎn)的兩倍，第 11 層節(jié)點(diǎn)的頻率只有第一層節(jié)點(diǎn)頻率的 1 / 1024，所以應(yīng)該從下往上找。
　　現(xiàn)在就開始計(jì)算碼表大小：
　　對(duì)于 256 個(gè)原始字節(jié)值，限制它的 huffman 樹的層數(shù)為 0 － 15，碼長(zhǎng)就需要 4 位，256 個(gè)碼長(zhǎng)需要 4 bit * 256 = 128 字節(jié)；而 256 個(gè)新編碼需要至少 256 字節(jié)。（當(dāng)二叉樹的所有葉子節(jié)點(diǎn)都放在第 8 層 —— 不算根節(jié)點(diǎn)一層，正好能放下 2 的 8 次方 = 256 個(gè)葉子節(jié)點(diǎn)，其中任何一個(gè)葉子節(jié)點(diǎn)往上升，至少造成兩個(gè)葉子節(jié)點(diǎn)往下降。換一個(gè)角度說，如果在第 8 層以上存在一個(gè)葉子節(jié)點(diǎn) a，在節(jié)點(diǎn) a 的位置放一個(gè)非葉子節(jié)點(diǎn) A，使 a 成為 A 的子節(jié)點(diǎn)，把某個(gè)超過 8 層的葉子節(jié)點(diǎn) b 提上來(lái)作為 A 的另一個(gè)子節(jié)點(diǎn)，此時(shí) b 的父節(jié)點(diǎn) B 只剩下一個(gè)子節(jié)點(diǎn) c，取消 B，把 c 放在 B 的位置，此時(shí) a 增長(zhǎng)了一位，c 縮短了一位，b 縮短了至少一位，編碼的平均位長(zhǎng)縮短。所以，當(dāng)?shù)?8 層以上不存在葉子節(jié)點(diǎn)，所有葉子節(jié)點(diǎn)都放在第 8 層時(shí)，編碼的平均位長(zhǎng)達(dá)到最短 —— 8位。）這套碼表共需至少 128 + 256 = 384 字節(jié)。
　　256 個(gè)“匹配長(zhǎng)度”的情況與原始字節(jié)值相同，兩套碼表共需至少 384 * 2 = 768 字節(jié)。
　 　對(duì)于 32k 個(gè)“匹配距離”，如果限制該 huffman 樹的層數(shù)為 0 － 31，保存每個(gè)值的碼長(zhǎng)需要 5 位，新編碼的平均長(zhǎng)度超過 15 位。（因?yàn)樗腥~子節(jié)點(diǎn)都放在第 15 層 —— 不算根節(jié)點(diǎn)一層，正好能放下 2 的 15 次方 = 32k 個(gè)葉子節(jié)點(diǎn)。）這套碼表要超過80k 字節(jié)（ (5 + 15) * 32k / 8 = 80k ）。
　　前面討論分段策略時(shí)已經(jīng)說過，為了避免個(gè)段落間節(jié)點(diǎn)頻率差異被互相抵消，要求段落劃分盡量細(xì)致、準(zhǔn)確，最小的段落可以僅為 4k，而采用上面這種簡(jiǎn)單的方式，碼表要超過 80k，顯然是無(wú)法接受的。
　 　對(duì)碼表的保存方式的深入研究，確實(shí)是個(gè)無(wú)法繞開的挑戰(zhàn)，如果不攻克這個(gè)難關(guān)，編碼式壓縮無(wú)法進(jìn)行下去！挑戰(zhàn)會(huì)帶來(lái)樂趣，困難會(huì)激發(fā)豪情。我們所要做的 是：觀察 gzip 如何一步步地通過繁復(fù)但又巧妙的做法解決這個(gè)難題，對(duì)其中的做法的道理務(wù)求知其然、知其所以然，通過觀察、思考，把握無(wú)損壓縮內(nèi)在的、深層的、本質(zhì)的規(guī) 律！事實(shí)上，對(duì) gzip 的這些做法進(jìn)行閱讀（源代碼）、分析、挖掘其中的智慧，本身就是一個(gè)對(duì)智慧、耐力、乃至決心的長(zhǎng)期的挑戰(zhàn)，我接受了這個(gè)挑戰(zhàn)，并把它描述、解釋出來(lái)，讀者 面對(duì)的挑戰(zhàn)是花費(fèi)較長(zhǎng)期的時(shí)間去閱讀、理解，希望讀者完全有耐力、豪情、興趣來(lái)接受這個(gè)挑戰(zhàn)，深化自己的技術(shù)層次、思維層次。

3.1 只保存碼長(zhǎng)，并增加一些特殊的值。

3.1.1 把 huffman 樹的每一層上的葉子節(jié)點(diǎn)都換到該層的左邊，按照其原始值從小到大依次排列，非葉子節(jié)點(diǎn)則集中在該層右邊，這時(shí)仍是一棵二叉樹，得到的編碼仍符合前綴編碼的 要求。每個(gè)葉子節(jié)點(diǎn)的編碼長(zhǎng)度不變，所以壓縮率也不變。僅需要按照原始值從小到大依次保存每個(gè)值的碼長(zhǎng)，解壓時(shí)就可以還原這套編碼表，還原方法是：碼長(zhǎng)為 n 的第一個(gè)值的編碼是碼長(zhǎng)為 n - 1 的最后一個(gè)值的編碼加 1，并左移一位（也就是說，在編碼最后加個(gè) 0），而碼長(zhǎng)為 n 的其他值的編碼是前一個(gè)碼長(zhǎng)為 n 的值的編碼加 1。從上面所說的樹的角度來(lái)解釋，每一層的第一個(gè)葉子節(jié)點(diǎn)是其上層最后一個(gè)葉子節(jié)點(diǎn)的右邊一個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)，所以它的編碼是上層最后一個(gè)葉子節(jié)點(diǎn)的編碼 加 1 并左移一位，而每一層上的葉子節(jié)點(diǎn)都緊密排列，所以除了第一個(gè)葉子節(jié)點(diǎn)外，其他葉子節(jié)點(diǎn)的編碼都是前一個(gè)葉子節(jié)點(diǎn)的編碼加 1。編程上的實(shí)現(xiàn)方法是：遍歷碼表，得到每個(gè)碼長(zhǎng)(n)上有多少個(gè)值，計(jì)算出每個(gè)碼長(zhǎng)上第一個(gè)值的編碼，放在數(shù)組 bit_len[]中，再次遍歷碼表，依次根據(jù)每個(gè)值的碼長(zhǎng)(n)，賦予它的編碼為該碼長(zhǎng)上的前一個(gè)值的編碼 (bit_len[n]) 加 1，bit_len[n] ++。
　　由于只需要保存碼長(zhǎng)，現(xiàn)在碼表由超過 80k 字節(jié)減小到約 20k 字節(jié)。

3.1.2 如何只保存在段落中出現(xiàn)過的節(jié)點(diǎn)（有效節(jié)點(diǎn)）的編碼？
　 　一個(gè) ASCⅡ文本，128 以后的值是不會(huì)在文件中出現(xiàn)的，按照 3.1.1 的方法，碼表中后半部分（都是 0）在解壓縮時(shí)是用不到的。為了避免這類浪費(fèi)，只保存有效節(jié)點(diǎn)（碼長(zhǎng)不為 0 的節(jié)點(diǎn)），一種方法是保存有效節(jié)點(diǎn)的原始值和新編碼的碼長(zhǎng)，當(dāng)有效節(jié)點(diǎn)超過所有節(jié)點(diǎn)的1/4，這種方法保存的碼表的大小會(huì)超過 3.1.1 的方法。
　 　gzip 采用的方法是：在 3.1.1 的基礎(chǔ)上，于若干種碼長(zhǎng)之外，增加一些特殊的值，他們表示當(dāng)前為之前一個(gè)碼長(zhǎng)或 0 碼長(zhǎng)（無(wú)效節(jié)點(diǎn)）的重復(fù)，遇到這種值，那后面的一個(gè)數(shù)字表示重復(fù)的次數(shù)。第一種值代表當(dāng)前為之前一個(gè)碼長(zhǎng)的重復(fù) 3 － 6 次，后面跟著 2 bit 為具體的重復(fù)次數(shù)；第二種值代表當(dāng)前為 0 碼長(zhǎng)的重復(fù) 3 － 10 次，后面跟著 3 bit 為具體的重復(fù)次數(shù)；第三種值代表當(dāng)前為 0 碼長(zhǎng)的重復(fù) 11 － 138 次，后面跟著 7 bit 為具體的重復(fù)次數(shù)。限制最小重復(fù)次數(shù)為 3，可以確保這種方法得到的碼表不會(huì)大過 3.1.1。第一種值限制最大重復(fù)次數(shù)為 6，是因?yàn)檫B續(xù) 6 個(gè)值以上的碼長(zhǎng)相等（說明頻率十分接近）的情況不常見，做這個(gè)限制可以節(jié)省附加 bit；第二第三種值區(qū)分重復(fù)次數(shù)的范圍，也是為了節(jié)省附加 bit。在只有少數(shù)有效節(jié)點(diǎn)的情況下，這種方法只需要保存較少的數(shù)據(jù)，同時(shí)也具有簡(jiǎn)單的去重復(fù)的作用。
　　如果最大碼長(zhǎng)是 15，0 － 15 共 16 種值，一個(gè)碼長(zhǎng)需要 4 位，加上上面 3 種值，共 19 種值，需要 5 位，在重復(fù)不多時(shí)，加了這 3 種值，是不是會(huì)增大碼表？其實(shí)不用擔(dān)心，gzip 會(huì)對(duì)碼表再進(jìn)行一次 huffman 壓縮，根據(jù)這 19 種值的頻率分配給它們可變碼長(zhǎng)的編碼，不會(huì)造成浪費(fèi)，由于涉及到一些其他情況，對(duì)碼表的再編碼壓縮在后面還會(huì)詳細(xì)介紹！

3.2 把原始字節(jié)值和匹配長(zhǎng)度值建在一棵樹上。
　　現(xiàn)在先考慮另一個(gè)問題：如何使解壓時(shí)能區(qū)分當(dāng)前是一個(gè)未匹配的字節(jié)，還是一個(gè)匹配？未匹配字節(jié)值和匹配長(zhǎng)度、匹配距離是三棵不同的 huffman 樹，它們的編碼互相不符合前綴編碼的要求，部分節(jié)點(diǎn)甚至可能編碼相同，解壓時(shí)如何區(qū)分？
　　第一種方法是用標(biāo)志位。輸出壓縮結(jié)果時(shí)，除了輸出每一段的碼表、重新編碼后的數(shù)據(jù)流，還要保存對(duì)應(yīng)于這一段數(shù)據(jù)的標(biāo)志位流，流中的每一位 0 或 1 表示當(dāng)前是一個(gè)未匹配的字節(jié)，還是一個(gè)匹配。
　　第二種方法是給原始字節(jié)值和匹配長(zhǎng)度值不同的編碼，并符合前綴編碼的要求。最好的做法是把它們建在一棵樹上，以確保它們符合前綴編碼的要求，并由它們的頻率來(lái)確定各自的碼長(zhǎng)。
　　第一種方法相當(dāng)于原始字節(jié)值和匹配長(zhǎng)度值的編碼都增長(zhǎng)一位。
　　第二種方法中這兩套節(jié)點(diǎn)的碼長(zhǎng)變化要根據(jù)具體節(jié)點(diǎn)各自的頻率而定。
　　經(jīng)過分析，第二種方法更好，因?yàn)榈谝环N方法可以看作是第二種方法的變種，相當(dāng)于簡(jiǎn)單地在兩棵 huffman 樹的根節(jié)點(diǎn)上再加一個(gè)父節(jié)點(diǎn)，這樣顯然是不能保證最佳的結(jié)果的。

3.3 把匹配長(zhǎng)度、匹配距離變?yōu)殚L(zhǎng)度范圍、距離范圍，減少節(jié)點(diǎn)。
　　經(jīng)過上面對(duì)保存碼表的方法的改進(jìn)后，現(xiàn)在碼表還有多大？
　　 由于有了上面介紹的去重復(fù)機(jī)制，碼表的實(shí)際大小和節(jié)點(diǎn)的重復(fù)情況有關(guān)，如果有很多連續(xù) 3 個(gè)以上節(jié)點(diǎn)的碼長(zhǎng)相等的情況出現(xiàn)，或有很多連續(xù) 3 個(gè)以上的無(wú)效節(jié)點(diǎn)的情況出現(xiàn)，碼表可能是很小的，但作為通用的無(wú)損壓縮算法，必須考慮重復(fù)不多的情況。“匹配距離”是碼表中最主要的部分，我們來(lái)分析一下 它的重復(fù)情況，“匹配距離”共有 32k 個(gè)取值，如果一個(gè)段落不到 32k，“匹配距離”的有效節(jié)點(diǎn)數(shù)當(dāng)然是不可能到 32k 的，思考一下，可以知道，它的有效節(jié)點(diǎn)數(shù)和這樣幾個(gè)因素有關(guān)：一段有多長(zhǎng)，段落中匹配數(shù)和未匹配數(shù)的比例，決定了它有多少個(gè)值，再加上這些值的重復(fù)性，決 定了它有多少個(gè)有效節(jié)點(diǎn)。再分析一下這些值的重復(fù)性：不同于原始字節(jié)和“匹配長(zhǎng)度”都只有 256 個(gè)取值，它有 32k 個(gè)取值，相同的匹配有相同的匹配長(zhǎng)度但不一定有相同的匹配距離，所以它的去值范圍廣，重復(fù)率低，有效節(jié)點(diǎn)多。雖然實(shí)際的情況無(wú)法預(yù)測(cè)，但我們可以做一些 “大致合理”的假設(shè)，以便對(duì)碼表的大小有一個(gè)基本的概念，假如短語(yǔ)式壓縮的輸出段落的大小為 90k 字節(jié)，其中未匹配字節(jié)數(shù)和匹配數(shù)的比例為 3 : 1，每個(gè)未匹配字節(jié)占 8 位；每個(gè)匹配中，長(zhǎng)度占 8 位，距離占 15 位，共 23 位，約為未匹配字節(jié)的 3 倍，所以匹配占了 90k 字節(jié)中的約 45k 字節(jié)，匹配數(shù)約 15k 個(gè)，也就是說有 15k 個(gè)距離值，假如距離值的平均節(jié)點(diǎn)頻率為 3，那么去掉重復(fù)后有 5k 個(gè)有效距離值節(jié)點(diǎn)，保存到碼表時(shí)每個(gè)碼長(zhǎng)需要 5 位，保存 5k 個(gè)碼長(zhǎng)需要 5k * 5 / 8 約 3k 字節(jié)，算上無(wú)效節(jié)點(diǎn)、碼長(zhǎng)的重復(fù)的因素，原始字節(jié)值、匹配長(zhǎng)度的保存，最終碼表約 5k 字節(jié)，為 90k 的 18 分之一。當(dāng)段落減小時(shí)，有效節(jié)點(diǎn)趨于稀疏，無(wú)效節(jié)點(diǎn)容易連成片，去重復(fù)機(jī)制能發(fā)揮更大的作用；當(dāng)段落增大時(shí)，無(wú)效節(jié)點(diǎn)密度減小，可能無(wú)法大片連接，去重復(fù) 機(jī)制的效用降低，碼表的比例可能會(huì)增大。一旦“匹配距離”需要保存的碼長(zhǎng)數(shù)達(dá)到了 32k個(gè)，碼表達(dá)到最大，之后段落再增大也不會(huì)增大碼表，于是碼表的比例又會(huì)逐漸下降。當(dāng)然段落通常不會(huì)達(dá)到這么大，使得“匹配距離”需要保存的碼長(zhǎng)數(shù)能 有機(jī)會(huì)達(dá)到 32k。
　　gzip 以犧牲壓縮率的代價(jià)來(lái)?yè)Q取碼表的進(jìn)一步的大幅度減小。我們先描述一下它的具體做法，再來(lái)分析其利弊。
　 　gzip 把匹配長(zhǎng)度劃成 29 個(gè)范圍，把匹配距離劃成 30 個(gè)范圍，根據(jù)每個(gè)范圍中節(jié)點(diǎn)的總頻率，為 29 個(gè)長(zhǎng)度范圍加 258 個(gè)字節(jié)值建 huffman 樹：l_tree，為 30 個(gè)距離范圍建 huffman 樹：d_tree。輸出一個(gè)值時(shí)先輸出該值所在范圍的編碼，再輸出附加碼，即它是該范圍中的第幾個(gè)值。這樣碼表中只需保存范圍的碼長(zhǎng)。范圍的大小都是 2 的乘方，所以范圍大小和附加碼的位長(zhǎng)是互相決定的。
29 個(gè)長(zhǎng)度范圍的附加碼位長(zhǎng)是：
{0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0};
30 個(gè)距離范圍的附加碼位長(zhǎng)是：
{0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13};
可以看出：范圍的劃分是從小到大的。為什么不平均劃分呢？
　 　如果仍以單個(gè)節(jié)點(diǎn)的角度來(lái)看，被分到同一范圍的節(jié)點(diǎn)相當(dāng)于被賦予了相同的碼長(zhǎng)：范圍編碼的碼長(zhǎng)加附加碼的碼長(zhǎng)。若頻率差別很大的節(jié)點(diǎn)因劃分入同一個(gè)范圍 而擁有相同的碼長(zhǎng)，就不符合 huffman 編碼的初衷，會(huì)對(duì)壓縮率產(chǎn)生不良影響。因此要求劃分后，范圍里的節(jié)點(diǎn)頻率相近，以盡量降低同一個(gè)范圍里不同節(jié)點(diǎn)間的相互影響。
　　“匹配長(zhǎng)度”從 短到長(zhǎng)，頻率會(huì)逐漸衰減，而且衰減的幅度有從大到小的特點(diǎn)，這個(gè)特點(diǎn)是在大多數(shù)原始文件中“自然存在”的。比如在 google 上搜索，2 個(gè)字的短語(yǔ)和 22 個(gè)字的短語(yǔ)，搜到的結(jié)果數(shù)差別巨大，200 個(gè)字和 220 個(gè)字，搜到的結(jié)果數(shù)差別就沒有那么大。頻率大致上單向地逐步變化，所以劃分范圍后，范圍內(nèi)節(jié)點(diǎn)的頻率較接近；變化速度由大到小，所以范圍的劃分應(yīng)該從小到 大。
　　“匹配距離”也有類似的特點(diǎn)，對(duì)大多數(shù)文件來(lái)說，匹配發(fā)生在 1k 以內(nèi)比發(fā)生在 5k 左右的可能性要大得多，但發(fā)生在 28k 處附近的可能性和發(fā)生在 32k 處附近的可能性的差別就沒那么明顯。所以范圍劃分也應(yīng)該是從小到大。
　 　“未匹配的原始字節(jié)”不具有頻率衰減或遞增的單向變化的規(guī)律，它們的頻率分布往往是參差不齊、難以預(yù)測(cè)的，不可能用預(yù)先設(shè)定的范圍表對(duì)它們進(jìn)行大致合理 的劃分，就像“匹配長(zhǎng)度”和“匹配距離”那樣。雖然也可以通過計(jì)算分析，對(duì)它們進(jìn)行不設(shè)定范圍數(shù)量和大小的劃分，以求每個(gè)范圍中的各節(jié)點(diǎn)頻率大致相近，但 1) “匹配距離”的劃分已經(jīng)大幅度地縮小了碼表的大小；2) 由于不具有頻率單向變化的趨向，要強(qiáng)行劃出節(jié)點(diǎn)頻率相近并且節(jié)點(diǎn)數(shù)是 2 的乘方的范圍太勉強(qiáng)，難度也大；3) 未匹配的字節(jié)數(shù)一般要大于“匹配數(shù)”（注意：不是“匹配字節(jié)數(shù)”），強(qiáng)行劃分造成的不良反應(yīng)較大。所以 gzip 保留了這套節(jié)點(diǎn)，沒去拆分。
　　長(zhǎng)度范圍的最后一個(gè)附加碼位長(zhǎng)是 0，是因?yàn)殚L(zhǎng)度大于 258 的匹配都被截?cái)嗟?258，所以 258 的頻率可能會(huì)高出前面的節(jié)點(diǎn)，單獨(dú)劃為一個(gè)范圍。
　　如果一個(gè)范圍里的節(jié)點(diǎn)頻率相同，節(jié)點(diǎn)數(shù)是 2 的乘方，且沒有無(wú)效節(jié)點(diǎn)，那么這個(gè)范圍可以看作 huffman 樹中的一棵子樹，范圍的編碼可以看作這棵子樹的根的編碼，這樣的劃分是不會(huì)影響壓縮率的。
　　對(duì)壓縮率的損害來(lái)自頻率不一致，以及無(wú)效節(jié)點(diǎn)的存在。范圍里的有效節(jié)點(diǎn)如果沒有過半，“附加碼”的位數(shù)就至少有一位浪費(fèi)了，也就是說，范圍里所有有效節(jié)點(diǎn)的碼長(zhǎng)無(wú)端增長(zhǎng)了一位，如果有效節(jié)點(diǎn)沒有過 1/4，至少就有 2 位附加碼浪費(fèi)。
　　劃分范圍的收益是使碼表減小到不足 0.2k，加上后面會(huì)介紹的對(duì)碼表的第二次壓縮，碼表的最終大小是微不足道的。
　 　現(xiàn)在我們來(lái)近似地估計(jì)一下劃分范圍在“一般情況”下對(duì)壓縮率的損害的情況，以便有一個(gè)大致的概念，仍舉前面的例子：段落大小為 90k，設(shè)其中未匹配字節(jié)數(shù)和匹配數(shù)的比例為 3:1，未匹配字節(jié)有 45k 個(gè)，匹配距離值和匹配長(zhǎng)度值各 15k 個(gè)，有效距離值節(jié)點(diǎn)為 5k個(gè)（節(jié)點(diǎn)平均頻率為 3），無(wú)效距離值節(jié)點(diǎn)為 32k - 5k = 27k 個(gè)，有效距離值節(jié)點(diǎn)的平均密度為 5/32，不到 1/6。范圍的劃分是前小后大，有效節(jié)點(diǎn)頻率是前大后小，無(wú)效節(jié)點(diǎn)是前少后多。距離值有 15k 個(gè)，設(shè)前面有效節(jié)點(diǎn)頻率高、密度較大的部分占一半，約 7k 個(gè)值，這個(gè)部分中無(wú)效節(jié)點(diǎn)帶來(lái)的損害較小，而且范圍劃分細(xì)，節(jié)點(diǎn)間頻率不一致帶來(lái)的損害也小，姑且不去計(jì)算。后面的范圍劃分大、有效節(jié)點(diǎn)密度小的部分損害 較大，這個(gè)部分占了約 7k 個(gè)值，由于前面的部分有效節(jié)點(diǎn)密度大，所以假設(shè)這個(gè)部分有效節(jié)點(diǎn)密度為 1/8（也就是說，約一半的匹配發(fā)生在 1k 距離以內(nèi)，且 1k 以內(nèi)無(wú)效節(jié)點(diǎn)很少，那么 4k / 31k 約等于 1/8），附加碼浪費(fèi)了 3 位，7k 個(gè)值浪費(fèi) 3 位，共浪費(fèi)了 21k bit 約等于 3k 字節(jié)。
　　再看頻率不一致帶來(lái)的損害：huffman 編碼如果要達(dá)到 50% 的壓縮率，需要節(jié)點(diǎn)間頻率的差異達(dá)到幾百倍。讀者可以虛擬一些節(jié)點(diǎn)頻率，試著建一下 huffman 樹，會(huì)發(fā)現(xiàn)當(dāng)節(jié)點(diǎn)頻率差異在幾十倍甚至只有幾倍的時(shí)候，壓縮率其實(shí)微乎其微。經(jīng)過上面這樣合理地劃分范圍，范圍內(nèi)的節(jié)點(diǎn)頻率差異一般不會(huì)那么大，所以我們 假設(shè)頻率不一致造成的損害為 1k － 2k。
　　匹配長(zhǎng)度值的取值范圍只有 258 個(gè)，而且匹配長(zhǎng)度可能很少會(huì)超過 20 字節(jié)，而前 20 字節(jié)的范圍劃分是很細(xì)的，所以無(wú)效節(jié)點(diǎn)的損害和頻率不一致的損害都較小。
　　這樣，在這個(gè)例子中，劃分范圍帶來(lái)的損害約在 5k － 6k，和不劃分范圍時(shí)碼表的大小非常相似，至少也是在一個(gè)數(shù)量級(jí)上。
　 　再來(lái)看看損害比例變化的趨勢(shì)：當(dāng)段落很小時(shí)，范圍中的有效值稀疏，損害比例會(huì)加大。而不劃分范圍時(shí)，碼表的去重復(fù)機(jī)制會(huì)有更大作用，無(wú)效節(jié)點(diǎn)連成片，損 害比例減小。反之，段落增大，范圍里有效節(jié)點(diǎn)密度大，損害比例降低，而不劃分范圍時(shí)，無(wú)效節(jié)點(diǎn)可能無(wú)法大片連接，去重復(fù)機(jī)制的效用降低，損害比例增大。
　　由于劃分范圍能使 huffman 樹的節(jié)點(diǎn)從最多 32k 減到不足 320 個(gè)，從而使壓縮速度顯著改善。綜上所述，段落小（比如不到 10k），不宜劃分范圍，否則劃分范圍是有益的。

3.4 對(duì)碼表進(jìn)行第二次壓縮。
　　目前為止，碼表中只需要保存各個(gè)節(jié)點(diǎn)經(jīng)過 huffman 編碼后的新編碼的碼長(zhǎng)。共兩棵樹，l_tree: 256 個(gè)原始字節(jié)值加 29 個(gè)長(zhǎng)度范圍值加 1 個(gè)段落中止符，共 286 個(gè)節(jié)點(diǎn)，段落中止符用來(lái)在解壓時(shí)標(biāo)示一個(gè)段落的終結(jié)。d_tree: 30 個(gè)距離范圍值。也就是說，共需要保存 286 + 30 = 316 個(gè)編碼的碼長(zhǎng)。gzip 限制 huffman 樹的最大層數(shù)為 15，這樣，碼長(zhǎng)就有 0 － 15 共 16 種值，再加上前面介紹過的去重復(fù)機(jī)制使用的 3 種特殊值，共 19 種值，如果就這樣保存碼表的話，每個(gè)碼長(zhǎng)都需要 5 位，才能表示 19 種值。我們觀察一下，316 個(gè)碼長(zhǎng)，一共只有 19 種值，碼長(zhǎng)值的重復(fù)是必然的，而且由于 huffman 樹上每層的節(jié)點(diǎn)數(shù)不同，所以各個(gè)碼長(zhǎng)值的頻率也不一樣。所以還可以為這 19 種值再建 huffman 樹，進(jìn)行第二次編碼。這棵樹只有 19 個(gè)節(jié)點(diǎn)，限制它的層數(shù)為 0 － 7，可以用 3 個(gè) bit 表示這 19 個(gè)節(jié)點(diǎn)的“長(zhǎng)度”。這樣，用新的“碼長(zhǎng)的編碼”來(lái)保存 316 個(gè)碼長(zhǎng)，另需額外保存 3 * 19 = 57 bit，就可以解壓出這 19 個(gè)“碼長(zhǎng)的編碼”。（至于這 57 bit，就沒有必要再作第 3 次編碼了）


4. 解決了碼表的問題，現(xiàn)在再回過頭來(lái)看靜態(tài)編碼。
　　靜態(tài)編碼是 gzip 預(yù)先設(shè)定的編碼方案，它的碼表是固定的。
　 　該如何合理設(shè)計(jì)這套編碼？作為 huffman 編碼的補(bǔ)助，它的耗時(shí)應(yīng)盡量少，前面說過，lz77 輸出一個(gè)分段之前，要比較 huffman 編碼和靜態(tài)編碼的壓縮結(jié)果，為了直接利用 lz77 輸出時(shí)做的匹配長(zhǎng)度范圍、匹配距離范圍的頻率的統(tǒng)計(jì)，靜態(tài)編碼采用了同樣的范圍－附加碼的方案，這樣可以快速得到靜態(tài)編碼的壓縮結(jié)果大小。
　　靜 態(tài)編碼的碼長(zhǎng)的分配是這樣的：29 個(gè)長(zhǎng)度范圍中前 24 個(gè)范圍的碼長(zhǎng)為 7，后 5 個(gè)范圍的碼長(zhǎng)為8。原始字節(jié)值中 0 － 143 的碼長(zhǎng)為 8，144 － 255 的碼長(zhǎng)為 9。而 30 個(gè)距離范圍的碼長(zhǎng)為 5。根據(jù)這些預(yù)先設(shè)定的碼長(zhǎng)建立靜態(tài)的 l_tree 和 d_tree，編碼也就產(chǎn)生了。結(jié)合前面提到的附加碼位數(shù)的定義：
29 個(gè)長(zhǎng)度范圍的附加碼位長(zhǎng)：
{0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0};
30 個(gè)距離范圍的附加碼位長(zhǎng)：
{0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13};
讀 者可以知道每一個(gè)值的實(shí)際碼長(zhǎng)。長(zhǎng)度范圍值和原始字節(jié)值建在一棵樹上，節(jié)點(diǎn)多所以碼長(zhǎng)較長(zhǎng)，30 個(gè)距離范圍值只需要 5 位二進(jìn)制數(shù)表示。短匹配的長(zhǎng)度范圍值位長(zhǎng)較短，字節(jié)值 0 － 143 的位長(zhǎng)中等，其他字節(jié)值和長(zhǎng)匹配的長(zhǎng)度范圍值較長(zhǎng)。這樣的分配反映了 gzip 作者對(duì)“大多數(shù)”文件中各種值的頻率的粗略估計(jì)。作為一個(gè)通用的壓縮算法，無(wú)法預(yù)先知道一個(gè)文件的實(shí)際情況，不可能做精確的估計(jì)。
　　進(jìn)一步的思 考：靜態(tài)編碼有必要嗎？靜態(tài)編碼采用了和 huffman 編碼相同的范圍－附加碼的方案，在碼長(zhǎng)的分配上不可能超過 huffman 編碼，如果能“獲勝”，那就是勝在不需要保存碼表上，而前面分析過，碼表是很小的，對(duì)壓縮率沒有多大影響，所以 gzip 設(shè)計(jì)的這個(gè)靜態(tài)編碼方案應(yīng)該是可有可無(wú)的。

5. 關(guān)于堆排序算法。
　　似乎已經(jīng)解決了所有的難題，但是對(duì)于沒有學(xué)過數(shù)據(jù)結(jié)構(gòu)的讀者，仍然有一個(gè)會(huì)對(duì)程序效率產(chǎn)生影響的問題需要關(guān)注，那就是“排序”。
　　已經(jīng)講過，huffman 算法就是從一個(gè)節(jié)點(diǎn)序列中，不斷找出兩個(gè)最小的節(jié)點(diǎn)，為它們建一個(gè)父節(jié)點(diǎn)，值為這兩個(gè)節(jié)點(diǎn)之和，然后從節(jié)點(diǎn)序列中去除這兩個(gè)節(jié)點(diǎn)，加入它們的父節(jié)點(diǎn)到序列中，不斷重復(fù)這樣的步驟，直到節(jié)點(diǎn)序列中只剩下一個(gè)節(jié)點(diǎn)。如何快速地找出最小的元素呢？
　 　在普通的線性羅列的數(shù)據(jù)結(jié)構(gòu)中，從 N 個(gè)元素中找出最小的元素的時(shí)間和 N 成正比，如果數(shù)據(jù)以我們所要介紹的“堆”的結(jié)構(gòu)存儲(chǔ)，時(shí)間和 lg N 成正比（注：lg 以 2 為底數(shù)，如 lg 256 = 8，lg 1024 = 10 ...）。 集合中的元素越多，堆排序算法的優(yōu)勢(shì)越突出，而且堆排序非常適合于在數(shù)據(jù)序列中不斷地取走最小的元素并加入新的元素。

5.1 什么是堆？
　　堆首先是一棵“完全二叉樹”，即所有的葉子節(jié)點(diǎn)都在樹的最低二層，最低一層的節(jié)點(diǎn)依次靠左排列的二叉樹。如圖：

　　　　　　　　　　　　　　　　　　　　　　　完全二叉樹
　　　　　　　　　　　　　　　　　　　　　　　　　｜
　　　　　　　　　　　　　　＋－－－－－－－－－－○－－－－－－－－－－＋
　　　　　　　　　　　　　　｜　　　　　　　　　　　　　　　　　　　　　｜
　　　　　　＋－－－－－－－○－－－－－－＋　　　　　　　　　　＋－－－○－－－＋
　　　　　　｜　　　　　　　　　　　　　　｜　　　　　　　　　　｜　　　　　　　｜
　　＋－－－○－－－＋　　　　　　＋－－－○－－－＋　　　　＋－○－＋　　　＋－○－＋
　　｜　　　　　　　｜　　　　　　｜　　　　　　　｜　　　　｜　　　｜　　　｜　　　｜
＋－○－＋　　　＋－○－＋　　＋－○－＋　　　＋－○－＋　　■　　　■　　　■　　　■
｜　　　｜　　　｜　　　｜　　｜　　　｜　　　｜　　　｜
■　　　■　　　■　　　■　　■　　　■　　　■　　　■


　　堆分大根堆和小根堆，大根堆的所有子節(jié)點(diǎn)都小于它的父節(jié)點(diǎn)，小根堆的所有子節(jié)點(diǎn)都大于它的父節(jié)點(diǎn)。下面就是一個(gè)小根堆：

　　　　　　　　　　　　　　　　　　　　　　　　　小根堆
　　　　　　　　　　　　　　　　　　　　　　　　　　｜
　　　　　　　　　　　　　　＋－－－－－－－－－－－２－－－－－－－－－－＋
　　　　　　　　　　　　　　｜　　　　　　　　　　　　　　　　　　　　　　｜
　　　　　　＋－－－－－－－３－－－－－－＋　　　　　　　　　　＋－－－－８－－－＋
　　　　　　｜　　　　　　　　　　　　　　｜　　　　　　　　　　｜　　　　　　　　｜
　　＋－－－６－－－＋　　　　　　＋－－－４－－－＋　　　　＋－１５－＋　　　＋－１８－＋
　　｜　　　　　　　｜　　　　　　｜　　　　　　　｜　　　　｜　　　　｜　　　｜　　　　｜
＋－８－＋　　　＋－９－＋　　＋－５－＋　　　＋－５－＋　　１６　　２０　　　１９　　　２０
｜　　　｜　　　｜　　　｜　　｜　　　｜　　　｜　　　｜
９　　　９　　１１　　１３　　６　　　８　　　６　　　６

5.2 堆如何在內(nèi)存中存儲(chǔ)？
　　堆存放在一個(gè)數(shù)組中，存放的順序是：從根開始，依次存放每一層從左至右的節(jié)點(diǎn)。
5.3 如何尋找任意節(jié)點(diǎn)的子節(jié)點(diǎn)和父節(jié)點(diǎn)？
　　數(shù)組中第 k 個(gè)元素，它的左子節(jié)點(diǎn)是第 2k 個(gè)元素，右子節(jié)點(diǎn)是第 2k + 1 個(gè)元素。它的父節(jié)點(diǎn)是┖ k/2 ┚（注：┖ X ┚表示小于等于 X 的最大整數(shù)）。
5.4 如何建立堆？
　 　先把 n 個(gè)元素依次放入數(shù)組中，令變量 k = ┖ n/2 ┚，這時(shí)第 k 個(gè)元素是最后一個(gè)元素的父節(jié)點(diǎn)，從第 k 個(gè)元素的兩個(gè)子節(jié)點(diǎn)中找出較小的一個(gè)與 k 元素比較，如果小于 k 元素，就和 k 元素交換一下位置，換位后的原先的 k 元素再和新的子節(jié)點(diǎn)比較（如果有子節(jié)點(diǎn)的話），直到它不再小于新的子節(jié)點(diǎn)或沒有子節(jié)點(diǎn)。令 k = k - 1。再重復(fù)上面的做法直到 k < 1，一個(gè)堆就建成了。
5.5 如何從堆中找出第二個(gè)最小的元素？
　　把堆中第一個(gè)元素（最小的元素）存放到其他地方，把第 n 個(gè)元素（最后一個(gè)）放到第一個(gè)的位置，再用前面的方法和下層節(jié)點(diǎn)交換直到它放到合適的位置，這時(shí)數(shù)組仍然是一個(gè)堆，第一個(gè)元素是最小的節(jié)點(diǎn)，數(shù)組的最后一個(gè)有效節(jié)點(diǎn)是第 n - 1 個(gè)元素。
　　花費(fèi)的時(shí)間和交換的次數(shù)成正比，最大的可能的交換次數(shù)是： 堆的層數(shù) - 1 =┏ lg (元素?cái)?shù) + 1) ┒- 1（注：┏ X ┒表示大于等于 X 的最小整數(shù)）。
　　現(xiàn)在可以看到，堆之所以采用完全二叉樹的形式，是為了樹的層數(shù)盡可能少。
　　而抽出最后一個(gè)元素放到樹根，而不是抽出第二層的元素，是為了維持完全二叉樹的結(jié)構(gòu)！
5.6 如何加入新的元素到堆中？
　　把第一個(gè)元素存放到其他地方，把新的元素放到第一個(gè)的位置，再用前面的方法和下層節(jié)點(diǎn)交換，直到它被放到合適的位置，此時(shí)數(shù)組中仍然是一個(gè)堆。

6. 建 huffman 樹和編碼的算法：
　　如果現(xiàn)在有 n 個(gè)待編碼的節(jié)點(diǎn)，按照原始數(shù)值從小到大存放在數(shù)組 tree[n] 中，那么，將要建立的 huffman 樹總共會(huì)有 2n -1 節(jié)點(diǎn)，包括葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)。申請(qǐng)一塊內(nèi)存，大小是能放下 huffman 樹的所有節(jié)點(diǎn)，先把 n 個(gè)待編碼節(jié)點(diǎn)放入這塊內(nèi)存的左端，然后用“堆排序”算法先把它們建成一個(gè)堆。
　　然后不斷用“堆排序”算法取出頻率最小 的節(jié)點(diǎn)，把它們從右到左、從小到大排放在內(nèi)存塊的右端，每當(dāng)取出兩個(gè)節(jié)點(diǎn)，給它們生成一個(gè)父節(jié)點(diǎn)，頻率等于它們之和，加入堆中。這樣直到堆中只剩下一個(gè)根 節(jié)點(diǎn)，這時(shí)，內(nèi)存中從左到右存儲(chǔ)的是頻率從大到小的所有節(jié)點(diǎn)，一棵 huffman 樹其實(shí)也就建成了，層數(shù)小的節(jié)點(diǎn)在前，層數(shù)大的節(jié)點(diǎn)在后，每一層的節(jié)點(diǎn)又是按頻率從大到小依次排列。
　　申請(qǐng)兩個(gè)數(shù)組：bl_count[]， bl_base[]。置根節(jié)點(diǎn)的碼長(zhǎng)為 0，從左至右，所有節(jié)點(diǎn)的碼長(zhǎng)(len)為它的父節(jié)點(diǎn)的碼長(zhǎng) + 1，如果是葉子節(jié)點(diǎn)，bl_count[len]++，得到了每一層上的葉子節(jié)點(diǎn)數(shù)目。令變量 code = 0，然后根據(jù) bl_count[] 生成 bl_base[]：碼長(zhǎng) len 從 1 開始遞增，bl_base[len] = code = (code + bl_count[len - 1]) << 1，得到了每一層上第一個(gè)葉子節(jié)點(diǎn)的編碼。
　　現(xiàn)在所有待編碼節(jié)點(diǎn)都被賦予了碼長(zhǎng)，遍歷待編碼節(jié)點(diǎn)，根據(jù)它們的碼長(zhǎng)得到它們的編碼：序號(hào) n 遞增，tree[n].code = bl_base[ tree[n].len ] ++。
　　注意：我們前面討論碼表的時(shí)候說過，gzip 對(duì) huffman 編碼進(jìn)行了改進(jìn)，只需要得到每一個(gè)葉子節(jié)點(diǎn)（待編碼節(jié)點(diǎn)）的碼長(zhǎng)，就可以進(jìn)行編碼，而不需要關(guān)心它的父節(jié)點(diǎn)的編碼是什么。而保存碼表時(shí)，只需要保存碼長(zhǎng)。

動(dòng)態(tài) huffman 壓縮和解壓的整個(gè)流程：
壓縮：
　　lz77 的壓縮過程中輸出未匹配的單雙字節(jié)，和匹配，并統(tǒng)計(jì)各字節(jié)值和匹配長(zhǎng)度范圍、匹配距離范圍的頻率，根據(jù)這些頻率建立兩棵 huffman 樹：ltree、dtree，得到這兩棵樹上所有節(jié)點(diǎn)的長(zhǎng)度和編碼。
　　統(tǒng)計(jì)這兩棵樹節(jié)點(diǎn)長(zhǎng)度的使用頻率，對(duì)各節(jié)點(diǎn)長(zhǎng)度建立 huffman 樹：bl_tree，得到 bl_tree 的長(zhǎng)度和編碼。
　　存儲(chǔ) bl_tree 的節(jié)點(diǎn)長(zhǎng)度數(shù)組。
　　再用 bl_tree 的編碼存儲(chǔ) ltree、dtree 的節(jié)點(diǎn)長(zhǎng)度數(shù)組。
　　再用 ltree 的編碼存儲(chǔ)各字節(jié)值和匹配長(zhǎng)度范圍（及附加碼）的流；用 dtree 的編碼存儲(chǔ)匹配距離范圍（及附加碼）的流。
解壓：
　　先根據(jù) bl_tree 的節(jié)點(diǎn)長(zhǎng)度數(shù)組得到 bl_tree 的編碼。
　　再用這些編碼得到 ltree、dtree 的節(jié)點(diǎn)長(zhǎng)度數(shù)組，進(jìn)而得到 ltree、dtree 的編碼。
　　再根據(jù) ltree、dtree 的編碼及附加碼的定義，得到 lz77 的輸出的原始結(jié)果：各字節(jié)值和匹配長(zhǎng)度的流，匹配距離的流。




后記：
　　寫作本文花費(fèi)了超過一年的業(yè)余時(shí)間，其實(shí)看懂 gzip 源碼只用了一個(gè)半月的業(yè)余時(shí)間，等真正開始寫這篇文章的時(shí)候，發(fā)現(xiàn)深入分析無(wú)損壓縮算法要投入的心力會(huì)遠(yuǎn)超過我原來(lái)的想象，不是光靠“毅然決然的態(tài)度”和“拼搏精神”就可以完成的。只有耐心地去付出。
　　經(jīng)過了一年多的時(shí)間，終于有了現(xiàn)在這樣質(zhì)量的這篇文章。這期間，我的工作已經(jīng)從應(yīng)用工程師轉(zhuǎn)變到了研究員，應(yīng)該說，寫作這篇文章對(duì)促成我把今后的工作轉(zhuǎn)變?yōu)楦阊芯渴怯杏绊懙摹Ｋ赃@篇文章對(duì)我自己的人生道路當(dāng)然是有重要的意義，我也希望它會(huì)促成讀者投身研究的決心。
　　巴甫洛夫說：“科學(xué)研究需要的是偉大的熱情和艱苦的勞作”，從看到這句話起，我就一直很喜歡它，常常會(huì)想起這句話。希望這篇文章能使讀者聯(lián)想到“長(zhǎng)久的熱情和耐心的勞作”，并在生活和工作中貫徹這種精神。
　　一篇文章發(fā)布以后，它的全部?jī)r(jià)值就在于讀者的閱讀，感謝讀者諸君。