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