奇妙的二叉樹：Huffman的貢獻(xiàn)
關(guān)鍵字 Huffman
提起 Huffman 這個名字，程序員們至少會聯(lián)想到二叉樹和二進(jìn)制編碼。的確，我們總以 Huffman 編碼來概括 D.A.Huffman 個人對計(jì)算機(jī)領(lǐng)域特別是數(shù)據(jù)壓縮領(lǐng)域的杰出貢獻(xiàn)。我們知道，壓縮 = 模型 + 編碼，作為一種壓縮方法，我們必須全面考慮其模型和編碼兩個模塊的功效；但同時，模型和編碼兩個模塊又相互具有獨(dú)立性。舉例來說，一個使用 Huffman 編碼方法的程序，完全可以采用不同的模型來統(tǒng)計(jì)字符在信息中出現(xiàn)的概率。因此，我們這一章將首先圍繞 Huffman 先生最為重要的貢獻(xiàn) —— Huffman 編碼展開討論，隨后，我們再具體介紹可以和 Huffman 聯(lián)合使用的概率模型。
為什么是二叉樹
為什么壓縮領(lǐng)域中的編碼方法總和二叉樹聯(lián)系在一起呢？原因非常簡單，回憶一下我們介紹過的“前綴編碼”：為了使用不固定的碼長表示單個字符，編碼必須符合“前綴編碼”的要求，即較短的編碼決不能是較長編碼的前綴。要構(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，則一個字符的編碼就是從根走到該字符所在樹葉的路徑。正因?yàn)樽址荒艹霈F(xiàn)在樹葉上，任何一個字符的路徑都不會是另一字符路徑的前綴路徑，符合要求的前綴編碼也就構(gòu)造成功了：
a - 00 b - 010 c - 011 d - 10 e - 11
Shannon-Fano 編碼
進(jìn)入 Huffman 先生構(gòu)造的神奇二叉樹之前，我們先來看一下它的前身，由 Claude Shannon 和 R.M.Fano 兩人提出的 Shannon-Fano 編碼。
討論之前，我們假定要編碼字符的出現(xiàn)概率已經(jīng)由某一模型統(tǒng)計(jì)出來，例如，對下面這串出現(xiàn)了五種字符的信息( 40 個字符長 ):
cabcedeacacdeddaaabaababaaabbacdebaceada
五種字符的出現(xiàn)次數(shù)分別：a - 16，b - 7，c - 6，d - 6，e - 5。
Shannon-Fano 編碼的核心仍然是構(gòu)造二叉樹，構(gòu)造的方式非常簡單：
1) 將給定符號按照其頻率從大到小排序。對上面的例子，應(yīng)該得到：
a - 16
b - 7
c - 6
d - 6
e - 5
2) 將序列分成上下兩部分，使得上部頻率總和盡可能接近下部頻率總和。我們有：
a - 16
b - 7
-----------------
c - 6
d - 6
e - 5
3) 我們把第二步中劃分出的上部作為二叉樹的左子樹，記 0，下部作為二叉樹的右子樹，記 1。
4) 分別對左右子樹重復(fù) 2 3 兩步，直到所有的符號都成為二叉樹的樹葉為止。現(xiàn)在我們有如下的二叉樹：
根(root)
0 | 1
+------+------+
0 | 1 0 | 1
+-----+-----+ +---+----+
| | | |
a b c |
0 | 1
+-----+-----+
| |
d e
于是我們得到了此信息的編碼表：
a - 00 b - 01 c - 10 d - 110 e - 111
可以將例子中的信息編碼為：
cabcedeacacdeddaaabaababaaabbacdebaceada
10 00 01 10 111 110 111 00 10 00 10 ......
碼長共 91 位。考慮用 ASCII 碼表示上述信息需要 8 * 40 = 240 位，我們確實(shí)實(shí)現(xiàn)了數(shù)據(jù)壓縮。
Huffman 編碼
Huffman 編碼構(gòu)造二叉樹的方法和 Shannon-Fano 正好相反，不是自上而下，而是從樹葉到樹根生成二叉樹。現(xiàn)在，我們?nèi)匀皇褂蒙厦娴睦觼韺W(xué)習(xí) Huffman 編碼方法。
1) 將各個符號及其出現(xiàn)頻率分別作為不同的小二叉樹（目前每棵樹只有根節(jié)點(diǎn)）。
a(16) b(7) c(6) d(6) e(5)
2) 在 1 中得到的樹林里找出頻率值最小的兩棵樹，將他們分別作為左、右子樹連成一棵大一些的二叉樹，該二叉樹的頻率值為兩棵子樹頻率值之和。對上面的例子，我們得到一個新的樹林：
| (11)
a(16) b(7) c(6) +---+---+
| |
d e
3) 對上面得到的樹林重復(fù) 2 的做法，直到所有符號都連入樹中為止。這一步完成后，我們有這樣的二叉樹：
根(root)
0 | 1
+------+----------------+
| 0 | 1
| +---------+-----------+
| 0 | 1 0 | 1
a +-------+------+ +-------+-------+
| | | |
b c d e
由此，我們可以建立和 Shannon-Fano 編碼略微不同的編碼表：
a - 0 b - 100 c - 101 d - 110 e - 111
對例子中信息的編碼為：
cabcedeacacdeddaaabaababaaabbacdebaceada
101 0 100 101 111 110 111 0 101 0 101 ......
碼長共 88 位。這比使用 Shannon-Fano 編碼要更短一點(diǎn)。
讓我們回顧一下熵的知識，使用我們在第二章學(xué)到的計(jì)算方法，上面的例子中，每個字符的熵為：
Ea = - log2(16 / 40) = 1.322
Eb = - log2( 7 / 40) = 2.515
Ec = - log2( 6 / 40) = 2.737
Ed = - log2( 6 / 40) = 2.737
Ee = - log2( 5 / 40) = 3.000
信息的熵為：
E = Ea * 16 + Eb * 7 + Ec * 6 + Ed * 6 + Ee * 5 = 86.601
也就是說，表示該條信息最少需要 86.601 位。我們看到，Shannon-Fano 編碼和 Huffman 編碼都已經(jīng)比較接近該信息的熵值了。同時，我們也看出，無論是 Shannon-Fano 還是 Huffman，都只能用近似的整數(shù)位來表示單個符號，而不是理想的小數(shù)位。我們可以將它們做一個對比：
符號 理想位數(shù) S-F 編碼 Huffman 編碼
( 熵 ) 需要位數(shù) 需要位數(shù)
----------------------------------------------------
a 1.322 2 1
b 2.515 2 3
c 2.737 2 3
d 2.737 3 3
e 3.000 3 3
----------------------------------------------------
總 計(jì) 86。601 91 88
這就是象 Huffman 這樣的整數(shù)位編碼方式無法達(dá)到最理想的壓縮效果的原因。
為 Huffman 編碼選擇模型（附范式 Huffman 編碼）
最簡單，最容易被 Huffman 編碼利用的模型是“靜態(tài)統(tǒng)計(jì)模型”，也就是說在編碼前統(tǒng)計(jì)要編碼的信息中所有字符的出現(xiàn)頻率，讓后根據(jù)統(tǒng)計(jì)出的信息建立編碼樹，進(jìn)行編碼。這種模型的缺點(diǎn)是顯而易見的：首先，對數(shù)據(jù)量較大的信息，靜態(tài)統(tǒng)計(jì)要消耗大量的時間；其次，必須保存統(tǒng)計(jì)出的結(jié)果以便解碼時構(gòu)造相同的編碼樹，或者直接保存編碼樹本身，而且，對于每次靜態(tài)統(tǒng)計(jì)，都有不同的結(jié)果，必須分別予以保存，這要消耗大量的空間（這意味著壓縮效率的下降）；再次，事實(shí)上，即使不將編碼樹計(jì)算在內(nèi)，對通常含有 0 - 255 字符集的計(jì)算機(jī)文件來說，靜態(tài)統(tǒng)計(jì)模型統(tǒng)計(jì)出的頻率是字符在整個文件中的出現(xiàn)頻率，往往反映不出字符在文件中不同局部出現(xiàn)頻率的變化情況，使用這一頻率進(jìn)行壓縮，大多數(shù)情況下得不到太好壓縮效果，文件有時甚至在壓縮后反而增大了。所以，“靜態(tài)統(tǒng)計(jì)模型”一般僅作為復(fù)雜算法的某一部分出現(xiàn)，在信息的某一局部完成壓縮功能。我們很難將其用于獨(dú)立的壓縮系統(tǒng)。
有一種有效的“靜態(tài)統(tǒng)計(jì)模型”的替代方案，如果我們要壓縮的所有信息具有某些共同的特性，也即在分布上存在著共同的特征，比如我們要壓縮的是普通的英文文本，那么，字母 a 或者字母 e 的出現(xiàn)頻率應(yīng)當(dāng)是大致穩(wěn)定的。使用語言學(xué)家事先已經(jīng)建立好的字母頻率表來進(jìn)行壓縮和解壓縮，不但不用保存多份統(tǒng)計(jì)信息，而且一般說來對該類文件有著較好的壓縮效果。這種方案除了適應(yīng)性不太強(qiáng)以外，偶爾還會有一些尷尬的時候。讀一遍下面這段話：
If Youth，throughout all history， had had a champion to stand up for it； to show a doubting world that a child can think；and， possibly， do it practically； you wouldn't constantly run across folks today who claim that "a child don't know anything." - Gadsby by E.V.Wright, 1939.
發(fā)現(xiàn)什么問題了嗎？哦，整段話中竟沒有出現(xiàn)一次英文中出現(xiàn)頻率最高的字母 e ！真讓人驚訝，但沒有辦法，事先擬定的頻率分布總有意外的時候。
對英文或中文文本，有一種比較實(shí)用的靜態(tài)模型：不是把字符而是把英文單詞或中文詞語作為統(tǒng)計(jì)頻率和編碼的單位進(jìn)行壓縮。也就是說，每次編碼的不再是 a b c 這樣的單個符號，而是 the look flower 這樣的單詞。這種壓縮方式可以達(dá)到相當(dāng)不錯的壓縮效果，并被廣泛地用于全文檢索系統(tǒng)。
對基于詞的編碼方式，需要解決幾個技術(shù)難點(diǎn)。首先是分詞的問題，英文單詞可以由詞間空格分隔，但中文怎么辦呢？其實(shí)，有很多中文分詞算法可以解決這個問題，本書就不再詳細(xì)介紹了。王笨笨就曾開發(fā)過一個不錯的分詞模塊，但希望通過收取一定報酬的方式提供該模塊，如有需要，請和王笨笨 E-Mail 聯(lián)系。一旦我們將詞語分離出來，我們就可以對每個詞進(jìn)行頻率統(tǒng)計(jì)，然后建立 Huffman 編碼樹，輸出編碼時，一個編碼將代替一個詞語。但要注意，英文和漢語的單詞數(shù)量都在幾萬到十幾萬左右，也就是說，我們的 Huffman 編碼樹將擁有十幾萬個葉子節(jié)點(diǎn)，這對于一棵樹來說太大太大了，系統(tǒng)將無力承擔(dān)所需要的資源，這怎么辦呢？我們可以暫時拋開樹結(jié)構(gòu)，采用另一種構(gòu)造 Huffman 編碼的方式——范式 Huffman 編碼。
范式 Huffman 編碼(Canonical Huffman Code)的基本思路是：并非只有使用二叉樹建立的前綴編碼才是 Huffman 編碼，只要符合(1)是前綴編碼(2)某一字符編碼長度和使用二叉樹建立的該字符的編碼長度相同這兩個條件的編碼都可以叫做 Huffman 編碼。考慮對下面六個單詞的編碼：
符號 出現(xiàn)次數(shù) 傳統(tǒng) Huffman 編碼 范式 Huffman 編碼
------------------------------------------------------------
單詞1 10 000 000
單詞2 11 001 001
單詞3 12 100 010
單詞4 13 101 011
單詞5 22 01 10
單詞6 23 11 11
注意到范式 Huffman 編碼的獨(dú)特之處了嗎？你無法使用二叉樹來建立這組編碼，但這組編碼確實(shí)能起到和 Huffman 編碼相同的作用。而且，范式 Huffman 編碼具有一個明顯的特點(diǎn)：當(dāng)我們把要編碼的符號按照其頻率從小到大排列時，如果把范式 Huffman 編碼本身作為單詞的話，也呈現(xiàn)出從小到大的字典順序。
構(gòu)造范式 Huffman 編碼的方法大致是：
1) 統(tǒng)計(jì)每個要編碼符號的頻率。
2) 根據(jù)這些頻率信息求出該符號在傳統(tǒng) Huffman 編碼樹中的深度（也就是表示該符號所需要的位數(shù) - 編碼長度）。因?yàn)槲覀冴P(guān)心的僅僅是該符號在樹中的深度，我們完全沒有必要構(gòu)造二叉樹，僅用一個數(shù)組就可以模擬二叉樹的創(chuàng)建過程并得到符號的深度，具體方法這里就不詳述了。
3) 分別統(tǒng)計(jì)從最大編碼長度 maxlength 到 1 的每個長度對應(yīng)了多少個符號。根據(jù)這一信息從 maxlength 個 0 開始以遞增順序?yàn)槊總€符號分配編碼。例如，編碼長度為 5 的符號有 4 個，長度為 3 的有 1 個，長度為 2 的有 3 個，則分配的編碼依次為： 00000 00001 00010 00011 001 01 10 11
4) 編碼輸出壓縮信息，并保存按照頻率順序排列的符號表，然后保存每組同樣長度編碼中的最前一個編碼以及該組中的編碼個數(shù)。
現(xiàn)在完全可以不依賴任何樹結(jié)構(gòu)進(jìn)行高速解壓縮了。而且在整個壓縮、解壓縮過程中需要的空間比傳統(tǒng) Huffman 編碼少得多。
最后要提到的是，Huffman 編碼可以采用自適應(yīng)模型，根據(jù)已經(jīng)編碼的符號頻率決定下一個符號的編碼。這時，我們無需為解壓縮預(yù)先保存任何信息，整個編碼是在壓縮和解壓縮過程中動態(tài)創(chuàng)建的，而且自適應(yīng)編碼由于其符號頻率是根據(jù)信息內(nèi)容的變化動態(tài)得到的，更符合符號的局部分布規(guī)律，因此在壓縮效果上比靜態(tài)模型好許多。但是，采用自適應(yīng)模型必須考慮編碼表的動態(tài)特性，即編碼表必須可以隨時更新以適應(yīng)符號頻率的變化。對于 Huffman 編碼來說，我們很難建立能夠隨時更新的二叉樹，使用范式 Huffman 編碼是個不錯的選擇，但依然存在不少技術(shù)上的難題。幸好，如果愿意的話，我們可以暫時不考慮自適應(yīng)模型的 Huffman 編碼，因?yàn)閷τ谧赃m應(yīng)模型我們還有許多更好的選擇，下面幾章將要談到的算術(shù)編碼、字典編碼等更為適合采用自適應(yīng)模型，我們將在其中深入探討自適應(yīng)模型的各種實(shí)現(xiàn)方法。