聲明

　　本論文題目：范式哈夫曼算法的分析與實(shí)現(xiàn)，作者：葉葉，于2010年10月14日在編程論壇上發(fā)表。頁面地址：http:///bbs/view12-29332-1.htm 。

目錄

　　1 前言 2
　　2 理論基礎(chǔ) 2
　　　　2.1 哈夫曼算法 2
　　　　2.2 范式哈夫曼算法 6
　　3 計(jì)算編碼位長 7
　　4 編碼 9
　　5 解碼 9
　　　　5.1 正常解碼 9
　　　　5.2 優(yōu)化解碼 10
　　6 限制編碼位長 11
　　7 碼表二次壓縮 15
　　　　7.1 指數(shù)哥倫布編碼 15
　　　　7.2 范式哈夫曼二次壓縮 17
　　8 測(cè)試與分析 18
　　9 結(jié)束語 20
　　參考文獻(xiàn) 20
　　附錄：項(xiàng)目說明 20
　　　　1 程序項(xiàng)目 20
　　　　2 MemoryBuffer.pas文件 21
　　　　3 CanonicalHuffman.pas文件 21
　　　　4 CanHuf_Debug.pas文件 22

范式哈夫曼算法的分析與實(shí)現(xiàn)

作者：葉葉（網(wǎng)名：yeye55）

　　摘要：全面介紹了范式哈夫曼算法的理論基礎(chǔ)和實(shí)現(xiàn)方式。詳細(xì)討論了編碼位長計(jì)算、限制編碼位長、解碼優(yōu)化、碼表二次壓縮等實(shí)現(xiàn)技術(shù)。并給出了一個(gè)切實(shí)可行的應(yīng)用程序。

　　關(guān)鍵詞：哈夫曼；范式哈夫曼；指數(shù)哥倫布編碼；Delphi

　　中圖分類號(hào)：TP301.6

　　1 前言

　　David A. Huffman于1952年第一次提出了哈夫曼（Huffman）算法[1]，該算法一經(jīng)提出就引起了研究人員的廣泛興趣。哈夫曼算法使用變長前綴編碼來壓縮數(shù)據(jù)。對(duì)于出現(xiàn)次數(shù)較多的符號(hào)使用較短的編碼表示，對(duì)于出現(xiàn)次數(shù)較少的符號(hào)使用較長的編碼表示。哈夫曼算法的性能十分優(yōu)異，即使在很糟糕的情況下都可以獲得不錯(cuò)的壓縮率。但是，哈夫曼算法也有許多缺點(diǎn)。例如：二叉樹大量占用內(nèi)存、碼表過大、編解碼速度過慢等等。

　　Eugene S. Schwartz于1964年提出了范式哈夫曼編碼（Canonical Huffman Code）算法[2]。作為哈夫曼算法的一個(gè)重要的變體，范式哈夫曼算法解決了哈夫曼算法的許多不足之處。范式哈夫曼算法可以根據(jù)編碼位長算出編碼。這樣輸出的碼表就大大的減少了，而且編解碼過程不再需要二叉樹結(jié)構(gòu)。在提高編解碼速度的同時(shí)，內(nèi)存占用也大幅減少。

　　目前范式哈夫曼算法已經(jīng)在數(shù)據(jù)壓縮領(lǐng)域大量的應(yīng)用。本文將詳細(xì)的分析范式哈夫曼算法的理論基礎(chǔ)和實(shí)現(xiàn)方式，并給出一個(gè)在Delphi 7.0下開發(fā)，使用范式哈夫曼算法壓縮數(shù)據(jù)的應(yīng)用程序。

　　2 理論基礎(chǔ)

　　2.1 哈夫曼算法

　　范式哈夫曼算法是哈夫曼算法的一種變體。所以這里先對(duì)哈夫曼算法進(jìn)行介紹，然后再推導(dǎo)出范式哈夫曼算法。

　　哈夫曼算法需要掃描兩遍數(shù)據(jù)。第一遍掃描計(jì)算符號(hào)在數(shù)據(jù)中出現(xiàn)的次數(shù)（以下簡稱“頻度”），然后根據(jù)符號(hào)頻度構(gòu)建一棵哈夫曼二叉樹（以下簡稱“哈夫曼樹”）。最后再次掃描數(shù)據(jù)將符號(hào)按哈夫曼樹進(jìn)行編碼。例如：一份長度為38個(gè)符號(hào)的數(shù)據(jù)，其中一共出現(xiàn)8種符號(hào)，其頻度如表2.1所示：

　　符號(hào) A　B C D　E F G H
　　頻度 10 1 1 11 1 1 8 5

　　表2.1 符號(hào)頻度

　　構(gòu)建哈夫曼樹的過程是這樣的：首先建立一個(gè)由二叉樹構(gòu)成的森林，每個(gè)葉子節(jié)點(diǎn)保存一個(gè)符號(hào)和它們的頻度。每個(gè)分支節(jié)點(diǎn)保存一個(gè)頻度總計(jì)。剛開始的時(shí)候每個(gè)二叉樹都只有葉子節(jié)點(diǎn)。然后對(duì)于森林中所有的二叉樹，以根節(jié)點(diǎn)的頻度作為關(guān)鍵字從小到大排序。排序完成后，將排名第1、2位的二叉樹合并成一棵新的二叉樹。具體做法是：新建一個(gè)根節(jié)點(diǎn)，將排名第1位的二叉樹作為新節(jié)點(diǎn)的左子樹，排名第2位的二叉樹作為新節(jié)點(diǎn)的右子樹，新節(jié)點(diǎn)的頻度等于這兩棵子樹根節(jié)點(diǎn)的頻度之和。合并完成后再進(jìn)行排序，不斷重復(fù)這個(gè)過程，直到所有節(jié)點(diǎn)都合并到一棵二叉樹上。利用表2.1中的頻度數(shù)據(jù)構(gòu)建哈夫曼樹的整個(gè)過程如圖2.1所示。

圖2.1 哈夫曼樹的構(gòu)建過程

　　圖2.1第8步得出的就是哈夫曼樹。現(xiàn)在可以對(duì)這棵哈夫曼樹分配編碼。一般采用左0右1的分配方案，即：為左子樹分配編碼0，為右子樹分配編碼1。注意：如果只是單純的使用哈夫曼算法，不管是采用左0右1還是采用右0左1都是可以正常編解碼的。只要編碼程序和解碼程序都使用相同的編碼方案就不會(huì)出現(xiàn)錯(cuò)誤。但是，本文中要推導(dǎo)出范式哈夫曼算法，所以必需采用左0右1的分配方案。一棵分配了編碼的哈夫曼樹如圖2.2所示。

圖2.2 分配編碼的哈夫曼樹

　　根據(jù)圖2.2中的哈夫曼樹可以得到表2.2中的哈夫曼編碼。哈夫曼算法編解碼的過程其實(shí)就是查樹的過程。編碼一個(gè)符號(hào)時(shí)，先查找該符號(hào)對(duì)應(yīng)的葉子節(jié)點(diǎn)；從葉子節(jié)點(diǎn)開始沿著父節(jié)點(diǎn)向上直到根節(jié)點(diǎn)；記錄下路過每個(gè)節(jié)點(diǎn)的編碼；最終得到的就是符號(hào)的哈夫曼編碼。解碼過程與之相反，從根節(jié)點(diǎn)開始；判斷輸入的位，為0時(shí)向左走，為1時(shí)向右走；當(dāng)遇到葉子節(jié)點(diǎn)時(shí)就可以解碼出一個(gè)符號(hào)。

　　符號(hào) 編碼位長 哈夫曼編碼 范式哈夫曼編碼
　　A　　2　　　　10　　　　 00
　　B　　5　　　　01010　　　11100
　　C　　5　　　　01011　　　11101
　　D　　2　　　　11　　　　 01
　　E　　5　　　　01000　　　11110
　　F　　5　　　　01001　　　11111
　　G　　2　　　　00　　　　 10
　　H　　3　　　　011　　　　110

　　表2.2 哈夫曼編碼和范式哈夫曼編碼

　　從上述的介紹中可以看出哈夫曼算法的一些缺點(diǎn)。首先，編解碼過程都需要建立哈夫曼樹。哈夫曼樹是根據(jù)符號(hào)頻度建立的。這就意味著編碼輸出的時(shí)候必需輸出一份頻度數(shù)據(jù)（以下簡稱“碼表”）以便解碼的時(shí)候可以重建哈夫曼樹。這份碼表將占用輸出數(shù)據(jù)很大的一部分空間。其次，哈夫曼樹將占用大量的內(nèi)存。而且頻繁查樹的效率也不高。另外，哈夫曼編碼具有不確定性。例如，前面講到的左0右1的分配方案；再例如，在構(gòu)建時(shí)采用穩(wěn)定或不穩(wěn)定的排序算法。這都會(huì)影響到最終輸出的哈夫曼編碼。范式哈夫曼算法就是為了解決上述缺點(diǎn)而提出的。

　　2.2 范式哈夫曼算法

　　范式哈夫曼算法采用了一個(gè)巧妙的方法對(duì)哈夫曼樹進(jìn)行了規(guī)范調(diào)整。首先，對(duì)于同一層的節(jié)點(diǎn)，所有的葉子節(jié)點(diǎn)都調(diào)整到左邊。然后，對(duì)于同一層的葉子節(jié)點(diǎn)按照符號(hào)順序從小到大調(diào)整。最后，按照左0右1的方案分配編碼。圖2.2中的哈夫曼樹經(jīng)過這樣的調(diào)整可以得到一棵范式哈夫曼樹（以下簡稱“范式樹”）如圖2.3所示。

圖2.3 范式哈夫曼樹

　　根據(jù)圖2.3中的范式樹可以得到表2.2中的范式哈夫曼編碼。將表2.2中的范式哈夫曼編碼，按照以編碼位長為第1關(guān)鍵字、符號(hào)為第2關(guān)鍵字進(jìn)行排序，可以得到范式哈夫曼編碼表?？梢詫⑾嗤婚L的符號(hào)稱之為同組符號(hào)。在同組符號(hào)之間的排序序號(hào)可以稱之為同組序號(hào)。結(jié)果如表2.3所示。

　　序號(hào) 同組序號(hào) 符號(hào) 位長 編碼
　　0　　0　　　　A　　2　　00
　　1　　1　　　　D　　2　　01
　　2　　2　　　　G　　2　　10
　　3　　0　　　　H　　3　　110
　　4　　0　　　　B　　5　　11100
　　5　　1　　　　C　　5　　11101
　　6　　2　　　　E　　5　　11110
　　7　　3　　　　F　　5　　11111

　　表2.3 范式哈夫曼編碼表

　　觀察圖2.3和表2.3可以得出一些結(jié)論。第一，只要知道一個(gè)符號(hào)的編碼位長就可以知道它在范式樹上的位置。這就意味著在碼表中只要保存每個(gè)符號(hào)的編碼位長即可。編碼位長通常要比符號(hào)頻度小很多，所以碼表的體積就可以減小很多。第二，相同位長的編碼之間都相差1。例如，同組符號(hào)“A”、“D”、“G”的編碼分別為“00”、“01”、“10”。而且，相鄰的不同位長的編碼，對(duì)齊后的高位相差1低位補(bǔ)充0。例如“H”和“B”的編碼分別為“110”和“11100”，高3位相差1，補(bǔ)充2位0。這就意味著編碼可以根據(jù)位長計(jì)算出來。編解碼的過程可以根據(jù)計(jì)算出來的編碼表進(jìn)行，從而加快了編解碼的速度。第三，根據(jù)以上兩點(diǎn)可以發(fā)現(xiàn)，在編碼的過程中，不必再建立范式樹。只要模擬哈夫曼樹的構(gòu)建，計(jì)算出符號(hào)的編碼位長即可。這樣可以加快編碼速度，同時(shí)又能減少內(nèi)存的占用。

　　可以看出，范式哈夫曼算法解決了哈夫曼算法的許多不足之處。以下就來討論范式哈夫曼算法的具體實(shí)現(xiàn)。

　　3 計(jì)算編碼位長

　　先說排序算法。前面講到哈夫曼樹的構(gòu)建過程，其實(shí)就是從一個(gè)有序表中刪除兩個(gè)最小的元素，再插入一個(gè)新的元素。在這種情況下使用堆排序算法（Heap Sort）可以獲得不錯(cuò)的性能。另外，由于只要計(jì)算編碼位長，可以使用一個(gè)數(shù)組模擬構(gòu)建哈夫曼樹的過程。Alistair Moffat在書中描述了一種計(jì)算哈夫曼編碼位長的算法[3]（以下簡稱“M算法”）。設(shè)n為符號(hào)的信息量（Content），M算法使用了一個(gè)2n大小的數(shù)組。利用數(shù)組的左邊保存一個(gè)最小堆結(jié)構(gòu)，利用數(shù)組的右邊保存符號(hào)頻度。在這個(gè)數(shù)組中進(jìn)行數(shù)據(jù)整理，可以模擬出構(gòu)建哈夫曼樹的過程。并且計(jì)算出編碼位長。M算法不僅節(jié)約內(nèi)存，其運(yùn)行效率也相當(dāng)不錯(cuò)。下面就來介紹這種算法。

　　在我們的例子里一共出現(xiàn)了8種符號(hào)，所以n = 8。可以使用下面的代碼建立一個(gè)具有2n個(gè)元素的數(shù)組Buf。

　　Buf : array [0 .. (2 * n) - 1] of Cardinal;

　　假設(shè)符號(hào)“A”的序號(hào)為0、“B”的序號(hào)為1、……、“H”的序號(hào)為7。先將“A”到“H”的符號(hào)頻度依次放入數(shù)組Buf的n到2n - 1位置。Buf的左邊用來建立一個(gè)最小堆結(jié)構(gòu)。左邊的每個(gè)元素都保存一個(gè)指向右邊元素的索引。對(duì)Buf的n到2n - 1元素遍歷一遍就可以構(gòu)建起一個(gè)最小堆，構(gòu)建完成后的數(shù)據(jù)如圖3.1 1)所示。

圖3.1 M算法的數(shù)據(jù)整理

　　根據(jù)最小堆的原理，Buf[0]就是最小的一個(gè)元素。將Buf[0]移動(dòng)到堆的末尾，這里是Buf[7]。然后重新整理堆，結(jié)果如圖3.1 2)所示。再執(zhí)行一次上述操作，結(jié)果如圖3.1 3)所示。這樣，我們就有兩個(gè)需要合并的節(jié)點(diǎn)Buf[7]和Buf[6]對(duì)應(yīng)Buf[9]和Buf[12]。將Buf[9]和Buf[12]相加保存到Buf[7]中，Buf[9]和Buf[12]分別保存對(duì)于Buf[7]的索引7。此時(shí)Buf[7]中已經(jīng)保存了頻度之和，將Buf[7]重新放入堆進(jìn)行整理。過程如圖3.1 4) 5)所示。重復(fù)這個(gè)過程，直到堆中只剩下一個(gè)元素，如圖3.1 6)所示。

　　可以看出，整理完成后Buf的1到2n-1已經(jīng)保存了一棵哈夫曼樹。Buf[1]就是根節(jié)點(diǎn)，后續(xù)元素保存一個(gè)指向父節(jié)點(diǎn)的索引。由于子節(jié)點(diǎn)的編碼位長肯定等于父節(jié)點(diǎn)編碼位長加1。所以可以用一個(gè)簡單的公式算出節(jié)點(diǎn)的編碼位長：Buf[i] = Buf[Buf[i]] + 1。將Buf[1]設(shè)為0。對(duì)Buf的2到2n - 1元素按上述公式遍歷計(jì)算一遍，就可以得到編碼位長。如圖3.1 7)所示。

　　自此，符號(hào)“A”到“H”的編碼位長就保存到Buf的n到2n - 1位置上。

　　4 編碼

　　當(dāng)符號(hào)的編碼位長計(jì)算出來之后，就可以根據(jù)位長為符號(hào)分配編碼?，F(xiàn)在先對(duì)表2.3中的數(shù)據(jù)進(jìn)行統(tǒng)計(jì)。計(jì)算出相同位長的符號(hào)數(shù)量。以及相同位長中第一個(gè)符號(hào)的編碼（以下簡稱“首編碼”）。結(jié)果如表4.1所示。

　　編碼位長 首編碼 符號(hào)數(shù)量
　　2　　　　00　　 3
　　3　　　　110　　1
　　5　　　　11100　4

　　表4.1 位長表

　　綜合分析表2.3和表4.1中的數(shù)據(jù)可以發(fā)現(xiàn)一些規(guī)律。每個(gè)首編碼都等于上個(gè)首編碼加上對(duì)應(yīng)的符號(hào)數(shù)量，再左移相差位。例如，“110”等于“00”加上3再左移1位。在同組符號(hào)之間，符號(hào)編碼等于首編碼加上該符號(hào)的同組序號(hào)。例如，在編碼位長為5的符號(hào)中“E”的序號(hào)是2。“E”的編碼“11110”等于“11100”加上2。

　　在實(shí)現(xiàn)的時(shí)候，由于前面計(jì)算完編碼位長后Buf的0到n - 1位置已經(jīng)不再使用。這時(shí)可以用這部分的空間來保存編碼。注意：這里有一個(gè)前提，編碼的位長不會(huì)超過32位。因?yàn)閿?shù)組Buf使用Cardinal類型保存數(shù)據(jù)。

　　分配編碼的過程是這樣的。首先，對(duì)Buf的n到2n - 1位置的位長數(shù)據(jù)掃描一遍。計(jì)算相同位長的符號(hào)數(shù)量；以及符號(hào)的同組序號(hào)。符號(hào)數(shù)量可以新建一個(gè)數(shù)組保存，同組序號(hào)可以保存到Buf的0到n - 1位置。接著，根據(jù)符號(hào)數(shù)量計(jì)算出首編碼。然后，對(duì)Buf的n到2n - 1位置的位長數(shù)據(jù)再掃描一遍。根據(jù)首編碼和符號(hào)的同組序號(hào)計(jì)算出符號(hào)編碼，保存到Buf的0到n - 1位置。

　　這樣當(dāng)范式哈夫曼算法第2遍掃描數(shù)據(jù)，進(jìn)行編碼的時(shí)候。就可以從Buf中直接獲得編碼以及編碼位長。例如，符號(hào)“A”的編碼就保存在Buf[“A”]中，編碼位長就保存在Buf[“A”+ n]中。

　　5 解碼

　　5.1 正常解碼

　　編碼過程中的符號(hào)編碼是根據(jù)一定的規(guī)律計(jì)算出來的。解碼過程就相當(dāng)于編碼過程的逆運(yùn)算。在解碼之前需要根據(jù)編碼位長建立一份解碼表。如表5.1所示。

　　序號(hào) 編碼位長 首編碼 符號(hào)數(shù)量 符號(hào)索引
　　0　　2　　　　00　　 3　　　　0
　　1　　3　　　　110　　1　　　　3
　　2　　5　　　　11100　4　　　　4

　　表5.1 解碼表

　　表5.1與表4.1類似，只是多了一個(gè)符號(hào)索引。符號(hào)索引對(duì)應(yīng)于表2.3中的序號(hào)。例如，編碼位長為5的符號(hào)，在表2.3中從序號(hào)4開始。那么表5.1中對(duì)應(yīng)符號(hào)索引就等于4。在解碼的時(shí)候不僅需要表5.1中的數(shù)據(jù)，還需要表2.3中經(jīng)過排序的符號(hào)列表。

　　一般情況下，編碼位長會(huì)和壓縮數(shù)據(jù)一起保存。解碼時(shí)先從壓縮數(shù)據(jù)中提取符號(hào)的編碼位長。然后，可以使用基數(shù)排序算法（Radix Sort）計(jì)算符號(hào)列表。同時(shí)計(jì)算出表5.1中的相關(guān)數(shù)據(jù)。具體過程同分配編碼時(shí)類似，這里就不再重復(fù)。

　　建立完解碼表就可以開始解碼了。首先，設(shè)i = 0，從解碼表的第i行開始。根據(jù)編碼位長從數(shù)據(jù)中讀取相應(yīng)長度的位。將讀取數(shù)據(jù)與首編碼相減，假設(shè)差值等于Num。如果Num大于等于符號(hào)數(shù)量，那么將i加1重新開始整個(gè)過程。如果Num小于符號(hào)數(shù)量，那么將符號(hào)索引加Num從符號(hào)列表上的對(duì)應(yīng)位置解碼出一個(gè)符號(hào)。

　　例如，輸入數(shù)據(jù)“11110”。令i = 0，此時(shí)編碼位長為2。讀取2位的數(shù)據(jù)“11”與首編碼相減等于3。3大于等于符號(hào)數(shù)量，于是i = i + 1等于1。此時(shí)編碼位長為3。讀取3位的數(shù)據(jù)“111”與首編碼相減等于1。1大于等于符號(hào)數(shù)量，于是i = i + 1等于2。此時(shí)編碼位長為5。讀取5位的數(shù)據(jù)“11110”與首編碼相減等于2。2小于符號(hào)數(shù)量，2加符號(hào)索引4等于6。從表2.3中可以查到序號(hào)為6的符號(hào)是“E”。從而解碼出符號(hào)“E”。跳過當(dāng)前已經(jīng)解碼的5位數(shù)據(jù)，可以重新開始解碼下一個(gè)符號(hào)。

　　由于前面編碼的時(shí)候假設(shè)了一個(gè)前提，即：編碼位長不會(huì)超過32位。那么在實(shí)現(xiàn)的時(shí)候，可以使用32個(gè)元素的數(shù)組保存表5.1中的數(shù)據(jù)。其中編碼位長隱含在數(shù)組中可以被省略。另外，解碼的時(shí)候可以聲明一個(gè)Cardinal類型的變量，一次性讀取32位的數(shù)據(jù)。在相減的時(shí)候，可以根據(jù)當(dāng)前的編碼位長將變量右移再相減。這樣就不用一點(diǎn)一點(diǎn)的讀取位數(shù)據(jù)。

　　5.2 優(yōu)化解碼

　　從解碼的過程可以看出，解碼最重要的問題就是判斷編碼位長。上述解碼算法需要從最小的編碼位長開始向下查找可能的編碼位長。這種算法并不高效。一種比較簡單的改進(jìn)方案是建立一張k位的快速查詢表（以下簡稱“快表”），其中k稱為快表位長。k位的快表一共有2k個(gè)表項(xiàng)，每個(gè)表項(xiàng)保存一個(gè)符號(hào)和對(duì)應(yīng)的編碼位長?？毂淼男蛱?hào)對(duì)應(yīng)于Num輸入的編碼。

　　快表的建立過程是這樣的：對(duì)于編碼位長小于快表位長的情況，快表序號(hào)高位與編碼相同的表項(xiàng)都設(shè)置為相應(yīng)的符號(hào)。對(duì)于編碼位長等于快表位長的情況，快表序號(hào)與編碼相同的表項(xiàng)設(shè)置為相應(yīng)的符號(hào)。對(duì)于編碼位長小于快表位長的情況，快表序號(hào)與編碼高位相同的表項(xiàng)設(shè)置為相應(yīng)的起始符號(hào)。在我們的例子中使用4位快表的情況，如表5.2所示。

　　序號(hào) 二進(jìn)制序號(hào) 符號(hào) 編碼位長 編碼
　　0　　0000　　　 A　　2　　　　00
　　1　　0001　　　 A　　2　　　　00
　　2　　0010　　　 A　　2　　　　00
　　3　　0011　　　 A　　2　　　　00
　　4　　0100　　　 D　　2　　　　01
　　5　　0101　　　 D　　2　　　　01
　　6　　0110　　　 D　　2　　　　01
　　7　　0111　　　 D　　2　　　　01
　　8　　1000　　　 G　　2　　　　10
　　9　　1001　　　 G　　2　　　　10
　　10　 1010　　　 G　　2　　　　10
　　11　 1011　　　 G　　2　　　　10
　　12　 1100　　　 H　　3　　　　110
　　13　 1101　　　 H　　3　　　　110
　　14　 1110　　　 -　　5　　　　11100
　　15　 1111　　　 -　　5　　　　11110

　　表5.2 快表

　　注意，快表中只保存符號(hào)和編碼位長兩項(xiàng)。使用快表解碼時(shí)，先讀取k位的數(shù)據(jù)。直接將數(shù)據(jù)作為索引在快表中查詢。如果對(duì)應(yīng)表項(xiàng)的編碼位長小于等于快表位長，則直接解碼出符號(hào)。如果對(duì)應(yīng)表項(xiàng)的編碼位長大于快表位長，則從對(duì)應(yīng)的編碼位長開始，然后按照正常解碼的算法進(jìn)行。

　　例如，輸入數(shù)據(jù)“01110”，先讀取4位數(shù)據(jù)“0111”。查詢快表，符號(hào)為“D”，編碼位長為2。2小于4，此時(shí)可以直接解碼出符號(hào)“D”。再例如，輸入數(shù)據(jù)“11110”，先讀取4位數(shù)據(jù)“1111”。查詢快表，符號(hào)不確定，編碼位長為5。5大于4，然后以編碼位長為5開始，按照正常解碼的算法進(jìn)行。可以解碼出“E”。

　　可以看出，快表能夠提高解碼速度。對(duì)于編碼位長小于等于k的符號(hào)一次查表就可以解碼出來。這些符號(hào)通常都是頻度比較高的符號(hào)。即使查表出現(xiàn)編碼位長大于k的情況，即：沒有命中符號(hào)。也可以根據(jù)查到的編碼位長縮短正常解碼時(shí)查詢的范圍。

　　在實(shí)現(xiàn)的時(shí)候，如果對(duì)內(nèi)存占用的要求很高，可以省略快表中的符號(hào)項(xiàng)。解碼時(shí)先從快表中查到對(duì)應(yīng)的編碼位長，再根據(jù)編碼位長進(jìn)行正常的解碼。這樣速度會(huì)略慢一點(diǎn)。另外，在處理實(shí)際數(shù)據(jù)的時(shí)候，可以根據(jù)數(shù)據(jù)特點(diǎn)調(diào)整快表的位長。例如，將快表位長設(shè)為最大編碼位長。在我們的例子里最大編碼位長是5。這樣解碼每一個(gè)符號(hào)都只要一次查表。但是在最大編碼位長較大的時(shí)候，這種方法會(huì)占用大量的內(nèi)存。所以實(shí)現(xiàn)的時(shí)候還要根據(jù)實(shí)際情況調(diào)整。還有，在解碼的時(shí)候同樣可以一次性讀取32位的數(shù)據(jù)。然后根據(jù)變量的高k位進(jìn)行查表。

　　6 限制編碼位長

　　在前面編解碼的時(shí)候都假設(shè)了一個(gè)前提：編碼位長不會(huì)超過32位。如果編碼位長超過了32位，前面的編解碼過程將會(huì)出現(xiàn)錯(cuò)誤。那么哈夫曼編碼位長最長可以達(dá)到多少？這是一個(gè)非常有趣的問題。學(xué)過算法的人都知道斐波那契數(shù)列，那么我們假設(shè)符號(hào)的頻度恰好為一個(gè)斐波那契數(shù)列。符號(hào)對(duì)應(yīng)的頻度如表6.1所示。

　　符號(hào) A B C D E F G　H
　　頻度 1 1 1 3 4 7 11 18

　　表6.1 符號(hào)頻度為斐波那契數(shù)列

　　其中符號(hào)“A”、“B”、“C”的頻度都為1，“D”的頻度為前3個(gè)頻度之和。從“E”開始頻度值為一個(gè)斐波那契數(shù)列。按照這樣的頻度生成的范式樹如圖6.1所示。

圖6.1 單邊范式樹

　　圖6.1中的范式樹可以被稱之為單邊范式樹。注意將它與單邊二叉樹相區(qū)別。根據(jù)上述規(guī)律，假設(shè)信息量為n的符號(hào)，其哈夫曼編碼位長理論上最長可以達(dá)到n - 1位。對(duì)于8位符號(hào)，信息量為256，其哈夫曼編碼位長理論上最長可以達(dá)到255位。這是一個(gè)相當(dāng)驚人的數(shù)據(jù)。但是這僅僅只是理論上的結(jié)果，我們還要考慮現(xiàn)實(shí)一點(diǎn)的問題。

　　當(dāng)實(shí)際編碼位長大于指定編碼位長時(shí)稱之為位長溢出。上面的例子中使用了8種符號(hào)以及一份46個(gè)符號(hào)的數(shù)據(jù)，讓實(shí)際編碼位長達(dá)到了7位。如果要讓編碼位長超過32位，就要使用34種符號(hào)。并構(gòu)造一份長達(dá)12,752,042個(gè)符號(hào)的數(shù)據(jù)。這還只是一份人工數(shù)據(jù)。在現(xiàn)實(shí)的應(yīng)用中，符號(hào)通常用來表示特定的信息。符號(hào)與符號(hào)之間也具有一定的關(guān)系。出現(xiàn)像表6.1那樣的頻度十分罕見。

　　當(dāng)然，出現(xiàn)位長溢出的概率很低不等于不會(huì)出現(xiàn)位長溢出。解決位長溢出的方法無外乎兩種，要么對(duì)計(jì)算出來的位長進(jìn)行限制，要么采用無限制位長的編解碼算法。很明顯采用無限制位長的編解碼算法會(huì)嚴(yán)重拖慢編解碼的速度。那么只有采用限制位長的方法。

　　限制位長的方法也有兩種，第一種方法是在計(jì)算編碼位長之前對(duì)符號(hào)頻度進(jìn)行調(diào)整，使之不會(huì)出現(xiàn)位長溢出；另一種方法是在出現(xiàn)位長溢出后對(duì)位長進(jìn)行調(diào)整，使之滿足要求。限制位長肯定會(huì)影響到壓縮率。第一種方法可以把壓縮率的損失降到最低，第二種方法次之。但第二種方法的速度比第一種方法快很多，而且它只是在出現(xiàn)溢出的時(shí)候才進(jìn)行調(diào)整。所以整體性能比第一種方法高。下面就來介紹第二種方法。

　　首先我們觀察圖2.3中的范式樹，假設(shè)現(xiàn)在要將編碼位長限制到4位。那么調(diào)整需要從最右邊最下層的分支（以下簡稱“右下分支”）開始。根據(jù)哈夫曼樹和范式樹的規(guī)律，右下分支肯定是如圖6.2所示的樣式。

圖6.2 右下分支

　　從圖2.3中的范式樹上查找小于第4層的最右邊的葉子節(jié)點(diǎn)?？梢钥闯鲞@是符號(hào)“H”對(duì)應(yīng)的葉子節(jié)點(diǎn)。將該葉子節(jié)點(diǎn)下放一層，形成一個(gè)分支節(jié)點(diǎn)。原葉子節(jié)點(diǎn)作為新分支節(jié)點(diǎn)的左葉子節(jié)點(diǎn)。將右下分支的左葉子節(jié)點(diǎn)作為新分支節(jié)點(diǎn)的右葉子節(jié)點(diǎn)。將右下分支的右葉子節(jié)點(diǎn)上提一層替換原右下分支節(jié)點(diǎn)。過程如圖6.3 1) 2)所示。

圖6.3 范式樹的調(diào)整

　　上述的調(diào)整可以看出一個(gè)問題：右下分支的葉子節(jié)點(diǎn)應(yīng)該是最下層的節(jié)點(diǎn)，占用最長的位。而該葉子節(jié)點(diǎn)卻被調(diào)整到了較上層，占用較少的位。這樣對(duì)于壓縮率的損失較大。所以還要進(jìn)行下優(yōu)化調(diào)整。優(yōu)化調(diào)整時(shí)遵循這樣一個(gè)原則：在調(diào)整的時(shí)候，盡量保持符號(hào)原先的左右順序不變。在滿足上一條件的情況下，再按照范式樹的規(guī)范進(jìn)行調(diào)整。優(yōu)化調(diào)整后的范式樹如圖6.3 3)所示。注意，由于此時(shí)調(diào)整還未完成，所以符號(hào)“H”排在了“B”和“C”的左邊。這是按照原先的左右順序排列。調(diào)整后又會(huì)出現(xiàn)一個(gè)右下分支，可以繼續(xù)進(jìn)行調(diào)整。直到所有的節(jié)點(diǎn)都不低于4層。最后調(diào)整完成的范式樹如圖6.3 4)所示。

　　當(dāng)然，范式哈夫曼算法在實(shí)現(xiàn)的時(shí)候并沒有生成一棵完整的樹。那么調(diào)整就要在表2.3中的數(shù)據(jù)中進(jìn)行。仔細(xì)觀察表2.3中的數(shù)據(jù)可以發(fā)現(xiàn)，位于表末尾的兩個(gè)符號(hào)就是要進(jìn)行調(diào)整的右下分支。這就意味著可以在表中進(jìn)行調(diào)整，以模擬出上述在樹中調(diào)整的過程。注意，表2.3中的數(shù)據(jù)是經(jīng)過排序的。

　　在表中調(diào)整位長的過程是這樣的：首先，從表的末尾向上查找位長小于限制位長的序號(hào)。這里是序號(hào)3。將該位長加1，并設(shè)置倒數(shù)第二位的位長為該位長。然后將倒數(shù)第一位的位長減1。最后再對(duì)位長數(shù)據(jù)按大小整理。整理時(shí)要注意保持符號(hào)的順序不變。原先序號(hào)6的位長被整理到了序號(hào)4。原先序號(hào)7的位長被整理到了序號(hào)5。這時(shí)可以判斷末尾的位長是否大于限制位長。如果不大于，則調(diào)整完成。如果大于，就從原先序號(hào)3的下一位序號(hào)4開始向上查找位長小于限制位長的序號(hào)。并重復(fù)剛才的調(diào)整過程，直到末尾的位長小于等于限制位長。整個(gè)過程如表6.2所示。

　　序號(hào) 符號(hào) 位長　 位長調(diào)整
　　　　　　　　　 第一輪 第二輪
　　0　　A　　2　　2 2　　2 2
　　1　　D　　2　　2 2　　2 2
　　2　　G　　2　　2 2　　3 3
　　3　　H　　3　　4 4　　4 3
　　4　　B　　5　　5 4　　4 4
　　5　　C　　5　　5 4　　4 4
　　6　　E　　5　　4 5　　3 4
　　7　　F　　5　　4 5　　4 4

　　表6.2 位長調(diào)整

　　可以看出在表中調(diào)整可以完美的模擬出在樹中的調(diào)整，而且速度還更快。觀察調(diào)整完的位長后可以發(fā)現(xiàn)，“B”、“C”、“E”、“F”的位長減小了，“H”的位長沒有改變，而“G”的位長增加了。這說明該算法在控制壓縮率損失方面并不優(yōu)秀。但是，由于每次調(diào)整都是從較下層的節(jié)點(diǎn)開始。如果下層節(jié)點(diǎn)能夠騰出足夠的位置，對(duì)于上層節(jié)點(diǎn)將不會(huì)有任何影響。這意味著，雖然該算法在壓縮率上會(huì)有損失，但仍然是可以被接受的。另外，由于只是在出現(xiàn)位長溢出的時(shí)候進(jìn)行調(diào)整。對(duì)于沒有溢出的壓縮來講，將不會(huì)有任何影響。

　　7 碼表二次壓縮

　　7.1 指數(shù)哥倫布編碼

　　一般情況下，碼表數(shù)據(jù)會(huì)和壓縮輸出數(shù)據(jù)一起保存。范式哈夫曼算法只需要保存編碼位長數(shù)據(jù)。位長已經(jīng)限制在了32。考慮到有的符號(hào)沒有出現(xiàn)，它們的位長為0。那么，位長數(shù)據(jù)的范圍就在0至32之間，每個(gè)位長數(shù)據(jù)需要6位的空間。假設(shè)8位符號(hào)總共輸出256個(gè)位長數(shù)據(jù)，需要占用192個(gè)字節(jié)。如果使用16位符號(hào)，則需要占用49,152個(gè)字節(jié)。所以，對(duì)于位長數(shù)據(jù)進(jìn)行再次壓縮還是很有必要的。

　　從前面幾節(jié)的描述中可以發(fā)現(xiàn)，位長數(shù)據(jù)都是一些數(shù)值比較小的數(shù)據(jù)。對(duì)于這種數(shù)據(jù)使用指數(shù)哥倫布編碼（Exp-Golomb Coding，以下簡稱“EG編碼”）壓縮是比較合適的。Jukka Teuhola于1978年提出了EG編碼[4]。EG編碼也是一種變長前綴編碼，它可以用來壓縮非負(fù)整數(shù)的數(shù)值數(shù)據(jù)。EG編碼利用較短的編碼表示較小的數(shù)值，利用較長的編碼表示較大的數(shù)值。EG編碼還可以設(shè)定一個(gè)階數(shù)k，根據(jù)待壓縮數(shù)據(jù)的數(shù)值范圍調(diào)整k，可以獲得更好的壓縮率。EG編碼由前綴m (m≥0)個(gè)0、分隔符“1”、后綴m + k (k≥0)個(gè)位組成。數(shù)值0至9的EG編碼如表7.1所示。

　　　　 數(shù)值　　 k = 0　　 k = 1　　k = 2
　　十進(jìn)制 二進(jìn)制 m 編碼　　m 編碼　 m 編碼
　　0　　　0000　 0　　1　　0　 10　 0　100
　　1　　　0001　 1　 010　 0　 11　 0　101
　　2　　　0010　 1　 011　 1　0100　0　110
　　3　　　0011　 2　00100　1　0101　0　111
　　4　　　0100　 2　00101　1　0110　1 01000
　　5　　　0101　 2　00110　1　0111　1 01001
　　6　　　0110　 2　00111　2 001000 1 01010
　　7　　　0111　 3 0001000 2 001001 1 01011
　　8　　　1000　 3 0001001 2 001010 1 01100
　　9　　　1001　 3 0001010 2 001011 1 01101

　　表7.1 指數(shù)哥倫布編碼

　　對(duì)于位長數(shù)據(jù)的壓縮，使用0階的EG編碼比較合適。0階EC編碼的編碼過程是這樣的：對(duì)于輸入的數(shù)值數(shù)據(jù)，例如Num。先將Num加1，然后計(jì)算Num最高位的“1”位于第幾位，將該數(shù)減1即是m。這相當(dāng)于是在計(jì)算log2Num。最后輸出m個(gè)“0”以及Num的低m + 1位。解碼過程與之相反：先從輸入數(shù)據(jù)中讀取“0”，直到遇到“1”。計(jì)算總共讀取了幾個(gè)“0”，賦值給m。然后從“1”開始讀取m + 1個(gè)位，賦值給Num。最后將Num減1，即可解碼出數(shù)值。

　　EG編碼可以有效的壓縮數(shù)值數(shù)據(jù)，但是在實(shí)現(xiàn)的時(shí)候還有幾個(gè)問題需要解決。首先觀察表2.2中的編碼位長數(shù)據(jù)?？梢园l(fā)現(xiàn)一點(diǎn)：數(shù)值較大的數(shù)據(jù)出現(xiàn)次數(shù)較多。比如位長5出現(xiàn)了4次。這是由于二叉樹的性質(zhì)決定的。對(duì)于一般的二叉樹來說，下層葉子節(jié)點(diǎn)總是比上層葉子節(jié)點(diǎn)多。這就意味著，在位長數(shù)據(jù)中數(shù)值較大的數(shù)據(jù)占大多數(shù)。這將不利于EG編碼壓縮。解決方法是對(duì)位長數(shù)據(jù)進(jìn)行調(diào)整。根據(jù)剛才分析的特點(diǎn)，可以用以下的公式對(duì)編碼位長數(shù)據(jù)進(jìn)行調(diào)整：

　　調(diào)整后數(shù)值 = 最大位長 - 當(dāng)前位長 + 1

　　將表2.2中的位長數(shù)據(jù)按照上述公式進(jìn)行調(diào)整，結(jié)果如表7.2所示。

　　符號(hào)　　　 A B C D E F G H
　　位長數(shù)值　 2 5 5 2 5 5 2 3
　　調(diào)整后數(shù)值 4 1 1 4 1 1 4 3

　　表7.2 位長數(shù)據(jù)調(diào)整

　　雖然在我們的例子里，這樣的調(diào)整沒有得到很好的效果。但是在符號(hào)較多的位長表中，這樣的調(diào)整可以讓數(shù)據(jù)整體變小，并且讓較下層的葉子節(jié)點(diǎn)使用較小的數(shù)值。這就可以充分發(fā)揮出EG編碼的特點(diǎn)。

　　在實(shí)現(xiàn)的時(shí)候還有另外一個(gè)問題。在有些數(shù)據(jù)中，符號(hào)并沒有完全出現(xiàn)。例如，對(duì)于8位符號(hào)總共有256種符號(hào)。在壓縮英文文檔或程序源代碼的時(shí)候，全文中大約只出現(xiàn)了80至90種符號(hào)。有大量的符號(hào)沒有出現(xiàn)，位長為0，如果直接保存也會(huì)占用大量空間。這時(shí)可以用RLE（Run Length Encoding）算法壓縮一下。RLE算法是利用數(shù)據(jù)和重復(fù)次數(shù)來替換重復(fù)的數(shù)據(jù)。由于在現(xiàn)實(shí)的情況下，不為0的位長重復(fù)的可能性很小。所以這里只對(duì)位長為0的數(shù)據(jù)進(jìn)行壓縮。具體做法是：如果遇到為0的位長就輸出0，然后輸出0重復(fù)的次數(shù)。即使為0的位長只出現(xiàn)了一次，也要輸出一個(gè)0和一個(gè)1。一個(gè)例子如表7.3所示。

　　位長 5 8 0 6 5 0 0 0 0 7
　　輸出 5 8 0 1 6 5 0 4 7

　　表7.3 位長數(shù)據(jù)的RLE壓縮

　　綜上所述，在輸出碼表數(shù)據(jù)的時(shí)候，先輸出最大位長。然后再依次輸出調(diào)整后的位長數(shù)據(jù)。如果遇到為0的位長就輸出0，然后輸出0重復(fù)的次數(shù)。所有輸出的數(shù)據(jù)都使用EG編碼。在我實(shí)現(xiàn)的程序里，將該壓縮方案稱之為“G方案”。經(jīng)測(cè)試，在使用8位符號(hào)的情況下。對(duì)于英文文檔，碼表可以壓縮到大約60至80字節(jié)。對(duì)于出現(xiàn)符號(hào)較多的文檔，碼表可以壓縮到大約110至160字節(jié)。

　　7.2 范式哈夫曼二次壓縮

　　使用G方案可以看出一個(gè)缺點(diǎn)：雖然對(duì)位長數(shù)據(jù)進(jìn)行了調(diào)整，但是這種調(diào)整不一定是最優(yōu)的。按照G方案的調(diào)整，最底層的葉子節(jié)點(diǎn)使用最小的數(shù)值。但是最底層不一定是出現(xiàn)最多葉子節(jié)點(diǎn)的層。所以更好的方案是將位長數(shù)據(jù)使用范式哈夫曼算法再壓縮一遍。這稱之為二次壓縮。二次壓縮又會(huì)產(chǎn)生一份新的碼表，稱為二次碼表。這份碼表再使用G方案壓縮。

　　可以根據(jù)當(dāng)前最大位長為二次壓縮的范式哈夫曼算法指定符號(hào)信息量。符號(hào)信息量等于最大位長加1。在我們的例子里可以設(shè)為6。即：位長數(shù)據(jù)只在0至5的范圍內(nèi)變化。另外，二次壓縮同樣使用RLE算法壓縮為0的位長數(shù)據(jù)。但是，有一點(diǎn)需要注意。RLE算法需要輸出重復(fù)次數(shù)。0位長出現(xiàn)的重復(fù)次數(shù)通常變化很大，特別是使用較多符號(hào)的數(shù)據(jù)中。所以重復(fù)次數(shù)不使用范式哈夫曼編碼，而使用EG編碼。

　　綜上所述，在輸出碼表數(shù)據(jù)的時(shí)候，先根據(jù)最大位長建立范式哈夫曼編碼器。掃描一遍位長數(shù)據(jù)，統(tǒng)計(jì)頻度分配編碼。隨后用EG編碼輸出最大位長。接著用G方案輸出二次碼表。然后再依次用范式哈夫曼編碼輸出位長數(shù)據(jù)。如果遇到為0的位長就用范式哈夫曼編碼輸出0，然后用EG編碼輸出0重復(fù)的次數(shù)。在我實(shí)現(xiàn)的程序里，將該壓縮方案稱之為“H方案”。

　　現(xiàn)在使用卡爾加里語料庫（The Calgary Corpus[5]）中的18個(gè)文件，進(jìn)行H方案的碼表壓縮性能測(cè)試。測(cè)試分別使用8位符號(hào)和16位符號(hào)兩種情況。測(cè)試輸出碼表壓縮后的大小，占用多少位以及大約相當(dāng)于多少字節(jié)。測(cè)試結(jié)果如表7.4所示。

　　文件　 8位符號(hào)　16位符號(hào)
　　　　　 位　字節(jié) 位　　 字節(jié)
　　bib　　463　57 10,287 1,285
　　book1　505　63 13,054 1,631
　　book2　482　60 20,382 2,547
　　geo　　707　88 15,983 1,997
　　news　 447　55 24,779 3,097
　　obj1　 787　98 30,695 3,836
　　obj2　 892 111 49,884 6,235
　　paper1 475　59 11,465 1,433
　　paper2 497　62　9,957 1,244
　　paper3 426　53　9,051 1,131
　　paper4 432　54　6,574　 821
　　paper5 456　57　7,758　 969
　　paper6 462　57 10,702 1,337
　　pic　　955 119 21,444 2,680
　　progc　427　53 11,648 1,456
　　progl　446　55　9,151 1,143
　　progp　483　60 11,214 1,401
　　trans　502　62 14,762 1,845

　　表7.4 碼表壓縮測(cè)試

　　注意，表7.4中的字節(jié)數(shù)據(jù)是由位數(shù)據(jù)直接整除8得到的。觀察表7.4中的數(shù)據(jù)可以發(fā)現(xiàn)，在使用8位符號(hào)的情況下。對(duì)于英文文檔或程序源代碼，如“book1”、“progc”等文件，碼表可以壓縮到大約55至65字節(jié)。對(duì)于出現(xiàn)符號(hào)較多的文檔，如“obj1”、“pic”等文件，碼表可以壓縮到大約100至120字節(jié)。

　　8 測(cè)試與分析

　　范式哈夫曼算法的實(shí)現(xiàn)程序在Delphi 7.0下開發(fā)，編譯通過并調(diào)試正常。測(cè)試程序的計(jì)算機(jī)使用Intel 2.66GHz單核CPU，DDR400 512MB內(nèi)存，Windows 2000 SP4操作系統(tǒng)。測(cè)試程序壓縮文件的時(shí)候，將文件全部讀入內(nèi)存進(jìn)行壓縮。壓縮后的數(shù)據(jù)再寫入到文件中。解壓縮的過程也是如此。算法計(jì)時(shí)的時(shí)候，讀寫文件的時(shí)間并沒有計(jì)算在內(nèi)。只計(jì)算單純算法的耗時(shí)。另外，程序中使用API函數(shù)GetTickCount進(jìn)行計(jì)時(shí)。按照微軟官方的說法，該函數(shù)有15ms（15毫秒）的誤差。

　　現(xiàn)在使用卡爾加里語料庫（The Calgary Corpus[5]）中的18個(gè)文件，以及大型語料庫（The Large Corpus[5]）中的3個(gè)文件，進(jìn)行測(cè)試。測(cè)試結(jié)果如表8.1和表8.2所示。

　　文件　 輸入大小 輸出大小 壓縮率 bpc 編碼耗時(shí) 解碼耗時(shí)
　　bib　　111,261B　72,824B 34％ 5.236bpc 16ms　0ms
　　book1　768,771B 438,444B 42％ 4.563bpc 31ms 31ms
　　book2　610,856B 368,364B 39％ 4.824bpc 16ms 16ms
　　geo　　102,400B　72,648B 29％ 5.676bpc　0ms　0ms
　　news　 377,109B 246,456B 34％ 5.228bpc 16ms 15ms
　　obj1　　21,504B　16,156B 24％ 6.010bpc　0ms　0ms
　　obj2　 246,814B 194,212B 21％ 6.295bpc 15ms 16ms
　　paper1　53,161B　33,400B 37％ 5.026bpc　0ms　0ms
　　paper2　82,199B　47,684B 41％ 4.641bpc　0ms　0ms
　　paper3　46,526B　27,332B 41％ 4.700bpc　0ms　0ms
　　paper4　13,286B　 7,920B 40％ 4.769bpc　0ms　0ms
　　paper5　11,954B　 7,492B 37％ 5.014bpc　0ms　0ms
　　paper6　38,105B　24,088B 36％ 5.057bpc　0ms　0ms
　　pic　　513,216B 106,676B 79％ 1.663bpc　0ms 15ms
　　progc　 39,611B　25,972B 34％ 5.245bpc　0ms　0ms
　　progl　 71,646B　43,044B 39％ 4.806bpc　0ms　0ms
　　progp　 49,379B　30,280B 38％ 4.906bpc　0ms　0ms
　　trans　 93,695B　65,288B 30％ 5.575bpc　0ms 16ms
　　總計(jì) 3,251,493B 1,828,280B 43％ 4.498bpc

　　表8.1 卡爾加里語料庫壓縮測(cè)試

　　文件　　　　 輸入大小　 輸出大小　 壓縮率 bpc 編碼耗時(shí) 解碼耗時(shí)
　　bible.txt　　4,047,392B 2,218,508B 45％ 4.385bpc 110ms 93ms
　　E.coli　　　 4,638,690B 1,159,688B 74％ 2.000bpc 125ms 125ms
　　world192.txt 2,473,400B 1,558,664B 36％ 5.041bpc 62ms 63ms
　　總計(jì)　　　　11,159,482B 4,936,860B 55％ 3.539bpc

　　表8.2 大型語料庫壓縮測(cè)試

　　以上測(cè)試數(shù)據(jù)中的壓縮率以及bpc（Bit Per Char）采用以下公式進(jìn)行計(jì)算：

　　壓縮率 = ((輸入大小 - 輸出大小) * 100) div 輸入大小
　　bpc = (輸出大小 * 8) / 輸入大小

　　測(cè)試程序使用8位符號(hào)進(jìn)行壓縮，保存碼表的時(shí)候使用了H方案，在解壓縮的時(shí)候使用了8位快表。

　　觀察測(cè)試數(shù)據(jù)可以發(fā)現(xiàn)，范式哈夫曼算法的速度還是很快的。對(duì)于數(shù)百KB的數(shù)據(jù)，無論是壓縮還是解壓縮耗時(shí)都在15ms左右。對(duì)于數(shù)MB的數(shù)據(jù)，耗時(shí)也保持在100ms左右。另外，范式哈夫曼算法的壓縮率在同類算法中還是不錯(cuò)的。在同類算法中范式哈夫曼算法的綜合性能最高。但是，范式哈夫曼算法也有許多不足之處。最大的缺點(diǎn)就是它需要掃描兩遍數(shù)據(jù)。對(duì)于實(shí)時(shí)數(shù)據(jù)壓縮，這個(gè)缺點(diǎn)是致命的。而且，從上一節(jié)的表7.4中可以發(fā)現(xiàn)，范式哈夫曼算法仍然需要輸出一份碼表。對(duì)于使用百萬量級(jí)符號(hào)的數(shù)據(jù)，這份碼表會(huì)占用很大的數(shù)據(jù)空間。

　　9 結(jié)束語

　　范式哈夫曼算法以其優(yōu)異的性能被廣泛的應(yīng)用在數(shù)據(jù)壓縮領(lǐng)域。本文詳細(xì)介紹了范式哈夫曼算法的理論基礎(chǔ)和各種實(shí)現(xiàn)技術(shù)的細(xì)節(jié)。并給出了一個(gè)切實(shí)可行的應(yīng)用程序。希望本文能夠?qū)嚎s算法的研究人員有所幫助。

　　參考文獻(xiàn)

　　[1] David A. Huffman, A Method for the Construction of Minimum-Redundancy Codes, Proceedings of the IRE, 1952, 40(9), 1098-1101.

　　[2] Eugene S. Schwartz, Bruce Kallick, Generating a cannonical prefix encoding, Communications of the ACM, 1964, 7(3), 166-169.

　　[3] Lan H. Witten, Alistair Moffat, Timothy C. Bell, 梁斌(譯), 深入搜索引擎, 北京: 電子工業(yè)出版社, 2009, 44-51, 421-432.

　　[4] Jukka Teuhola, A Compression Method for Clustered Bit-Vectors, Information Processing Letters, 1978, 7, 308-311.

　　[5] The Canterbury Corpus, http://corpus./descriptions/.

　　附錄：項(xiàng)目說明

　　1 程序項(xiàng)目

　　本程序項(xiàng)目是論文《范式哈夫曼算法的分析與實(shí)現(xiàn)》（以下簡稱“《范》”）的配套程序。本程序項(xiàng)目同時(shí)作為免費(fèi)開源程序進(jìn)行發(fā)布。本程序項(xiàng)目中的代碼無需任何授權(quán)或許可即可用于個(gè)人和商業(yè)目的。使用者一切后果自負(fù)。

　　本程序項(xiàng)目在Delphi 7.0下開發(fā)，編譯通過并且調(diào)試正常。本程序項(xiàng)目提供了一個(gè)文件到文件的，范示哈夫曼算法的壓縮程序。本程序項(xiàng)目中還提供了相關(guān)測(cè)試代碼，以分析范式哈夫曼算法的運(yùn)行過程。

　　本程序項(xiàng)目中的主要文件及相關(guān)說明如表1.1所示。

　　文件　　　　　　　　 說明
　　Project1.dpr　　　　 項(xiàng)目主文件
　　Project1.exe　　　　 項(xiàng)目可執(zhí)行文件
　　Unit1.pas　　　　　　主窗口單元文件
　　Unit1.dfm　　　　　　主窗口窗體文件
　　MemoryBuffer.pas　　 內(nèi)存緩沖區(qū)管理單元文件
　　CanonicalHuffman.pas 范式哈夫曼算法實(shí)現(xiàn)單元文件
　　CanHuf_Debug.pas　　 帶測(cè)試信息實(shí)現(xiàn)的單元文件
　　示范數(shù)據(jù).txt　　　　 文《范》中的例子數(shù)據(jù)

　　表1.1 項(xiàng)目主要文件說明

　　在程序項(xiàng)目中MemoryBuffer.pas和CanonicalHuffman.pas兩個(gè)文件是核心文件。在這兩個(gè)文件中實(shí)現(xiàn)了論文《范》中描述的所有算法。同時(shí)，這兩個(gè)文件也可以獨(dú)立使用。將這兩個(gè)文件添加到其它項(xiàng)目中，調(diào)用其中的相關(guān)函數(shù)就可以實(shí)現(xiàn)數(shù)據(jù)壓縮。

　　2 MemoryBuffer.pas文件

　　由于范式哈夫曼算法輸出變長位的數(shù)據(jù)，所以我編寫了這個(gè)單元文件，提供了位讀寫的可擴(kuò)展緩沖區(qū)操作。在這個(gè)單元文件里我定義了一個(gè)緩沖區(qū)類型TMBBuffer。同時(shí)，我編寫了一系列的函數(shù)，提供對(duì)這個(gè)類型緩沖區(qū)的讀寫操作。通過這些函數(shù)可以以字節(jié)為單位讀寫緩沖區(qū)，也可以以位為單位讀寫緩沖區(qū)。還可以把緩沖區(qū)中的內(nèi)容導(dǎo)入或?qū)С龅轿募?。向緩沖區(qū)寫入數(shù)據(jù)時(shí)，如果緩沖區(qū)不足，這些函數(shù)還可以擴(kuò)展緩沖區(qū)。另外注明一點(diǎn)。出于性能的考慮，這些函數(shù)在讀寫位時(shí)將緩沖區(qū)視為Cardinal類型構(gòu)成的數(shù)組。讀寫位時(shí)從Cardinal元素的高位向低位讀寫。

　　這些函數(shù)中比較重要的有MBWriteBit和MBReadBit兩個(gè)函數(shù)。MBWriteBit函數(shù)負(fù)責(zé)將Cardinal類型數(shù)據(jù)的指定位寫入到緩沖區(qū)中。而MBReadBit函數(shù)負(fù)責(zé)從緩沖區(qū)中讀取指定的位數(shù)據(jù)。在范式哈夫曼算法編解碼的過程中，主要調(diào)用這兩個(gè)函數(shù)完成位數(shù)據(jù)的讀寫操作。

　　另外兩個(gè)比較重要的函數(shù)是MBEncodeEG和MBDecodeEG。這兩個(gè)函數(shù)實(shí)現(xiàn)了0階的EG編碼（指數(shù)哥倫布編碼）。MBEncodeEG可以將一個(gè)Cardinal類型的數(shù)值數(shù)據(jù)進(jìn)行編碼并寫入到緩沖區(qū)中，MBDecodeEG可以從緩沖區(qū)中解碼出一個(gè)數(shù)值數(shù)據(jù)。在進(jìn)行范式哈夫曼算法的碼表壓縮時(shí)，主要調(diào)用這兩個(gè)函數(shù)完成EG編碼的輸入和輸出。

　　單元文件中還有許多其它函數(shù)。我在每個(gè)函數(shù)實(shí)現(xiàn)部分的開頭，添加了相應(yīng)的說明注釋。有興趣的讀者可以到單元文件中查看，這里不再重復(fù)。

　　3 CanonicalHuffman.pas文件

　　我在這個(gè)單元文件里編寫了范式哈夫曼算法的實(shí)現(xiàn)代碼。在這個(gè)單元文件中一共定義了3個(gè)類。其中，TCHEncode實(shí)現(xiàn)了編碼過程，TCHDecode實(shí)現(xiàn)了解碼過程，TCHCoding提供了對(duì)TCHEncode和TCHDecode的簡單封裝。

　　TCHEncode類實(shí)現(xiàn)了范式哈夫曼算法的編碼過程。注意，TCHEncode類不負(fù)責(zé)符號(hào)頻度的統(tǒng)計(jì)工作。頻度統(tǒng)計(jì)工作應(yīng)該由調(diào)用TCHEncode類的代碼完成。在TCHEncode類中的AllocCode方法實(shí)現(xiàn)了編碼位長計(jì)算和編碼分配兩個(gè)過程。對(duì)應(yīng)于論文《范》中的第3節(jié)和第4節(jié)。TCHEncode類中的LengthLimited方法實(shí)現(xiàn)了限制編碼位長的過程。對(duì)應(yīng)于論文《范》中的第6節(jié)。TCHEncode類中的SaveBitLenG和SaveBitLenH兩個(gè)方法實(shí)現(xiàn)了碼表二次壓縮的過程。對(duì)應(yīng)于論文《范》中的第7節(jié)。其中，SaveBitLenG使用G方案，對(duì)應(yīng)第7.1節(jié)；SaveBitLenH使用H方案，對(duì)應(yīng)第7.2節(jié)。TCHEncode類的其它方法說明見單元文件中的相關(guān)注釋。

　　TCHDecode類實(shí)現(xiàn)了范式哈夫曼算法的解碼過程。TCHDecode類中的Construct方法實(shí)現(xiàn)了解碼表的構(gòu)建和快表的構(gòu)建兩個(gè)過程。對(duì)應(yīng)于論文《范》中的第5節(jié)。TCHDecode類中的LoadBitLenG和LoadBitLenH兩個(gè)方法實(shí)現(xiàn)了碼表解壓縮的過程。對(duì)應(yīng)于論文《范》中的第7節(jié)。TCHDecode類的其它方法說明見單元文件中的相關(guān)注釋。

　　TCHCoding類實(shí)現(xiàn)了范式哈夫曼算法的編解碼過程。TCHCoding類是對(duì)TCHEncode和TCHDecode的簡單封裝。TCHCoding類提供了一個(gè)緩沖區(qū)到緩沖區(qū)的壓縮與解壓縮過程。TCHCoding類中的Encode方法是以字節(jié)為單位從緩沖區(qū)中讀取數(shù)據(jù)進(jìn)行壓縮，然后保存到另一緩沖區(qū)中。TCHCoding類中的Decode方法是從緩沖區(qū)中讀取壓縮數(shù)據(jù)進(jìn)行解壓縮，然后保存到另一緩沖區(qū)中。TCHCoding類中的Encode16和Decode16兩個(gè)方法與上述兩個(gè)方法類似。只不過這兩個(gè)方法是以雙字節(jié)（Word）為單位進(jìn)行數(shù)據(jù)的壓縮與解壓縮。在Unit1.pas單元文件中的測(cè)試程序就是調(diào)用TCHCoding類中的相關(guān)方法完成文件壓縮與解壓縮的。

　　4 CanHuf_Debug.pas文件

　　本單元文件是在CanonicalHuffman.pas單元文件的基礎(chǔ)上添加了測(cè)試數(shù)據(jù)輸出代碼。本單元文件中的基本功能與CanonicalHuffman.pas單元文件完全相同。除此之外，在調(diào)用本單元中的一些方法的時(shí)候，這些方法會(huì)向Unit1.pas單元中的Form1.Memo1輸出測(cè)試信息。正是由于如此，本單元文件必需與Unit1.pas單元文件一同使用。

　　在本單元文件中，TCHEncode. AllocCode會(huì)輸出分配編碼表的內(nèi)容。TCHEncode. LengthLimited會(huì)輸出位長整理的整個(gè)過程。TCHEncode類中的SaveBitLenG和SaveBitLenH會(huì)輸出碼表壓縮情況。TCHDecode. Construct會(huì)輸出解碼表和快表的內(nèi)容。TCHDecode類中的LoadBitLenG和LoadBitLenH會(huì)輸出碼表解壓縮情況。

　　在本單元文件中可以修改常量CH_MAXLENGTH，這個(gè)常量就是限制位長的大小。在測(cè)試的時(shí)候可以將這個(gè)常量調(diào)小，以觀察TCHEncode. LengthLimited方法的調(diào)整過程。

　　在本程序項(xiàng)目中帶有一個(gè)例子文件：示范數(shù)據(jù).txt文件。這個(gè)文件中的數(shù)據(jù)與論文《范》中的例子相對(duì)應(yīng)。其符號(hào)與編碼的對(duì)應(yīng)關(guān)系如表4.1所示。

　　符號(hào) A　 B　 C　 D　 E　 F　 G　 H
　　編碼 $41 $42 $43 $44 $45 $46 $47 $48

　　表4.1 符號(hào)與編碼對(duì)應(yīng)關(guān)系

　　現(xiàn)在對(duì)該文件進(jìn)行測(cè)試。在程序中選擇“范式哈夫曼算法（8位符號(hào)測(cè)試）”算法。注意：由于采用H方案保存碼表，輸出信息會(huì)有兩份。一份是數(shù)據(jù)壓縮的編碼表，一份是碼表壓縮的編碼表。程序輸出結(jié)果如下：

==================================================================
使用范式哈夫曼算法壓縮（8位符號(hào)測(cè)試）...
從：E:\示范數(shù)據(jù).txt
到：E:\Temp.pack

數(shù)據(jù)種數(shù)：8
最大位長：5
編碼表：
序號(hào) 符號(hào) 位長 編碼
　0 $41　2 00
　1 $44　2 01
　2 $47　2 10
　3 $48　3 110
　4 $42　5 11100
　5 $43　5 11101
　6 $45　5 11110
　7 $46　5 11111

數(shù)據(jù)種數(shù)：4
最大位長：3
編碼表：
序號(hào) 符號(hào) 位長 編碼
　0 $05　1 0
　1 $02　2 10
　2 $00　3 110
　3 $03　3 111

設(shè)定符號(hào)容量：6種
實(shí)際符號(hào)種數(shù)：4種
最大編碼位長：3位
輸出碼表大?。℅）：27位≈3字節(jié)

設(shè)定符號(hào)容量：256種
實(shí)際符號(hào)種數(shù)：8種
最大編碼位長：5位
輸出碼表大?。℉）：79位≈9字節(jié)

編碼器內(nèi)存占用：2080B ≈ 2KB ≈ 0MB

編碼器內(nèi)存占用：80B ≈ 0KB ≈ 0MB

操作完成，耗時(shí)：15
壓縮前：38 字節(jié)
壓縮后：28 字節(jié)
壓縮率：26％ 5.895bpc
==================================================================

==================================================================
使用范式哈夫曼算法解壓縮（8位符號(hào)測(cè)試）...
從：E:\Temp.pack
到：E:\Temp.data

數(shù)據(jù)種數(shù)：4
符號(hào)順序表：
　0 $05
　1 $02
　2 $00
　3 $03

最大位長：3
解碼表：
序號(hào) 首編碼 符號(hào)數(shù)量 符號(hào)索引
　1 0　　 1　 0
　2 10　　1　 1
　3 110　 2　 2

快表位長：3
快表：
序號(hào) 二進(jìn)制序號(hào) 符號(hào) 編碼位長
　0 000 $05　 1
　1 001 $05　 1
　2 010 $05　 1
　3 011 $05　 1
　4 100 $02　 2
　5 101 $02　 2
　6 110 $00　 3
　7 111 $03　 3

輸入碼表大小（G）：27位≈3字節(jié)

數(shù)據(jù)種數(shù)：8
符號(hào)順序表：
　0 $41
　1 $44
　2 $47
　3 $48
　4 $42
　5 $43
　6 $45
　7 $46

最大位長：5
解碼表：
序號(hào) 首編碼 符號(hào)數(shù)量 符號(hào)索引
　1 0　　　 0　 0
　2 00　　　3　 0
　3 110　　 1　 3
　4 1110　　0　 4
　5 11100　 4　 4

快表位長：5
快表：
序號(hào) 二進(jìn)制序號(hào) 符號(hào) 編碼位長
　0 00000 $41　 2
　1 00001 $41　 2
　2 00010 $41　 2
　3 00011 $41　 2
　4 00100 $41　 2
　5 00101 $41　 2
　6 00110 $41　 2
　7 00111 $41　 2
　8 01000 $44　 2
　9 01001 $44　 2
 10 01010 $44　 2
 11 01011 $44　 2
 12 01100 $44　 2
 13 01101 $44　 2
 14 01110 $44　 2
 15 01111 $44　 2
 16 10000 $47　 2
 17 10001 $47　 2
 18 10010 $47　 2
 19 10011 $47　 2
 20 10100 $47　 2
 21 10101 $47　 2
 22 10110 $47　 2
 23 10111 $47　 2
 24 11000 $48　 3
 25 11001 $48　 3
 26 11010 $48　 3
 27 11011 $48　 3
 28 11100 $42　 5
 29 11101 $43　 5
 30 11110 $45　 5
 31 11111 $46　 5

輸入碼表大?。℉）：107位≈13字節(jié)

解碼器內(nèi)存占用：1604B ≈ 1KB ≈ 0MB

解碼器內(nèi)存占用：484B ≈ 0KB ≈ 0MB

操作完成，耗時(shí)：47
==================================================================

比較文件：
E:\示范數(shù)據(jù).txt
E:\Temp.data
長度38字節(jié)，比較一致。
　　
　　感興趣的讀者可以修改CanHuf_Debug.pas文件中的相關(guān)參數(shù)，例如：CH_MAXLENGTH，觀察程序測(cè)試輸出的不同變化。

葉葉
2010年6月22日