什么是熵
數(shù)據(jù)壓縮不僅起源于 40 年代由 Claude Shannon 首創(chuàng)的信息論，而且其基本原理即信息究竟能被壓縮到多小，至今依然遵循信息論中的一條定理，這條定理借用了熱力學(xué)中的名詞“熵”( Entropy )來表示一條信息中真正需要編碼的信息量：
考慮用 0 和 1 組成的二進(jìn)制數(shù)碼為含有 n 個(gè)符號(hào)的某條信息編碼，假設(shè)符號(hào) Fn 在整條信息中重復(fù)出現(xiàn)的概率為 Pn，則該符號(hào)的熵也即表示該符號(hào)所需的位數(shù)位為：
En = - log2( Pn )
整條信息的熵也即表示整條信息所需的位數(shù)為：E = ∑En
舉個(gè)例子，對(duì)下面這條只出現(xiàn)了 a b c 三個(gè)字符的字符串：
aabbaccbaa
字符串長(zhǎng)度為 10，字符 a b c 分別出現(xiàn)了 5 3 2 次，則 a b c 在信息中出現(xiàn)的概率分別為 0.5 0.3 0.2，他們的熵分別為：
Ea = -log2(0.5) = 1
Eb = -log2(0.3) = 1.737
Ec = -log2(0.2) = 2.322
整條信息的熵也即表達(dá)整個(gè)字符串需要的位數(shù)為：
E = Ea * 5 + Eb * 3 + Ec * 2 = 14.855 位
回想一下如果用計(jì)算機(jī)中常用的 ASCII 編碼，表示上面的字符串我們需要整整 80 位呢！現(xiàn)在知道信息為什么能被壓縮而不丟失原有的信息內(nèi)容了吧。簡(jiǎn)單地講，用較少的位數(shù)表示較頻繁出現(xiàn)的符號(hào)，這就是數(shù)據(jù)壓縮的基本準(zhǔn)則。
細(xì)心的讀者馬上會(huì)想到，我們?cè)撛鯓佑?0 1 這樣的二進(jìn)制數(shù)碼表示零點(diǎn)幾個(gè)二進(jìn)制位呢？確實(shí)很困難，但不是沒有辦法。一旦我們找到了準(zhǔn)確表示零點(diǎn)幾個(gè)二進(jìn)制位的方法，我們就有權(quán)利向無損壓縮的極限挑戰(zhàn)了。不要著急，看到第四章就明白了。
模型
從上面的描述，我們明白，要壓縮一條信息，首先要分析清楚信息中每個(gè)符號(hào)出現(xiàn)的概率。不同的壓縮程序通過不同的方法確定符號(hào)的出現(xiàn)概率，對(duì)符號(hào)的概率計(jì)算得越準(zhǔn)確，也就越容易得到好的壓縮效果。在壓縮程序中，用來處理輸入信息，計(jì)算符號(hào)的概率并決定輸出哪個(gè)或哪些代碼的模塊叫做模型。
難道對(duì)信息中字符的出現(xiàn)概率這么難以估計(jì)以至于有各種不同的壓縮模型嗎？對(duì)上面的字符串我們不是很容易就知道每個(gè)字符的概率了嗎？是的是的，不過上面的字符串僅有 10 個(gè)字符長(zhǎng)呀，那只是例子而已?？紤]我們現(xiàn)實(shí)中要壓縮的文件，大多數(shù)可是有幾十 K 甚至幾百 K 長(zhǎng)，幾 M 字節(jié)的文件不是也屢見不鮮嗎？
是的，我們可以預(yù)先掃描文件中的所有字符，統(tǒng)計(jì)出每個(gè)字符出現(xiàn)的概率，這種方法在壓縮術(shù)語里叫做“靜態(tài)統(tǒng)計(jì)模型”。但是，不同的文件中，字符有不同的分布概率，我們要么先花上大量的時(shí)間統(tǒng)計(jì)我們要壓縮的所有文件中的字符概率，要么為每一個(gè)單獨(dú)的文件保存一份概率表以備解壓縮時(shí)需要。糟糕的是，不但掃描文件要消耗大量時(shí)間，而且保存一份概率表也使壓縮后的文件增大了不少。所以，在實(shí)際應(yīng)用中，“靜態(tài)統(tǒng)計(jì)模型”應(yīng)用的很少。
真正的壓縮程序中使用的大多是一種叫“自適應(yīng)模型”的東西。自適應(yīng)模型可以說是一臺(tái)具有學(xué)習(xí)功能的自動(dòng)機(jī)。他在信息被輸入之前對(duì)信息內(nèi)容一無所知并假定每個(gè)字符的出現(xiàn)概率均等，隨著字符不斷被輸入和編碼，他統(tǒng)計(jì)并紀(jì)錄已經(jīng)出現(xiàn)過的字符的概率并將這些概率應(yīng)用于對(duì)后續(xù)字符的編碼。也就是說，自適應(yīng)模型在壓縮開始時(shí)壓縮效果并不理想，但隨著壓縮的進(jìn)行，他會(huì)越來越接近字符概率的準(zhǔn)確值，并達(dá)到理想的壓縮效果。自適應(yīng)模型還可以適應(yīng)輸入信息中字符分布的突然變化，可以適應(yīng)不同的文件中的字符分布而不需要保存概率表。
上面提到的模型可以統(tǒng)稱為“統(tǒng)計(jì)模型”，因?yàn)樗麄兌际腔趯?duì)每個(gè)字符出現(xiàn)次數(shù)的統(tǒng)計(jì)得到字符概率的。另一大類模型叫做“字典模型”。實(shí)際上，當(dāng)我們?cè)谏钪刑岬健肮ば小边@個(gè)詞的時(shí)候，我們都知道其意思是指“中國(guó)工商銀行”，類似的例子還有不少，但共同的前提是我們心中都有一本約定俗成的縮寫字典。字典模型也是如此，他并不直接計(jì)算字符出現(xiàn)的概率，而是使用一本字典，隨著輸入信息的讀入，模型找出輸入信息在字典中匹配的最長(zhǎng)的字符串，然后輸出該字符串在字典中的索引信息。匹配越長(zhǎng)，壓縮效果越好。事實(shí)上，字典模型本質(zhì)上仍然是基于對(duì)字符概率的計(jì)算的，只不過，字典模型使用整個(gè)字符串的匹配代替了對(duì)某一字符重復(fù)次數(shù)的統(tǒng)計(jì)?？梢宰C明，字典模型得到的壓縮效果仍然無法突破熵的極限。
當(dāng)然，對(duì)通用的壓縮程序來說，保存一本大字典所需的空間仍然是無法讓人忍受的，況且，任何一本預(yù)先定義的字典都無法適應(yīng)不同文件中數(shù)據(jù)的變化情況。對(duì)了，字典模型也有相應(yīng)的“自適應(yīng)”方案。我們可以隨著信息的不斷輸入，從已經(jīng)輸入的信息中建立合適的字典，并不斷更新這本字典，以適應(yīng)數(shù)據(jù)的不斷變化。
讓我們從另一個(gè)角度理解一下自適應(yīng)模型。Cluade Shannon 曾試圖通過一個(gè)“聚會(huì)游戲”(party game)來測(cè)定英語的真實(shí)信息容量。他每次向聽眾公布一條被他隱藏起一個(gè)字符的消息，讓聽眾來猜下一個(gè)字符是什么，一次猜一個(gè)，直到猜對(duì)為止。然后，Shannon 使用猜測(cè)次數(shù)來確定整個(gè)信息的熵。在這個(gè)實(shí)驗(yàn)中，一種根據(jù)前面出現(xiàn)過的字符估計(jì)下一個(gè)字符概率的模型就存在于聽眾的頭腦中，比計(jì)算機(jī)中使用的自適應(yīng)模型更為高級(jí)的是，聽眾除了根據(jù)字符出現(xiàn)過的次數(shù)外，還可以根據(jù)他們對(duì)語言的經(jīng)驗(yàn)進(jìn)行猜測(cè)。
編碼
通過模型，我們已經(jīng)確定了對(duì)某一個(gè)符號(hào)該用多少位二進(jìn)制數(shù)進(jìn)行編碼?，F(xiàn)在的問題是，如何設(shè)計(jì)一種編碼方案，使其盡量精確地用模型計(jì)算出來的位數(shù)表示某個(gè)符號(hào)。
最先被考慮的問題是，如果對(duì) a 用 3 個(gè)二進(jìn)制位就可以表示，而對(duì) b 用 4 個(gè)二進(jìn)制位就可以表示，那么，在解碼時(shí)，面對(duì)一連串的二進(jìn)制流，我怎么知道哪三個(gè)位是 a，哪四個(gè)位是 b 呢？所以，必須設(shè)計(jì)出一種編碼方式，使得解碼程序可以方便地分離每個(gè)字符的編碼部分。于是有了一種叫“前綴編碼”的技術(shù)。該技術(shù)的主導(dǎo)思想是，任何一個(gè)字符的編碼，都不是另一個(gè)字符編碼的前綴。反過來說就是，任何一個(gè)字符的編碼，都不是由另一個(gè)字符的編碼加上若干位 0 或 1 組成?？匆幌虑熬Y編碼的一個(gè)最簡(jiǎn)單的例子：
符號(hào) 編碼
A 0
B 10
C 110
D 1110
E 11110
有了上面的碼表，你一定可以輕松地從下面這串二進(jìn)制流中分辨出真正的信息內(nèi)容了：
1110010101110110111100010 - DABBDCEAAB
下一個(gè)問題是：象上面這樣的前綴編碼只能表示整數(shù)位的符號(hào)，對(duì)幾點(diǎn)幾位的符號(hào)只能用近似的整數(shù)位輸出，那么怎樣輸出小數(shù)位數(shù)呢？科學(xué)家們用算術(shù)編碼解決了這個(gè)問題，我們將在第四章對(duì)算術(shù)編碼作詳細(xì)的討論。
總結(jié)一下
不同的模型使用不同的方法計(jì)算字符的出現(xiàn)概率，由此概率可以得出字符的熵；然后使用不同的編碼方法，盡量接近我們期望得到的熵值。所以，壓縮效果的好壞一方面取決于模型能否準(zhǔn)確地得到字符概率，另一方面也取決于編碼方法能否準(zhǔn)確地用期望的位數(shù)輸出字符代碼。換句話說，壓縮 = 模型 + 編碼。如下圖所示：
--------- 符號(hào) ---------- 概率 ---------- 代碼 ----------
| 輸入 |-------->;| 模型 |-------->;| 編碼 |-------->;| 輸出 |
--------- ---------- ---------- ----------
資源
我們已經(jīng)知道，編寫壓縮程序往往不能對(duì)數(shù)據(jù)的整個(gè)字節(jié)進(jìn)行處理，而是要按照二進(jìn)制位來讀寫和處理數(shù)據(jù)，操作二進(jìn)制位的函數(shù)也就成為了壓縮程序中使用最為普遍的工具函數(shù)。
幾種壓縮算法奇妙的二叉樹：Huffman的貢獻(xiàn)
提起 Huffman 這個(gè)名字，程序員們至少會(huì)聯(lián)想到二叉樹和二進(jìn)制編碼。的確，我們總以 Huffman 編碼來概括 D.A.Huffman 個(gè)人對(duì)計(jì)算機(jī)領(lǐng)域特別是數(shù)據(jù)壓縮領(lǐng)域的杰出貢獻(xiàn)。我們知道，壓縮 = 模型 + 編碼，作為一種壓縮方法，我們必須全面考慮其模型和編碼兩個(gè)模塊的功效；但同時(shí)，模型和編碼兩個(gè)模塊又相互具有獨(dú)立性。舉例來說，一個(gè)使用 Huffman 編碼方法的程序，完全可以采用不同的模型來統(tǒng)計(jì)字符在信息中出現(xiàn)的概率。因此，我們這一章將首先圍繞 Huffman 先生最為重要的貢獻(xiàn) —— Huffman 編碼展開討論，隨后，我們?cè)倬唧w介紹可以和 Huffman 聯(lián)合使用的概率模型。
為什么是二叉樹
為什么壓縮領(lǐng)域中的編碼方法總和二叉樹聯(lián)系在一起呢？原因非常簡(jiǎn)單，回憶一下我們介紹過的“前綴編碼”：為了使用不固定的碼長(zhǎng)表示單個(gè)字符，編碼必須符合“前綴編碼”的要求，即較短的編碼決不能是較長(zhǎng)編碼的前綴。要構(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
Shannon-Fano 編碼
進(jìn)入 Huffman 先生構(gòu)造的神奇二叉樹之前，我們先來看一下它的前身，由 Claude Shannon 和 R.M.Fano 兩人提出的 Shannon-Fano 編碼。
討論之前，我們假定要編碼字符的出現(xiàn)概率已經(jīng)由某一模型統(tǒng)計(jì)出來，例如，對(duì)下面這串出現(xiàn)了五種字符的信息( 40 個(gè)字符長(zhǎng) ):
cabcedeacacdeddaaabaababaaabbacdebaceada
五種字符的出現(xiàn)次數(shù)分別：a - 16，b - 7，c - 6，d - 6，e - 5。
Shannon-Fano 編碼的核心仍然是構(gòu)造二叉樹，構(gòu)造的方式非常簡(jiǎn)單：
1) 將給定符號(hào)按照其頻率從大到小排序。對(duì)上面的例子，應(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) 分別對(duì)左右子樹重復(fù) 2 3 兩步，直到所有的符號(hào)都成為二叉樹的樹葉為止?，F(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 ......
碼長(zhǎng)共 91 位?？紤]用 ASCII 碼表示上述信息需要 8 * 40 = 240 位，我們確實(shí)實(shí)現(xiàn)了數(shù)據(jù)壓縮。
Huffman 編碼
Huffman 編碼構(gòu)造二叉樹的方法和 Shannon-Fano 正好相反，不是自上而下，而是從樹葉到樹根生成二叉樹?，F(xiàn)在，我們?nèi)匀皇褂蒙厦娴睦觼韺W(xué)習(xí) Huffman 編碼方法。
1) 將各個(gè)符號(hào)及其出現(xiàn)頻率分別作為不同的小二叉樹（目前每棵樹只有根節(jié)點(diǎn)）。
a(16) b(7) c(6) d(6) e(5)
2) 在 1 中得到的樹林里找出頻率值最小的兩棵樹，將他們分別作為左、右子樹連成一棵大一些的二叉樹，該二叉樹的頻率值為兩棵子樹頻率值之和。對(duì)上面的例子，我們得到一個(gè)新的樹林：
| (11)
a(16) b(7) c(6) +---+---+
| |
d e
3) 對(duì)上面得到的樹林重復(fù) 2 的做法，直到所有符號(hào)都連入樹中為止。這一步完成后，我們有這樣的二叉樹：
根(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
對(duì)例子中信息的編碼為：
cabcedeacacdeddaaabaababaaabbacdebaceada
101 0 100 101 111 110 111 0 101 0 101 ......
碼長(zhǎng)共 88 位。這比使用 Shannon-Fano 編碼要更短一點(diǎn)。
讓我們回顧一下熵的知識(shí)，使用我們?cè)诘诙聦W(xué)到的計(jì)算方法，上面的例子中，每個(gè)字符的熵為：
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)比較接近該信息的熵值了。同時(shí)，我們也看出，無論是 Shannon-Fano 還是 Huffman，都只能用近似的整數(shù)位來表示單個(gè)符號(hào)，而不是理想的小數(shù)位。我們可以將它們做一個(gè)對(duì)比：
符號(hào) 理想位數(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 編碼）
最簡(jiǎn)單，最容易被 Huffman 編碼利用的模型是“靜態(tài)統(tǒng)計(jì)模型”，也就是說在編碼前統(tǒng)計(jì)要編碼的信息中所有字符的出現(xiàn)頻率，讓后根據(jù)統(tǒng)計(jì)出的信息建立編碼樹，進(jìn)行編碼。這種模型的缺點(diǎn)是顯而易見的：首先，對(duì)數(shù)據(jù)量較大的信息，靜態(tài)統(tǒng)計(jì)要消耗大量的時(shí)間；其次，必須保存統(tǒng)計(jì)出的結(jié)果以便解碼時(shí)構(gòu)造相同的編碼樹，或者直接保存編碼樹本身，而且，對(duì)于每次靜態(tài)統(tǒng)計(jì)，都有不同的結(jié)果，必須分別予以保存，這要消耗大量的空間（這意味著壓縮效率的下降）；再次，事實(shí)上，即使不將編碼樹計(jì)算在內(nèi)，對(duì)通常含有 0 - 255 字符集的計(jì)算機(jī)文件來說，靜態(tài)統(tǒng)計(jì)模型統(tǒng)計(jì)出的頻率是字符在整個(gè)文件中的出現(xiàn)頻率，往往反映不出字符在文件中不同局部出現(xiàn)頻率的變化情況，使用這一頻率進(jìn)行壓縮，大多數(shù)情況下得不到太好壓縮效果，文件有時(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ì)信息，而且一般說來對(duì)該類文件有著較好的壓縮效果。這種方案除了適應(yīng)性不太強(qiáng)以外，偶爾還會(huì)有一些尷尬的時(shí)候。讀一遍下面這段話：
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í)候。
對(duì)英文或中文文本，有一種比較實(shí)用的靜態(tài)模型：不是把字符而是把英文單詞或中文詞語作為統(tǒng)計(jì)頻率和編碼的單位進(jìn)行壓縮。也就是說，每次編碼的不再是 a b c 這樣的單個(gè)符號(hào)，而是 the look flower 這樣的單詞。這種壓縮方式可以達(dá)到相當(dāng)不錯(cuò)的壓縮效果，并被廣泛地用于全文檢索系統(tǒng)。
對(duì)基于詞的編碼方式，需要解決幾個(gè)技術(shù)難點(diǎn)。首先是分詞的問題，英文單詞可以由詞間空格分隔，但中文怎么辦呢？其實(shí)，有很多中文分詞算法可以解決這個(gè)問題，本書就不再詳細(xì)介紹了。王笨笨就曾開發(fā)過一個(gè)不錯(cuò)的分詞模塊，但希望通過收取一定報(bào)酬的方式提供該模塊，如有需要，請(qǐng)和王笨笨 E-Mail 聯(lián)系。一旦我們將詞語分離出來，我們就可以對(duì)每個(gè)詞進(jìn)行頻率統(tǒng)計(jì)，然后建立 Huffman 編碼樹，輸出編碼時(shí)，一個(gè)編碼將代替一個(gè)詞語。但要注意，英文和漢語的單詞數(shù)量都在幾萬到十幾萬左右，也就是說，我們的 Huffman 編碼樹將擁有十幾萬個(gè)葉子節(jié)點(diǎn)，這對(duì)于一棵樹來說太大太大了，系統(tǒng)將無力承擔(dān)所需要的資源，這怎么辦呢？我們可以暫時(shí)拋開樹結(jié)構(gòu)，采用另一種構(gòu)造 Huffman 編碼的方式——范式 Huffman 編碼。
范式 Huffman 編碼(Canonical Huffman Code)的基本思路是：并非只有使用二叉樹建立的前綴編碼才是 Huffman 編碼，只要符合(1)是前綴編碼(2)某一字符編碼長(zhǎng)度和使用二叉樹建立的該字符的編碼長(zhǎng)度相同這兩個(gè)條件的編碼都可以叫做 Huffman 編碼?？紤]對(duì)下面六個(gè)單詞的編碼：
符號(hào) 出現(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 編碼具有一個(gè)明顯的特點(diǎn)：當(dāng)我們把要編碼的符號(hào)按照其頻率從小到大排列時(shí)，如果把范式 Huffman 編碼本身作為單詞的話，也呈現(xiàn)出從小到大的字典順序。
構(gòu)造范式 Huffman 編碼的方法大致是：
1) 統(tǒng)計(jì)每個(gè)要編碼符號(hào)的頻率。
2) 根據(jù)這些頻率信息求出該符號(hào)在傳統(tǒng) Huffman 編碼樹中的深度（也就是表示該符號(hào)所需要的位數(shù) - 編碼長(zhǎng)度）。因?yàn)槲覀冴P(guān)心的僅僅是該符號(hào)在樹中的深度，我們完全沒有必要構(gòu)造二叉樹，僅用一個(gè)數(shù)組就可以模擬二叉樹的創(chuàng)建過程并得到符號(hào)的深度，具體方法這里就不詳述了。
3) 分別統(tǒng)計(jì)從最大編碼長(zhǎng)度 maxlength 到 1 的每個(gè)長(zhǎng)度對(duì)應(yīng)了多少個(gè)符號(hào)。根據(jù)這一信息從 maxlength 個(gè) 0 開始以遞增順序?yàn)槊總€(gè)符號(hào)分配編碼。例如，編碼長(zhǎng)度為 5 的符號(hào)有 4 個(gè)，長(zhǎng)度為 3 的有 1 個(gè)，長(zhǎng)度為 2 的有 3 個(gè)，則分配的編碼依次為： 00000 00001 00010 00011 001 01 10 11
4) 編碼輸出壓縮信息，并保存按照頻率順序排列的符號(hào)表，然后保存每組同樣長(zhǎng)度編碼中的最前一個(gè)編碼以及該組中的編碼個(gè)數(shù)。
現(xiàn)在完全可以不依賴任何樹結(jié)構(gòu)進(jìn)行高速解壓縮了。而且在整個(gè)壓縮、解壓縮過程中需要的空間比傳統(tǒng) Huffman 編碼少得多。
最后要提到的是，Huffman 編碼可以采用自適應(yīng)模型，根據(jù)已經(jīng)編碼的符號(hào)頻率決定下一個(gè)符號(hào)的編碼。這時(shí)，我們無需為解壓縮預(yù)先保存任何信息，整個(gè)編碼是在壓縮和解壓縮過程中動(dòng)態(tài)創(chuàng)建的，而且自適應(yīng)編碼由于其符號(hào)頻率是根據(jù)信息內(nèi)容的變化動(dòng)態(tài)得到的，更符合符號(hào)的局部分布規(guī)律，因此在壓縮效果上比靜態(tài)模型好許多。但是，采用自適應(yīng)模型必須考慮編碼表的動(dòng)態(tài)特性，即編碼表必須可以隨時(shí)更新以適應(yīng)符號(hào)頻率的變化。對(duì)于 Huffman 編碼來說，我們很難建立能夠隨時(shí)更新的二叉樹，使用范式 Huffman 編碼是個(gè)不錯(cuò)的選擇，但依然存在不少技術(shù)上的難題。幸好，如果愿意的話，我們可以暫時(shí)不考慮自適應(yīng)模型的 Huffman 編碼，因?yàn)閷?duì)于自適應(yīng)模型我們還有許多更好的選擇，下面幾章將要談到的算術(shù)編碼、字典編碼等更為適合采用自適應(yīng)模型，我們將在其中深入探討自適應(yīng)模型的各種實(shí)現(xiàn)方法。
幾種壓縮算法向極限挑戰(zhàn)：算術(shù)編碼
我們?cè)谏弦徽轮幸呀?jīng)明白，Huffman 編碼使用整數(shù)個(gè)二進(jìn)制位對(duì)符號(hào)進(jìn)行編碼，這種方法在許多情況下無法得到最優(yōu)的壓縮效果。假設(shè)某個(gè)字符的出現(xiàn)概率為 80%，該字符事實(shí)上只需要 -log2(0.8) = 0.322 位編碼，但 Huffman 編碼一定會(huì)為其分配一位 0 或一位 1 的編碼?？梢韵胂?，整個(gè)信息的 80% 在壓縮后都幾乎相當(dāng)于理想長(zhǎng)度的 3 倍左右，壓縮效果可想而知。
難道真的能只輸出 0.322 個(gè) 0 或 0.322 個(gè) 1 嗎？是用剪刀把計(jì)算機(jī)存儲(chǔ)器中的二進(jìn)制位剪開嗎？計(jì)算機(jī)真有這樣的特異功能嗎？慢著慢著，我們不要被表面現(xiàn)象所迷惑，其實(shí)，在這一問題上，我們只要換一換腦筋，從另一個(gè)角度……哎呀，還是想不通，怎么能是半個(gè)呢？好了，不用費(fèi)心了，數(shù)學(xué)家們也不過是在十幾年前才想到了算術(shù)編碼這種神奇的方法，還是讓我們虛心地研究一下他們究竟是從哪個(gè)角度找到突破口的吧。
輸出：一個(gè)小數(shù)
更神奇的事情發(fā)生了，算術(shù)編碼對(duì)整條信息（無論信息有多么長(zhǎng)），其輸出僅僅是一個(gè)數(shù)，而且是一個(gè)介于 0 和 1 之間的二進(jìn)制小數(shù)。例如算術(shù)編碼對(duì)某條信息的輸出為 1010001111，那么它表示小數(shù) 0.1010001111，也即十進(jìn)制數(shù) 0.64。
咦？怎么一會(huì)兒是表示半個(gè)二進(jìn)制位，一會(huì)兒又是輸出一個(gè)小數(shù)，算術(shù)編碼怎么這么古怪呀？不要著急，我們借助下面一個(gè)簡(jiǎn)單的例子來闡釋算術(shù)編碼的基本原理。為了表示上的清晰，我們暫時(shí)使用十進(jìn)制表示算法中出現(xiàn)的小數(shù)，這絲毫不會(huì)影響算法的可行性。
考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的信息為 bccb。
在沒有開始?jí)嚎s進(jìn)程之前，假設(shè)我們對(duì) a b c 三者在信息中的出現(xiàn)概率一無所知（我們采用的是自適應(yīng)模型），沒辦法，我們暫時(shí)認(rèn)為三者的出現(xiàn)概率相等，也就是都為 1/3，我們將 0 - 1 區(qū)間按照概率的比例分配給三個(gè)字符，即 a 從 0.0000 到 0.3333，b 從 0.3333 到 0.6667，c 從 0.6667 到 1.0000。用圖形表示就是：
+-- 1.0000
|
Pc = 1/3 |
|
+-- 0.6667
|
Pb = 1/3 |
|
+-- 0.3333
|
Pa = 1/3 |
|
+-- 0.0000
現(xiàn)在我們拿到第一個(gè)字符 b，讓我們把目光投向 b 對(duì)應(yīng)的區(qū)間 0.3333 - 0.6667。這時(shí)由于多了字符 b，三個(gè)字符的概率分布變成：Pa = 1/4，Pb = 2/4，Pc = 1/4。好，讓我們按照新的概率分布比例劃分 0.3333 - 0.6667 這一區(qū)間，劃分的結(jié)果可以用圖形表示為：
+-- 0.6667
Pc = 1/4 |
+-- 0.5834
|
|
Pb = 2/4 |
|
|
+-- 0.4167
Pa = 1/4 |
+-- 0.3333
接著我們拿到字符 c，我們現(xiàn)在要關(guān)注上一步中得到的 c 的區(qū)間 0.5834 - 0.6667。新添了 c 以后，三個(gè)字符的概率分布變成 Pa = 1/5，Pb = 2/5，Pc = 2/5。我們用這個(gè)概率分布劃分區(qū)間 0.5834 - 0.6667：
+-- 0.6667
|
Pc = 2/5 |
|
+-- 0.6334
|
Pb = 2/5 |
|
+-- 0.6001
Pa = 1/5 |
+-- 0.5834
現(xiàn)在輸入下一個(gè)字符 c，三個(gè)字符的概率分布為：Pa = 1/6，Pb = 2/6，Pc = 3/6。我們來劃分 c 的區(qū)間 0.6334 - 0.6667：
+-- 0.6667
|
|
Pc = 3/6 |
|
|
+-- 0.6501
|
Pb = 2/6 |
|
+-- 0.6390
Pa = 1/6 |
+-- 0.6334
輸入最后一個(gè)字符 b，因?yàn)槭亲詈笠粋€(gè)字符，不用再做進(jìn)一步的劃分了，上一步中得到的 b 的區(qū)間為 0.6390 - 0.6501，好，讓我們?cè)谶@個(gè)區(qū)間內(nèi)隨便選擇一個(gè)容易變成二進(jìn)制的數(shù)，例如 0.64，將它變成二進(jìn)制 0.1010001111，去掉前面沒有太多意義的 0 和小數(shù)點(diǎn)，我們可以輸出 1010001111，這就是信息被壓縮后的結(jié)果，我們完成了一次最簡(jiǎn)單的算術(shù)壓縮過程。
怎么樣，不算很難吧？可如何解壓縮呢？那就更簡(jiǎn)單了。解壓縮之前我們?nèi)匀患俣ㄈ齻€(gè)字符的概率相等，并得出上面的第一幅分布圖。解壓縮時(shí)我們面對(duì)的是二進(jìn)制流 1010001111，我們先在前面加上 0 和小數(shù)點(diǎn)把它變成小數(shù) 0.1010001111，也就是十進(jìn)制 0.64。這時(shí)我們發(fā)現(xiàn) 0.64 在分布圖中落入字符 b 的區(qū)間內(nèi)，我們立即輸出字符 b，并得出三個(gè)字符新的概率分布。類似壓縮時(shí)采用的方法，我們按照新的概率分布劃分字符 b 的區(qū)間。在新的劃分中，我們發(fā)現(xiàn) 0.64 落入了字符 c 的區(qū)間，我們可以輸出字符 c。同理，我們可以繼續(xù)輸出所有的字符，完成全部解壓縮過程（注意，為了敘述方便，我們暫時(shí)回避了如何判斷解壓縮結(jié)束的問題，實(shí)際應(yīng)用中，這個(gè)問題并不難解決）。
現(xiàn)在把教程拋開，仔細(xì)回想一下，直到你理解了算術(shù)壓縮的基本原理，并產(chǎn)生了許多新的問題為止。
真的能接近極限嗎？
現(xiàn)在你一定明白了一些東西，也一定有了不少新問題，沒有關(guān)系，讓我們一個(gè)一個(gè)解決。
首先，我們?cè)磸?fù)強(qiáng)調(diào)，算術(shù)壓縮可以表示小數(shù)個(gè)二進(jìn)制位，并由此可以接近無損壓縮的熵極限，怎么從上面的描述中沒有看出來呢？
算術(shù)編碼實(shí)際上采用了化零為整的思想來表示小數(shù)個(gè)二進(jìn)制位，我們確實(shí)無法精確表示單個(gè)小數(shù)位字符，但我們可以將許多字符集中起來表示，僅僅允許在最后一位有些許的誤差。
結(jié)合上面的簡(jiǎn)單例子考慮，我們每輸入一個(gè)符號(hào)，都對(duì)概率的分布表做一下調(diào)整，并將要輸出的小數(shù)限定在某個(gè)越來越小的區(qū)間范圍內(nèi)。對(duì)輸出區(qū)間的限定是問題的關(guān)鍵所在，例如，我們輸入第一個(gè)字符 b 時(shí)，輸出區(qū)間被限定在 0.3333 - 0.6667 之間，我們無法決定輸出值得第一位是 3、4、5 還是 6，也就是說，b 的編碼長(zhǎng)度小于一個(gè)十進(jìn)制位（注意我們用十進(jìn)制講解，和二進(jìn)制不完全相同），那么我們暫時(shí)不決定輸出信息的任何位，繼續(xù)輸入下面的字符。直到輸入了第三個(gè)字符 c 以后，我們的輸出區(qū)間被限定在 0.6334 - 0.6667 之間，我們終于知道輸出小數(shù)的第一位（十進(jìn)制）是 6，但仍然無法知道第二位是多少，也即前三個(gè)字符的編碼長(zhǎng)度在 1 和 2 之間。等到我們輸入了所有字符之后，我們的輸出區(qū)間為 0.6390 - 0.6501，我們始終沒有得到關(guān)于第二位的確切信息，現(xiàn)在我們明白，輸出所有的 4 個(gè)字符，我們只需要 1 點(diǎn)幾個(gè)十進(jìn)制位，我們唯一的選擇是輸出 2 個(gè)十進(jìn)制位 0.64。這樣，我們?cè)谡`差不超過 1 個(gè)十進(jìn)制位的情況下相當(dāng)精確地輸出了所有信息，很好地接近了熵值（需要注明的是，為了更好地和下面的課程接軌，上面的例子采用的是 0 階自適應(yīng)模型，其結(jié)果和真正的熵值還有一定的差距）。
小數(shù)有多長(zhǎng)？
你一定已經(jīng)想到，如果信息內(nèi)容特別豐富，我們要輸出的小數(shù)將會(huì)很長(zhǎng)很長(zhǎng)，我們?cè)撊绾卧趦?nèi)存中表示如此長(zhǎng)的小數(shù)呢？
其實(shí)，沒有任何必要在內(nèi)存中存儲(chǔ)要輸出的整個(gè)小數(shù)。我們從上面的例子可以知道，在編碼的進(jìn)行中，我們會(huì)不斷地得到有關(guān)要輸出小數(shù)的各種信息。具體地講，當(dāng)我們將區(qū)間限定在 0.6390 - 0.6501 之間時(shí)，我們已經(jīng)知道要輸出的小數(shù)第一位（十進(jìn)制）一定是 6，那么我們完全可以將 6 從內(nèi)存中拿掉，接著在區(qū)間 0.390 - 0.501 之間繼續(xù)我們的壓縮進(jìn)程。內(nèi)存中始終不會(huì)有非常長(zhǎng)的小數(shù)存在。使用二進(jìn)制時(shí)也是一樣的，我們會(huì)隨著壓縮的進(jìn)行不斷決定下一個(gè)要輸出的二進(jìn)制位是 0 還是 1，然后輸出該位并減小內(nèi)存中小數(shù)的長(zhǎng)度。
靜態(tài)模型如何實(shí)現(xiàn)？
我們知道上面的簡(jiǎn)單例子采用的是自適應(yīng)模型，那么如何實(shí)現(xiàn)靜態(tài)模型呢？其實(shí)很簡(jiǎn)單。對(duì)信息 bccb 我們統(tǒng)計(jì)出其中只有兩個(gè)字符，概率分布為 Pb = 0.5，Pc = 0.5。我們?cè)趬嚎s過程中不必再更新此概率分布，每次對(duì)區(qū)間的劃分都依照此分布即可，對(duì)上例也就是每次都平分區(qū)間。這樣，我們的壓縮過程可以簡(jiǎn)單表示為：
輸出區(qū)間的下限 輸出區(qū)間的上限
--------------------------------------------------
壓縮前 0.0 1.0
輸入 b 0.0 0.5
輸入 c 0.25 0.5
輸入 c 0.375 0.5
輸入 b 0.375 0.4375
我們看出，最后的輸出區(qū)間在 0.375 - 0.4375 之間，甚至連一個(gè)十進(jìn)制位都沒有確定，也就是說，整個(gè)信息根本用不了一個(gè)十進(jìn)制位。如果我們改用二進(jìn)制來表示上述過程的話，我們會(huì)發(fā)現(xiàn)我們可以非常接近該信息的熵值（有的讀者可能已經(jīng)算出來了，該信息的熵值為 4 個(gè)二進(jìn)制位）。
為什么用自適應(yīng)模型？
既然我們使用靜態(tài)模型可以很好地接近熵值，為什么還要采用自適應(yīng)模型呢？
要知道，靜態(tài)模型無法適應(yīng)信息的多樣性，例如，我們上面得出的概率分布沒法在所有待壓縮信息上使用，為了能正確解壓縮，我們必須再消耗一定的空間保存靜態(tài)模型統(tǒng)計(jì)出的概率分布，保存模型所用的空間將使我們重新遠(yuǎn)離熵值。其次，靜態(tài)模型需要在壓縮前對(duì)信息內(nèi)字符的分布進(jìn)行統(tǒng)計(jì)，這一統(tǒng)計(jì)過程將消耗大量的時(shí)間，使得本來就比較慢的算術(shù)編碼壓縮更加緩慢。
另外還有最重要的一點(diǎn)，對(duì)較長(zhǎng)的信息，靜態(tài)模型統(tǒng)計(jì)出的符號(hào)概率是該符號(hào)在整個(gè)信息中的出現(xiàn)概率，而自適應(yīng)模型可以統(tǒng)計(jì)出某個(gè)符號(hào)在某一局部的出現(xiàn)概率或某個(gè)符號(hào)相對(duì)于某一上下文的出現(xiàn)概率，換句話說，自適應(yīng)模型得到的概率分布將有利于對(duì)信息的壓縮（可以說結(jié)合上下文的自適應(yīng)模型的信息熵建立在更高的概率層次上，其總熵值更?。玫幕谏舷挛牡淖赃m應(yīng)模型得到的壓縮結(jié)果將遠(yuǎn)遠(yuǎn)超過靜態(tài)模型。
自適應(yīng)模型的階
我們通常用“階”(order)這一術(shù)語區(qū)分不同的自適應(yīng)模型。本章開頭的例子中采用的是 0 階自適應(yīng)模型，也就是說，該例子中統(tǒng)計(jì)的是符號(hào)在已輸入信息中的出現(xiàn)概率，沒有考慮任何上下文信息。
如果我們將模型變成統(tǒng)計(jì)符號(hào)在某個(gè)特定符號(hào)后的出現(xiàn)概率，那么，模型就成為了 1 階上下文自適應(yīng)模型。舉例來說，我們要對(duì)一篇英文文本進(jìn)行編碼，我們已經(jīng)編碼了 10000 個(gè)英文字符，剛剛編碼的字符是 t，下一個(gè)要編碼的字符是 h。我們?cè)谇懊娴木幋a過程中已經(jīng)統(tǒng)計(jì)出前 10000 個(gè)字符中出現(xiàn)了 113 次字母 t，其中有 47 個(gè) t 后面跟著字母 h。我們得出字符 h 在字符 t 后的出現(xiàn)頻率是 47/113，我們使用這一頻率對(duì)字符 h 進(jìn)行編碼，需要 -log2(47/113) = 1.266 位。
對(duì)比 0 階自適應(yīng)模型，如果前 10000 個(gè)字符中 h 的出現(xiàn)次數(shù)為 82 次，則字符 h 的概率是 82/10000，我們用此概率對(duì) h 進(jìn)行編碼，需要 -log2(82/10000) = 6.930 位?？紤]上下文因素的優(yōu)勢(shì)顯而易見。
我們還可以進(jìn)一步擴(kuò)大這一優(yōu)勢(shì)，例如要編碼字符 h 的前兩個(gè)字符是 gt，而在已經(jīng)編碼的文本中 gt 后面出現(xiàn) h 的概率是 80%，那么我們只需要 0.322 位就可以編碼輸出字符 h。此時(shí)，我們使用的模型叫做 2 階上下文自適應(yīng)模型。
最理想的情況是采用 3 階自適應(yīng)模型。此時(shí)，如果結(jié)合算術(shù)編碼，對(duì)信息的壓縮效果將達(dá)到驚人的程度。采用更高階的模型需要消耗的系統(tǒng)空間和時(shí)間至少在目前還無法讓人接受，使用算術(shù)壓縮的應(yīng)用程序大多數(shù)采用 2 階或 3 階的自適應(yīng)模型。
轉(zhuǎn)義碼的作用
使用自適應(yīng)模型的算術(shù)編碼算法必須考慮如何為從未出現(xiàn)過的上下文編碼。例如，在 1 階上下文模型中，需要統(tǒng)計(jì)出現(xiàn)概率的上下文可能有 256 * 256 = 65536 種，因?yàn)?0 - 255 的所有字符都有可能出現(xiàn)在 0 - 255 個(gè)字符中任何一個(gè)之后。當(dāng)我們面對(duì)一個(gè)從未出現(xiàn)過的上下文時(shí)（比如剛編碼過字符 b，要編碼字符 d，而在此之前，d 從未出現(xiàn)在 b 的后面），該怎樣確定字符的概率呢？
比較簡(jiǎn)單的辦法是在壓縮開始之前，為所有可能的上下文分配計(jì)數(shù)為 1 的出現(xiàn)次數(shù)，如果在壓縮中碰到從未出現(xiàn)的 bd 組合，我們認(rèn)為 d 出現(xiàn)在 b 之后的次數(shù)為 1，并可由此得到概率進(jìn)行正確的編碼。使用這種方法的問題是，在壓縮開始之前，在某上下文中的字符已經(jīng)具有了一個(gè)比較小的頻率。例如對(duì) 1 階上下文模型，壓縮前，任意字符的頻率都被人為地設(shè)定為 1/65536，按照這個(gè)頻率，壓縮開始時(shí)每個(gè)字符要用 16 位編碼，只有隨著壓縮的進(jìn)行，出現(xiàn)較頻繁的字符在頻率分布圖上占據(jù)了較大的空間后，壓縮效果才會(huì)逐漸好起來。對(duì)于 2 階或 3 階上下文模型，情況就更糟糕，我們要為幾乎從不出現(xiàn)的大多數(shù)上下文浪費(fèi)大量的空間。
我們通過引入“轉(zhuǎn)義碼”來解決這一問題。“轉(zhuǎn)義碼”是混在壓縮數(shù)據(jù)流中的特殊的記號(hào)，用于通知解壓縮程序下一個(gè)上下文在此之前從未出現(xiàn)過，需要使用低階的上下文進(jìn)行編碼。
舉例來講，在 3 階上下文模型中，我們剛編碼過 ght，下一個(gè)要編碼的字符是 a，而在此之前，ght 后面從未出現(xiàn)過字符 a，這時(shí)，壓縮程序輸出轉(zhuǎn)義碼，然后檢查 2 階的上下文表，看在此之前 ht 后面出現(xiàn) a 的次數(shù)；如果 ht 后面曾經(jīng)出現(xiàn)過 a，那么就使用 2 階上下文表中的概率為 a 編碼，否則再輸出轉(zhuǎn)義碼，檢查 1 階上下文表；如果仍未能查到，則輸出轉(zhuǎn)義碼，轉(zhuǎn)入最低的 0 階上下文表，看以前是否出現(xiàn)過字符 a；如果以前根本沒有出現(xiàn)過 a，那么我們轉(zhuǎn)到一個(gè)特殊的“轉(zhuǎn)義”上下文表，該表內(nèi)包含 0 - 255 所有符號(hào)，每個(gè)符號(hào)的計(jì)數(shù)都為 1，并且永遠(yuǎn)不會(huì)被更新，任何在高階上下文中沒有出現(xiàn)的符號(hào)都可以退到這里按照 1/256 的頻率進(jìn)行編碼。
“轉(zhuǎn)義碼”的引入使我們擺脫了從未出現(xiàn)過的上下文的困擾，可以使模型根據(jù)輸入數(shù)據(jù)的變化快速調(diào)整到最佳位置，并迅速減少對(duì)高概率符號(hào)編碼所需要的位數(shù)。
存儲(chǔ)空間問題
在算術(shù)編碼高階上下文模型的實(shí)現(xiàn)中，對(duì)內(nèi)存的需求量是一個(gè)十分棘手的問題。因?yàn)槲覀儽仨毐３謱?duì)已出現(xiàn)的上下文的計(jì)數(shù)，而高階上下文模型中可能出現(xiàn)的上下文種類又是如此之多，數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)將直接影響到算法實(shí)現(xiàn)的成功與否。
在 1 階上下文模型中，使用數(shù)組來進(jìn)行出現(xiàn)次數(shù)的統(tǒng)計(jì)是可行的，但對(duì)于 2 階或 3 階上下文模型，數(shù)組大小將依照指數(shù)規(guī)律增長(zhǎng)，現(xiàn)有計(jì)算機(jī)的內(nèi)存滿足不了我們的要求。
比較聰明的辦法是采用樹結(jié)構(gòu)存儲(chǔ)所有出現(xiàn)過的上下文。利用高階上下文總是建立在低階上下文的基礎(chǔ)上這一規(guī)律，我們將 0 階上下文表存儲(chǔ)在數(shù)組中，每個(gè)數(shù)組元素包含了指向相應(yīng)的 1 階上下文表的指針，1 階上下文表中又包含了指向 2 階上下文表的指針……由此構(gòu)成整個(gè)上下文樹。樹中只有出現(xiàn)過的上下文才擁有已分配的節(jié)點(diǎn)，沒有出現(xiàn)過的上下文不必占用內(nèi)存空間。在每個(gè)上下文表中，也無需保存所有 256 個(gè)字符的計(jì)數(shù)，只有在該上下文后面出現(xiàn)過的字符才擁有計(jì)數(shù)值。由此，我們可以最大限度地減少空間消耗。
幾種壓縮算法全新的思路
我們?cè)诘谌偷谒恼轮杏懻摰膲嚎s模型都是基于對(duì)信息中單個(gè)字符出現(xiàn)頻率的統(tǒng)計(jì)而設(shè)計(jì)的，直到 70 年代末期，這種思路在數(shù)據(jù)壓縮領(lǐng)域一直占據(jù)著統(tǒng)治地位。在我們今天看來，這種情形在某種程度上顯得有些可笑，但事情就是這樣，一旦某項(xiàng)技術(shù)在某一領(lǐng)域形成了慣例，人們就很難創(chuàng)造出在思路上與其大相徑庭的哪怕是更簡(jiǎn)單更實(shí)用的技術(shù)來。
我們敬佩那兩個(gè)在數(shù)據(jù)壓縮領(lǐng)域做出了杰出貢獻(xiàn)的以色列人，因?yàn)檎撬麄兇蚱屏?Huffman 編碼一統(tǒng)天下的格局，帶給了我們既高效又簡(jiǎn)便的“字典模型”。至今，幾乎我們?nèi)粘Ｊ褂玫乃型ㄓ脡嚎s工具，象 ARJ，PKZip，WinZip，LHArc，RAR，GZip，ACE，ZOO，TurboZip，Compress，JAR……甚至許多硬件如網(wǎng)絡(luò)設(shè)備中內(nèi)置的壓縮算法，無一例外，都可以最終歸結(jié)為這兩個(gè)以色列人的杰出貢獻(xiàn)。
說起來，字典模型的思路相當(dāng)簡(jiǎn)單，我們?nèi)粘Ｉ钪芯徒?jīng)常在使用這種壓縮思想。我們常常跟人說“奧運(yùn)會(huì)”、“IBM”、“TCP”之類的詞匯，說者和聽者都明白它們指的是“奧林匹克運(yùn)動(dòng)會(huì)”、“國(guó)際商業(yè)機(jī)器公司”和“傳輸控制協(xié)議”，這實(shí)際就是信息的壓縮。我們之所以可以順利使用這種壓縮方式而不產(chǎn)生語義上的誤解，是因?yàn)樵谡f者和聽者的心中都有一個(gè)事先定義好的縮略語字典，我們?cè)趯?duì)信息進(jìn)行壓縮（說）和解壓縮（聽）的過程中都對(duì)字典進(jìn)行了查詢操作。字典壓縮模型正是基于這一思路設(shè)計(jì)實(shí)現(xiàn)的。
最簡(jiǎn)單的情況是，我們擁有一本預(yù)先定義好的字典。例如，我們要對(duì)一篇中文文章進(jìn)行壓縮，我們手中已經(jīng)有一本《現(xiàn)代漢語詞典》。那么，我們掃描要壓縮的文章，并對(duì)其中的句子進(jìn)行分詞操作，對(duì)每一個(gè)獨(dú)立的詞語，我們?cè)凇冬F(xiàn)代漢語詞典》查找它的出現(xiàn)位置，如果找到，我們就輸出頁(yè)碼和該詞在該頁(yè)中的序號(hào)，如果沒有找到，我們就輸出一個(gè)新詞。這就是靜態(tài)字典模型的基本算法了。
你一定可以發(fā)現(xiàn)，靜態(tài)字典模型并不是好的選擇。首先，靜態(tài)模型的適應(yīng)性不強(qiáng)，我們必須為每類不同的信息建立不同的字典；其次，對(duì)靜態(tài)模型，我們必須維護(hù)信息量并不算小的字典，這一額外的信息量影響了最終的壓縮效果。所以，幾乎所有通用的字典模型都使用了自適應(yīng)的方式，也就是說，將已經(jīng)編碼過的信息作為字典，如果要編碼的字符串曾經(jīng)出現(xiàn)過，就輸出該字符串的出現(xiàn)位置及長(zhǎng)度，否則輸出新的字符串。根據(jù)這一思路，你能從下面這幅圖中讀出其中包含的原始信息嗎？
啊，對(duì)了，是“吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮”。現(xiàn)在你該大致明白自適應(yīng)字典模型的梗概了吧。好了，下面就讓我們來深入學(xué)習(xí)字典模型的第一類實(shí)現(xiàn)——LZ77 算法。
滑動(dòng)的窗口
LZ77 算法在某種意義上又可以稱為“滑動(dòng)窗口壓縮”，這是由于該算法將一個(gè)虛擬的，可以跟隨壓縮進(jìn)程滑動(dòng)的窗口作為術(shù)語字典，要壓縮的字符串如果在該窗口中出現(xiàn)，則輸出其出現(xiàn)位置和長(zhǎng)度。使用固定大小窗口進(jìn)行術(shù)語匹配，而不是在所有已經(jīng)編碼的信息中匹配，是因?yàn)槠ヅ渌惴ǖ臅r(shí)間消耗往往很多，必須限制字典的大小才能保證算法的效率；隨著壓縮的進(jìn)程滑動(dòng)字典窗口，使其中總包含最近編碼過的信息，是因?yàn)閷?duì)大多數(shù)信息而言，要編碼的字符串往往在最近的上下文中更容易找到匹配串。
參照下圖，讓我們熟悉一下 LZ77 算法的基本流程。
1、從當(dāng)前壓縮位置開始，考察未編碼的數(shù)據(jù)，并試圖在滑動(dòng)窗口中找出最長(zhǎng)的匹配字符串，如果找到，則進(jìn)行步驟 2，否則進(jìn)行步驟 3。
2、輸出三元符號(hào)組 ( off, len, c )。其中 off 為窗口中匹配字符串相對(duì)窗口邊界的偏移，len 為可匹配的長(zhǎng)度，c 為下一個(gè)字符。然后將窗口向后滑動(dòng) len + 1 個(gè)字符，繼續(xù)步驟 1。
3、輸出三元符號(hào)組 ( 0, 0, c )。其中 c 為下一個(gè)字符。然后將窗口向后滑動(dòng) len + 1 個(gè)字符，繼續(xù)步驟 1。
我們結(jié)合實(shí)例來說明。假設(shè)窗口的大小為 10 個(gè)字符，我們剛編碼過的 10 個(gè)字符是：abcdbbccaa，即將編碼的字符為：abaeaaabaee
我們首先發(fā)現(xiàn)，可以和要編碼字符匹配的最長(zhǎng)串為 ab ( off = 0, len = 2 ), ab 的下一個(gè)字符為 a，我們輸出三元組：( 0, 2, a )
現(xiàn)在窗口向后滑動(dòng) 3 個(gè)字符，窗口中的內(nèi)容為：dbbccaaaba
下一個(gè)字符 e 在窗口中沒有匹配，我們輸出三元組：( 0, 0, e )
窗口向后滑動(dòng) 1 個(gè)字符，其中內(nèi)容變?yōu)椋篵bccaaabae
我們馬上發(fā)現(xiàn)，要編碼的 aaabae 在窗口中存在( off = 4, len = 6 )，其后的字符為 e，我們可以輸出：( 4, 6, e )
這樣，我們將可以匹配的字符串都變成了指向窗口內(nèi)的指針，并由此完成了對(duì)上述數(shù)據(jù)的壓縮。
解壓縮的過程十分簡(jiǎn)單，只要我們向壓縮時(shí)那樣維護(hù)好滑動(dòng)的窗口，隨著三元組的不斷輸入，我們?cè)诖翱谥姓业较鄳?yīng)的匹配串，綴上后繼字符 c 輸出（如果 off 和 len 都為 0 則只輸出后繼字符 c )即可還原出原始數(shù)據(jù)。
當(dāng)然，真正實(shí)現(xiàn) LZ77 算法時(shí)還有許多復(fù)雜的問題需要解決，下面我們就來對(duì)可能碰到的問題逐一加以探討。
編碼方法
我們必須精心設(shè)計(jì)三元組中每個(gè)分量的表示方法，才能達(dá)到較好的壓縮效果。一般來講，編碼的設(shè)計(jì)要根據(jù)待編碼的數(shù)值的分布情況而定。對(duì)于三元組的第一個(gè)分量——窗口內(nèi)的偏移，通常的經(jīng)驗(yàn)是，偏移接近窗口尾部的情況要多于接近窗口頭部的情況，這是因?yàn)樽址谂c其接近的位置較容易找到匹配串，但對(duì)于普通的窗口大小（例如 4096 字節(jié)）來說，偏移值基本還是均勻分布的，我們完全可以用固定的位數(shù)來表示它。
編碼 off 需要的位數(shù) bitnum = upper_bound( log2( MAX_WND_SIZE ))
由此，如果窗口大小為 4096，用 12 位就可以對(duì)偏移編碼。如果窗口大小為 2048，用 11 位就可以了。復(fù)雜一點(diǎn)的程序考慮到在壓縮開始時(shí)，窗口大小并沒有達(dá)到 MAX_WND_SIZE，而是隨著壓縮的進(jìn)行增長(zhǎng)，因此可以根據(jù)窗口的當(dāng)前大小動(dòng)態(tài)計(jì)算所需要的位數(shù)，這樣可以略微節(jié)省一點(diǎn)空間。
對(duì)于第二個(gè)分量——字符串長(zhǎng)度，我們必須考慮到，它在大多數(shù)時(shí)候不會(huì)太大，少數(shù)情況下才會(huì)發(fā)生大字符串的匹配。顯然可以使用一種變長(zhǎng)的編碼方式來表示該長(zhǎng)度值。在前面我們已經(jīng)知道，要輸出變長(zhǎng)的編碼，該編碼必須滿足前綴編碼的條件。其實(shí) Huffman 編碼也可以在此處使用，但卻不是最好的選擇。適用于此處的好的編碼方案很多，我在這里介紹其中兩種應(yīng)用非常廣泛的編碼。
第一種叫 Golomb 編碼。假設(shè)對(duì)正整數(shù) x 進(jìn)行 Golomb 編碼，選擇參數(shù) m，令
b = 2m
q = INT((x - 1)/b)
r = x - qb - 1
則 x 可以被編碼為兩部分，第一部分是由 q 個(gè) 1 加 1 個(gè) 0 組成，第二部分為 m 位二進(jìn)制數(shù)，其值為 r。我們將 m = 0, 1, 2, 3 時(shí)的 Golomb 編碼表列出：
值 x m = 0 m = 1 m = 2 m = 3
-------------------------------------------------------------
1 0 0 0 0 00 0 000
2 10 0 1 0 01 0 001
3 110 10 0 0 10 0 010
4 1110 10 1 0 11 0 011
5 11110 110 0 10 00 0 100
6 111110 110 1 10 01 0 101
7 1111110 1110 0 10 10 0 110
8 11111110 1110 1 10 11 0 111
9 111111110 11110 0 110 00 10 000
從表中我們可以看出，Golomb 編碼不但符合前綴編碼的規(guī)律，而且可以用較少的位表示較小的 x 值，而用較長(zhǎng)的位表示較大的 x 值。這樣，如果 x 的取值傾向于比較小的數(shù)值時(shí)，Golomb 編碼就可以有效地節(jié)省空間。當(dāng)然，根據(jù) x 的分布規(guī)律不同，我們可以選取不同的 m 值以達(dá)到最好的壓縮效果。
對(duì)我們上面討論的三元組 len 值，我們可以采用 Golomb 方式編碼。上面的討論中 len 可能取 0，我們只需用 len + 1 的 Golomb 編碼即可。至于參數(shù) m 的選擇，一般經(jīng)驗(yàn)是取 3 或 4 即可。
可以考慮的另一種變長(zhǎng)前綴編碼叫做 γ 編碼。它也分作前后兩個(gè)部分，假設(shè)對(duì) x 編碼，令 q = int( log2x )，則編碼的前一部分是 q 個(gè) 1 加一個(gè) 0，后一部分是 q 位長(zhǎng)的二進(jìn)制數(shù)，其值等于 x - 2q 。γ編碼表如下：
值 x γ編碼
---------------------
1 0
2 10 0
3 10 1
4 110 00
5 110 01
6 110 10
7 110 11
8 1110 000
9 1110 001
其實(shí)，如果對(duì) off 值考慮其傾向于窗口后部的規(guī)律，我們也可以采用變長(zhǎng)的編碼方法。但這種方式對(duì)窗口較小的情況改善并不明顯，有時(shí)壓縮效果還不如固定長(zhǎng)編碼。
對(duì)三元組的最后一個(gè)分量——字符 c，因?yàn)槠浞植疾o規(guī)律可循，我們只能老老實(shí)實(shí)地用 8 個(gè)二進(jìn)制位對(duì)其編碼。
根據(jù)上面的敘述，相信你一定也能寫出高效的編碼和解碼程序了。
另一種輸出方式
LZ77 的原始算法采用三元組輸出每一個(gè)匹配串及其后續(xù)字符，即使沒有匹配，我們?nèi)匀恍枰敵鲆粋€(gè) len = 0 的三元組來表示單個(gè)字符。試驗(yàn)表明，這種方式對(duì)于某些特殊情況（例如同一字符不斷重復(fù)的情形）有著較好的適應(yīng)能力。但對(duì)于一般數(shù)據(jù)，我們還可以設(shè)計(jì)出另外一種更為有效的輸出方式：將匹配串和不能匹配的單個(gè)字符分別編碼、分別輸出，輸出匹配串時(shí)不同時(shí)輸出后續(xù)字符。
我們將每一個(gè)輸出分成匹配串和單個(gè)字符兩種類型，并首先輸出一個(gè)二進(jìn)制位對(duì)其加以區(qū)分。例如，輸出 0 表示下面是一個(gè)匹配串，輸出 1 表示下面是一個(gè)單個(gè)字符。
之后，如果要輸出的是單個(gè)字符，我們直接輸出該字符的字節(jié)值，這要用 8 個(gè)二進(jìn)制位。也就是說，我們輸出一個(gè)單個(gè)的字符共需要 9 個(gè)二進(jìn)制位。
如果要輸出的是匹配串，我們按照前面的方法依次輸出 off 和 len。對(duì) off，我們可以輸出定長(zhǎng)編碼，也可以輸出變長(zhǎng)前綴碼，對(duì) len 我們輸出變長(zhǎng)前綴碼。有時(shí)候我們可以對(duì)匹配長(zhǎng)度加以限制，例如，我們可以限制最少匹配 3 個(gè)字符。因?yàn)?，?duì)于 2 個(gè)字符的匹配串，我們使用匹配串的方式輸出并不一定比我們直接輸出 2 個(gè)單個(gè)字符（需要 18 位）節(jié)省空間（是否節(jié)省取決于我們采用何種編碼輸出 off 和 len）。
這種輸出方式的優(yōu)點(diǎn)是輸出單個(gè)字符的時(shí)候比較節(jié)省空間。另外，因?yàn)椴粡?qiáng)求每次都外帶一個(gè)后續(xù)字符，可以適應(yīng)一些較長(zhǎng)匹配的情況。
如何查找匹配串
在滑動(dòng)窗口中查找最長(zhǎng)的匹配串，大概是 LZ77 算法中的核心問題。容易知道，LZ77 算法中空間和時(shí)間的消耗集中于對(duì)匹配串的查找算法。每次滑動(dòng)窗口之后，都要進(jìn)行下一個(gè)匹配串的查找，如果查找算法的時(shí)間效率在 O(n2) 或者更高，總的算法時(shí)間效率就將達(dá)到 O(n3)，這是我們無法容忍的。正常的順序匹配算法顯然無法滿足我們的要求。事實(shí)上，我們有以下幾種可選的方案。
1、限制可匹配字符串的最大長(zhǎng)度（例如 20 個(gè)字節(jié)），將窗口中每一個(gè) 20 字節(jié)長(zhǎng)的串抽取出來，按照大小順序組織成二叉有序樹。在這樣的二叉有序樹中進(jìn)行字符串的查找，其效率是很高的。樹中每一個(gè)節(jié)點(diǎn)大小是 20(key) + 4(off) + 4(left child) + 4(right child) = 32。樹中共有 MAX_WND_SIZE - 19 個(gè)節(jié)點(diǎn)，假如窗口大小為 4096 字節(jié)，樹的大小大約是 130k 字節(jié)?？臻g消耗也不算多。這種方法對(duì)匹配串長(zhǎng)度的限制雖然影響了壓縮程序?qū)σ恍┨厥鈹?shù)據(jù)（又很長(zhǎng)的匹配串）的壓縮效果，但就平均性能而言，壓縮效果還是不錯(cuò)的。
2、將窗口中每個(gè)長(zhǎng)度為 3 （視情況也可取 2 或 4）的字符串建立索引，先在此索引中匹配，之后對(duì)得出的每個(gè)可匹配位置進(jìn)行順序查找，直到找到最長(zhǎng)匹配字符串。因?yàn)殚L(zhǎng)度為 3 的字符串可以有 2563 種情況，我們不可能用靜態(tài)數(shù)組存儲(chǔ)該索引結(jié)構(gòu)。使用 Hash 表是一個(gè)明智的選擇。我們可以僅用 MAX_WND_SIZE - 1 的數(shù)組存儲(chǔ)每個(gè)索引點(diǎn)，Hash 函數(shù)的參數(shù)當(dāng)然是字符串本身的 3 個(gè)字符值了，Hash 函數(shù)算法及 Hash 之后的散列函數(shù)很容易設(shè)計(jì)。每個(gè)索引點(diǎn)之后是該字符串出現(xiàn)的所有位置，我們可以使用單鏈表來存儲(chǔ)每一個(gè)位置。值得注意的是，對(duì)一些特殊情況比如 aaaaaa...之類的連續(xù)字串，字符串 aaa 有很多連續(xù)出現(xiàn)位置，但我們無需對(duì)其中的每一個(gè)位置都進(jìn)行匹配，只要對(duì)最左邊和最右邊的位置操作就可以了。解決的辦法是在鏈表節(jié)點(diǎn)中紀(jì)錄相同字符連續(xù)出現(xiàn)的長(zhǎng)度，對(duì)連續(xù)的出現(xiàn)位置不再建立新的節(jié)點(diǎn)。這種方法可以匹配任意長(zhǎng)度的字符串，壓縮效果要好一些，但缺點(diǎn)是查找耗時(shí)多于第一種方法。
3、使用字符樹( trie )來對(duì)窗口內(nèi)的字符串建立索引，因?yàn)樽址娜≈捣秶?0 - 255，字符樹本身的層次不可能太多，3 - 4 層之下就應(yīng)該換用其他的數(shù)據(jù)結(jié)構(gòu)例如 Hash 表等。這種方法可以作為第二種方法的改進(jìn)算法出現(xiàn)，可以提高查找速度，但空間的消耗較多。
如果對(duì)窗口中的數(shù)據(jù)進(jìn)行索引，就必然帶來一個(gè)索引位置表示的問題，即我們?cè)谒饕Y(jié)構(gòu)中該往偏移項(xiàng)中存儲(chǔ)什么數(shù)據(jù)：首先，窗口是不斷向后滑動(dòng)的，我們每次將窗口向后滑動(dòng)一個(gè)位置，索引結(jié)構(gòu)就要作相應(yīng)的更新，我們必須刪除那些已經(jīng)移動(dòng)出窗口的數(shù)據(jù)，并增加新的索引信息。其次，窗口不斷向后滑動(dòng)的事實(shí)使我們無法用相對(duì)窗口左邊界的偏移來表示索引位置，因?yàn)殡S著窗口的滑動(dòng)，每個(gè)被索引的字符串相對(duì)窗口左邊界的位置都在改變，我們無法承擔(dān)更新所有索引位置的時(shí)間消耗。
解決這一問題的辦法是，使用一種可以環(huán)形滾動(dòng)的偏移系統(tǒng)來建立索引，而輸出匹配字符串時(shí)再將環(huán)形偏移還原為相對(duì)窗口左邊界的真正偏移。讓我們用圖形來說明，窗口剛剛達(dá)到最大時(shí)，環(huán)形偏移和原始偏移系統(tǒng)相同：
偏移： 0 1 2 3 4 ...... Max
|--------------------------------------------------------------|
環(huán)形偏移： 0 1 2 3 4 ...... Max
窗口向后滑動(dòng)一個(gè)字節(jié)后，滑出窗口左端的環(huán)形偏移 0 被補(bǔ)到了窗口右端：
偏移： 0 1 2 3 4 ...... Max
|--------------------------------------------------------------|
環(huán)形偏移： 1 2 3 4 5 ...... Max 0
窗口再滑動(dòng) 3 個(gè)子節(jié)后，偏移系統(tǒng)的情況是：
偏移： 0 1 2 3 4 ...... Max
|--------------------------------------------------------------|
環(huán)形偏移： 4 5 6 7 8...... Max 0 1 2 3
依此類推。
我們?cè)谒饕Y(jié)構(gòu)中保存環(huán)形偏移，但在查找到匹配字符串后，輸出的匹配位置 off 必須是原始偏移（相對(duì)窗口左邊），這樣才可以保證解碼程序的順利執(zhí)行。我們用下面的代碼將環(huán)形偏移還原為原始偏移：
// 由環(huán)形 off 得到真正的off(相對(duì)于窗口左邊)
// 其中 nLeftOff 為當(dāng)前與窗口左邊對(duì)應(yīng)的環(huán)形偏移值
int GetRealOff(int off)
{
if (off >;= nLeftOff)
return off - nLeftOff;
else
return (_MAX_WINDOW_SIZE - (nLeftOff - off));
}
這樣，解碼程序無需考慮環(huán)形偏移系統(tǒng)就可以順利高速解碼了。
資源
結(jié)合上面的討論，典型的 LZ77 算法應(yīng)當(dāng)不難實(shí)現(xiàn)，我們本章給出的源碼是一個(gè)較為特殊的實(shí)現(xiàn)。
示例程序 lz77.exe 使用對(duì)匹配串和單個(gè)字符分類輸出的模型，輸出匹配串時(shí)，off 采用定長(zhǎng)編碼，len 采用γ編碼。索引結(jié)構(gòu)采用 2 字節(jié)長(zhǎng)字符串的索引，使用 256 * 256 大小的靜態(tài)數(shù)組存儲(chǔ)索引點(diǎn)，每個(gè)索引點(diǎn)指向一個(gè)位置鏈表。鏈表節(jié)點(diǎn)考慮了對(duì) aaaaa... 之類的重復(fù)串的優(yōu)化。
示例程序的獨(dú)特之處在于使用了 64k 大小的固定長(zhǎng)度窗口，窗口不做滑動(dòng)（因此不需要環(huán)形偏移系統(tǒng)，也節(jié)省了刪除索引點(diǎn)的時(shí)間）。壓縮函數(shù)每次只對(duì)最多 64k 長(zhǎng)的數(shù)據(jù)進(jìn)行壓縮，主函數(shù)將原始文件分成 64k 大小的塊逐個(gè)壓縮存儲(chǔ)。使用這種方法首先可以增大匹配的概率，字符串可以在 64k 空間內(nèi)任意尋找最大匹配串，以此提高壓縮效率。其次，這種方法有利于實(shí)現(xiàn)解壓縮的同步。也就是說，利用這種方法分塊壓縮的數(shù)據(jù)，很容易從原始文件中間的任何一個(gè)位置開始解壓縮，這尤其適用于全文檢索系統(tǒng)中全文信息的保存和隨機(jī)讀取。 |
|
|
|
