|
本論文題目：范式哈夫曼算法的分析與實(shí)現(xiàn)，作者：葉葉，于2010年10月14日在編程論壇上發(fā)表。頁(yè)面地址：http://programbbs.com/bbs/view12-29332-1.htm 。 目錄 1 前言 2 范式哈夫曼算法的分析與實(shí)現(xiàn) 作者：葉葉（網(wǎng)名：yeye55） 摘要：全面介紹了范式哈夫曼算法的理論基礎(chǔ)和實(shí)現(xiàn)方式。詳細(xì)討論了編碼位長(zhǎng)計(jì)算、限制編碼位長(zhǎng)、解碼優(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)提出就引起了研究人員的廣泛興趣。哈夫曼算法使用變長(zhǎng)前綴編碼來(lái)壓縮數(shù)據(jù)。對(duì)于出現(xiàn)次數(shù)較多的符號(hào)使用較短的編碼表示，對(duì)于出現(xiàn)次數(shù)較少的符號(hào)使用較長(zhǎng)的編碼表示。哈夫曼算法的性能十分優(yōu)異，即使在很糟糕的情況下都可以獲得不錯(cuò)的壓縮率。但是，哈夫曼算法也有許多缺點(diǎn)。例如：二叉樹(shù)大量占用內(nèi)存、碼表過(guò)大、編解碼速度過(guò)慢等等。 Eugene S. Schwartz于1964年提出了范式哈夫曼編碼（Canonical Huffman Code）算法[2]。作為哈夫曼算法的一個(gè)重要的變體，范式哈夫曼算法解決了哈夫曼算法的許多不足之處。范式哈夫曼算法可以根據(jù)編碼位長(zhǎng)算出編碼。這樣輸出的碼表就大大的減少了，而且編解碼過(guò)程不再需要二叉樹(shù)結(jié)構(gòu)。在提高編解碼速度的同時(shí)，內(nèi)存占用也大幅減少。 目前范式哈夫曼算法已經(jīng)在數(shù)據(jù)壓縮領(lǐng)域大量的應(yīng)用。本文將詳細(xì)的分析范式哈夫曼算法的理論基礎(chǔ)和實(shí)現(xiàn)方式，并給出一個(gè)在Delphi 7.0下開(kāi)發(fā)，使用范式哈夫曼算法壓縮數(shù)據(jù)的應(yīng)用程序。 2 理論基礎(chǔ) 2.1 哈夫曼算法 范式哈夫曼算法是哈夫曼算法的一種變體。所以這里先對(duì)哈夫曼算法進(jìn)行介紹，然后再推導(dǎo)出范式哈夫曼算法。 哈夫曼算法需要掃描兩遍數(shù)據(jù)。第一遍掃描計(jì)算符號(hào)在數(shù)據(jù)中出現(xiàn)的次數(shù)（以下簡(jiǎn)稱“頻度”），然后根據(jù)符號(hào)頻度構(gòu)建一棵哈夫曼二叉樹(shù)（以下簡(jiǎn)稱“哈夫曼樹(shù)”）。最后再次掃描數(shù)據(jù)將符號(hào)按哈夫曼樹(shù)進(jìn)行編碼。例如：一份長(zhǎng)度為38個(gè)符號(hào)的數(shù)據(jù)，其中一共出現(xiàn)8種符號(hào)，其頻度如表2.1所示： 符號(hào) A B C D E F G H 表2.1 符號(hào)頻度 構(gòu)建哈夫曼樹(shù)的過(guò)程是這樣的：首先建立一個(gè)由二叉樹(shù)構(gòu)成的森林，每個(gè)葉子節(jié)點(diǎn)保存一個(gè)符號(hào)和它們的頻度。每個(gè)分支節(jié)點(diǎn)保存一個(gè)頻度總計(jì)。剛開(kāi)始的時(shí)候每個(gè)二叉樹(shù)都只有葉子節(jié)點(diǎn)。然后對(duì)于森林中所有的二叉樹(shù)，以根節(jié)點(diǎn)的頻度作為關(guān)鍵字從小到大排序。排序完成后，將排名第1、2位的二叉樹(shù)合并成一棵新的二叉樹(shù)。具體做法是：新建一個(gè)根節(jié)點(diǎn)，將排名第1位的二叉樹(shù)作為新節(jié)點(diǎn)的左子樹(shù)，排名第2位的二叉樹(shù)作為新節(jié)點(diǎn)的右子樹(shù)，新節(jié)點(diǎn)的頻度等于這兩棵子樹(shù)根節(jié)點(diǎn)的頻度之和。合并完成后再進(jìn)行排序，不斷重復(fù)這個(gè)過(guò)程，直到所有節(jié)點(diǎn)都合并到一棵二叉樹(shù)上。利用表2.1中的頻度數(shù)據(jù)構(gòu)建哈夫曼樹(shù)的整個(gè)過(guò)程如圖2.1所示。
圖2.1第8步得出的就是哈夫曼樹(shù)?，F(xiàn)在可以對(duì)這棵哈夫曼樹(shù)分配編碼。一般采用左0右1的分配方案，即：為左子樹(shù)分配編碼0，為右子樹(shù)分配編碼1。注意：如果只是單純的使用哈夫曼算法，不管是采用左0右1還是采用右0左1都是可以正常編解碼的。只要編碼程序和解碼程序都使用相同的編碼方案就不會(huì)出現(xiàn)錯(cuò)誤。但是，本文中要推導(dǎo)出范式哈夫曼算法，所以必需采用左0右1的分配方案。一棵分配了編碼的哈夫曼樹(shù)如圖2.2所示。
根據(jù)圖2.2中的哈夫曼樹(shù)可以得到表2.2中的哈夫曼編碼。哈夫曼算法編解碼的過(guò)程其實(shí)就是查樹(shù)的過(guò)程。編碼一個(gè)符號(hào)時(shí)，先查找該符號(hào)對(duì)應(yīng)的葉子節(jié)點(diǎn)；從葉子節(jié)點(diǎn)開(kāi)始沿著父節(jié)點(diǎn)向上直到根節(jié)點(diǎn)；記錄下路過(guò)每個(gè)節(jié)點(diǎn)的編碼；最終得到的就是符號(hào)的哈夫曼編碼。解碼過(guò)程與之相反，從根節(jié)點(diǎn)開(kāi)始；判斷輸入的位，為0時(shí)向左走，為1時(shí)向右走；當(dāng)遇到葉子節(jié)點(diǎn)時(shí)就可以解碼出一個(gè)符號(hào)。 符號(hào) 編碼位長(zhǎng) 哈夫曼編碼 范式哈夫曼編碼 表2.2 哈夫曼編碼和范式哈夫曼編碼 從上述的介紹中可以看出哈夫曼算法的一些缺點(diǎn)。首先，編解碼過(guò)程都需要建立哈夫曼樹(shù)。哈夫曼樹(shù)是根據(jù)符號(hào)頻度建立的。這就意味著編碼輸出的時(shí)候必需輸出一份頻度數(shù)據(jù)（以下簡(jiǎn)稱“碼表”）以便解碼的時(shí)候可以重建哈夫曼樹(shù)。這份碼表將占用輸出數(shù)據(jù)很大的一部分空間。其次，哈夫曼樹(shù)將占用大量的內(nèi)存。而且頻繁查樹(shù)的效率也不高。另外，哈夫曼編碼具有不確定性。例如，前面講到的左0右1的分配方案；再例如，在構(gòu)建時(shí)采用穩(wěn)定或不穩(wěn)定的排序算法。這都會(huì)影響到最終輸出的哈夫曼編碼。范式哈夫曼算法就是為了解決上述缺點(diǎn)而提出的。 2.2 范式哈夫曼算法 范式哈夫曼算法采用了一個(gè)巧妙的方法對(duì)哈夫曼樹(shù)進(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中的哈夫曼樹(shù)經(jīng)過(guò)這樣的調(diào)整可以得到一棵范式哈夫曼樹(shù)（以下簡(jiǎn)稱“范式樹(shù)”）如圖2.3所示。
根據(jù)圖2.3中的范式樹(shù)可以得到表2.2中的范式哈夫曼編碼。將表2.2中的范式哈夫曼編碼，按照以編碼位長(zhǎng)為第1關(guān)鍵字、符號(hào)為第2關(guān)鍵字進(jìn)行排序，可以得到范式哈夫曼編碼表?？梢詫⑾嗤婚L(zhǎng)的符號(hào)稱之為同組符號(hào)。在同組符號(hào)之間的排序序號(hào)可以稱之為同組序號(hào)。結(jié)果如表2.3所示。 序號(hào) 同組序號(hào) 符號(hào) 位長(zhǎng) 編碼 表2.3 范式哈夫曼編碼表 觀察圖2.3和表2.3可以得出一些結(jié)論。第一，只要知道一個(gè)符號(hào)的編碼位長(zhǎng)就可以知道它在范式樹(shù)上的位置。這就意味著在碼表中只要保存每個(gè)符號(hào)的編碼位長(zhǎng)即可。編碼位長(zhǎng)通常要比符號(hào)頻度小很多，所以碼表的體積就可以減小很多。第二，相同位長(zhǎng)的編碼之間都相差1。例如，同組符號(hào)“A”、“D”、“G”的編碼分別為“00”、“01”、“10”。而且，相鄰的不同位長(zhǎng)的編碼，對(duì)齊后的高位相差1低位補(bǔ)充0。例如“H”和“B”的編碼分別為“110”和“11100”，高3位相差1，補(bǔ)充2位0。這就意味著編碼可以根據(jù)位長(zhǎng)計(jì)算出來(lái)。編解碼的過(guò)程可以根據(jù)計(jì)算出來(lái)的編碼表進(jìn)行，從而加快了編解碼的速度。第三，根據(jù)以上兩點(diǎn)可以發(fā)現(xiàn)，在編碼的過(guò)程中，不必再建立范式樹(shù)。只要模擬哈夫曼樹(shù)的構(gòu)建，計(jì)算出符號(hào)的編碼位長(zhǎng)即可。這樣可以加快編碼速度，同時(shí)又能減少內(nèi)存的占用。 可以看出，范式哈夫曼算法解決了哈夫曼算法的許多不足之處。以下就來(lái)討論范式哈夫曼算法的具體實(shí)現(xiàn)。 3 計(jì)算編碼位長(zhǎng) 先說(shuō)排序算法。前面講到哈夫曼樹(shù)的構(gòu)建過(guò)程，其實(shí)就是從一個(gè)有序表中刪除兩個(gè)最小的元素，再插入一個(gè)新的元素。在這種情況下使用堆排序算法（Heap Sort）可以獲得不錯(cuò)的性能。另外，由于只要計(jì)算編碼位長(zhǎng)，可以使用一個(gè)數(shù)組模擬構(gòu)建哈夫曼樹(shù)的過(guò)程。Alistair Moffat在書中描述了一種計(jì)算哈夫曼編碼位長(zhǎng)的算法[3]（以下簡(jiǎn)稱“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)建哈夫曼樹(shù)的過(guò)程。并且計(jì)算出編碼位長(zhǎng)。M算法不僅節(jié)約內(nèi)存，其運(yùn)行效率也相當(dāng)不錯(cuò)。下面就來(lái)介紹這種算法。 在我們的例子里一共出現(xiàn)了8種符號(hào)，所以n = 8?？梢允褂孟旅娴拇a建立一個(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的左邊用來(lái)建立一個(gè)最小堆結(jié)構(gòu)。左邊的每個(gè)元素都保存一個(gè)指向右邊元素的索引。對(duì)Buf的n到2n - 1元素遍歷一遍就可以構(gòu)建起一個(gè)最小堆，構(gòu)建完成后的數(shù)據(jù)如圖3.1 1)所示。
根據(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)行整理。過(guò)程如圖3.1 4) 5)所示。重復(fù)這個(gè)過(guò)程，直到堆中只剩下一個(gè)元素，如圖3.1 6)所示。 可以看出，整理完成后Buf的1到2n-1已經(jīng)保存了一棵哈夫曼樹(shù)。Buf[1]就是根節(jié)點(diǎn)，后續(xù)元素保存一個(gè)指向父節(jié)點(diǎn)的索引。由于子節(jié)點(diǎn)的編碼位長(zhǎng)肯定等于父節(jié)點(diǎn)編碼位長(zhǎng)加1。所以可以用一個(gè)簡(jiǎn)單的公式算出節(jié)點(diǎn)的編碼位長(zhǎng)：Buf[i] = Buf[Buf[i]] + 1。將Buf[1]設(shè)為0。對(duì)Buf的2到2n - 1元素按上述公式遍歷計(jì)算一遍，就可以得到編碼位長(zhǎng)。如圖3.1 7)所示。 自此，符號(hào)“A”到“H”的編碼位長(zhǎng)就保存到Buf的n到2n - 1位置上。 4 編碼 當(dāng)符號(hào)的編碼位長(zhǎng)計(jì)算出來(lái)之后，就可以根據(jù)位長(zhǎng)為符號(hào)分配編碼?，F(xiàn)在先對(duì)表2.3中的數(shù)據(jù)進(jìn)行統(tǒng)計(jì)。計(jì)算出相同位長(zhǎng)的符號(hào)數(shù)量。以及相同位長(zhǎng)中第一個(gè)符號(hào)的編碼（以下簡(jiǎn)稱“首編碼”）。結(jié)果如表4.1所示。 編碼位長(zhǎng) 首編碼 符號(hào)數(shù)量 表4.1 位長(zhǎng)表 綜合分析表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)。例如，在編碼位長(zhǎng)為5的符號(hào)中“E”的序號(hào)是2?！癊”的編碼“11110”等于“11100”加上2。 在實(shí)現(xiàn)的時(shí)候，由于前面計(jì)算完編碼位長(zhǎng)后Buf的0到n - 1位置已經(jīng)不再使用。這時(shí)可以用這部分的空間來(lái)保存編碼。注意：這里有一個(gè)前提，編碼的位長(zhǎng)不會(huì)超過(guò)32位。因?yàn)閿?shù)組Buf使用Cardinal類型保存數(shù)據(jù)。 分配編碼的過(guò)程是這樣的。首先，對(duì)Buf的n到2n - 1位置的位長(zhǎng)數(shù)據(jù)掃描一遍。計(jì)算相同位長(zhǎng)的符號(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位置的位長(zhǎng)數(shù)據(jù)再掃描一遍。根據(jù)首編碼和符號(hào)的同組序號(hào)計(jì)算出符號(hào)編碼，保存到Buf的0到n - 1位置。 這樣當(dāng)范式哈夫曼算法第2遍掃描數(shù)據(jù)，進(jìn)行編碼的時(shí)候。就可以從Buf中直接獲得編碼以及編碼位長(zhǎng)。例如，符號(hào)“A”的編碼就保存在Buf[“A”]中，編碼位長(zhǎng)就保存在Buf[“A”+ n]中。 5 解碼 5.1 正常解碼 編碼過(guò)程中的符號(hào)編碼是根據(jù)一定的規(guī)律計(jì)算出來(lái)的。解碼過(guò)程就相當(dāng)于編碼過(guò)程的逆運(yùn)算。在解碼之前需要根據(jù)編碼位長(zhǎng)建立一份解碼表。如表5.1所示。 序號(hào) 編碼位長(zhǎng) 首編碼 符號(hào)數(shù)量 符號(hào)索引 表5.1 解碼表 表5.1與表4.1類似，只是多了一個(gè)符號(hào)索引。符號(hào)索引對(duì)應(yīng)于表2.3中的序號(hào)。例如，編碼位長(zhǎng)為5的符號(hào)，在表2.3中從序號(hào)4開(kāi)始。那么表5.1中對(duì)應(yīng)符號(hào)索引就等于4。在解碼的時(shí)候不僅需要表5.1中的數(shù)據(jù)，還需要表2.3中經(jīng)過(guò)排序的符號(hào)列表。 一般情況下，編碼位長(zhǎng)會(huì)和壓縮數(shù)據(jù)一起保存。解碼時(shí)先從壓縮數(shù)據(jù)中提取符號(hào)的編碼位長(zhǎng)。然后，可以使用基數(shù)排序算法（Radix Sort）計(jì)算符號(hào)列表。同時(shí)計(jì)算出表5.1中的相關(guān)數(shù)據(jù)。具體過(guò)程同分配編碼時(shí)類似，這里就不再重復(fù)。 建立完解碼表就可以開(kāi)始解碼了。首先，設(shè)i = 0，從解碼表的第i行開(kāi)始。根據(jù)編碼位長(zhǎng)從數(shù)據(jù)中讀取相應(yīng)長(zhǎng)度的位。將讀取數(shù)據(jù)與首編碼相減，假設(shè)差值等于Num。如果Num大于等于符號(hào)數(shù)量，那么將i加1重新開(kāi)始整個(gè)過(guò)程。如果Num小于符號(hào)數(shù)量，那么將符號(hào)索引加Num從符號(hào)列表上的對(duì)應(yīng)位置解碼出一個(gè)符號(hào)。 例如，輸入數(shù)據(jù)“11110”。令i = 0，此時(shí)編碼位長(zhǎng)為2。讀取2位的數(shù)據(jù)“11”與首編碼相減等于3。3大于等于符號(hào)數(shù)量，于是i = i + 1等于1。此時(shí)編碼位長(zhǎng)為3。讀取3位的數(shù)據(jù)“111”與首編碼相減等于1。1大于等于符號(hào)數(shù)量，于是i = i + 1等于2。此時(shí)編碼位長(zhǎng)為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”。跳過(guò)當(dāng)前已經(jīng)解碼的5位數(shù)據(jù)，可以重新開(kāi)始解碼下一個(gè)符號(hào)。 由于前面編碼的時(shí)候假設(shè)了一個(gè)前提，即：編碼位長(zhǎng)不會(huì)超過(guò)32位。那么在實(shí)現(xiàn)的時(shí)候，可以使用32個(gè)元素的數(shù)組保存表5.1中的數(shù)據(jù)。其中編碼位長(zhǎng)隱含在數(shù)組中可以被省略。另外，解碼的時(shí)候可以聲明一個(gè)Cardinal類型的變量，一次性讀取32位的數(shù)據(jù)。在相減的時(shí)候，可以根據(jù)當(dāng)前的編碼位長(zhǎng)將變量右移再相減。這樣就不用一點(diǎn)一點(diǎn)的讀取位數(shù)據(jù)。 5.2 優(yōu)化解碼 從解碼的過(guò)程可以看出，解碼最重要的問(wèn)題就是判斷編碼位長(zhǎng)。上述解碼算法需要從最小的編碼位長(zhǎng)開(kāi)始向下查找可能的編碼位長(zhǎng)。這種算法并不高效。一種比較簡(jiǎn)單的改進(jìn)方案是建立一張k位的快速查詢表（以下簡(jiǎn)稱“快表”），其中k稱為快表位長(zhǎng)。k位的快表一共有2k個(gè)表項(xiàng)，每個(gè)表項(xiàng)保存一個(gè)符號(hào)和對(duì)應(yīng)的編碼位長(zhǎng)?？毂淼男蛱?hào)對(duì)應(yīng)于Num輸入的編碼。 快表的建立過(guò)程是這樣的：對(duì)于編碼位長(zhǎng)小于快表位長(zhǎng)的情況，快表序號(hào)高位與編碼相同的表項(xiàng)都設(shè)置為相應(yīng)的符號(hào)。對(duì)于編碼位長(zhǎng)等于快表位長(zhǎng)的情況，快表序號(hào)與編碼相同的表項(xiàng)設(shè)置為相應(yīng)的符號(hào)。對(duì)于編碼位長(zhǎng)小于快表位長(zhǎng)的情況，快表序號(hào)與編碼高位相同的表項(xiàng)設(shè)置為相應(yīng)的起始符號(hào)。在我們的例子中使用4位快表的情況，如表5.2所示。 序號(hào) 二進(jìn)制序號(hào) 符號(hào) 編碼位長(zhǎng) 編碼 表5.2 快表 注意，快表中只保存符號(hào)和編碼位長(zhǎng)兩項(xiàng)。使用快表解碼時(shí)，先讀取k位的數(shù)據(jù)。直接將數(shù)據(jù)作為索引在快表中查詢。如果對(duì)應(yīng)表項(xiàng)的編碼位長(zhǎng)小于等于快表位長(zhǎng)，則直接解碼出符號(hào)。如果對(duì)應(yīng)表項(xiàng)的編碼位長(zhǎng)大于快表位長(zhǎng)，則從對(duì)應(yīng)的編碼位長(zhǎng)開(kāi)始，然后按照正常解碼的算法進(jìn)行。 例如，輸入數(shù)據(jù)“01110”，先讀取4位數(shù)據(jù)“0111”。查詢快表，符號(hào)為“D”，編碼位長(zhǎng)為2。2小于4，此時(shí)可以直接解碼出符號(hào)“D”。再例如，輸入數(shù)據(jù)“11110”，先讀取4位數(shù)據(jù)“1111”。查詢快表，符號(hào)不確定，編碼位長(zhǎng)為5。5大于4，然后以編碼位長(zhǎng)為5開(kāi)始，按照正常解碼的算法進(jìn)行?？梢越獯a出“E”。 可以看出，快表能夠提高解碼速度。對(duì)于編碼位長(zhǎng)小于等于k的符號(hào)一次查表就可以解碼出來(lái)。這些符號(hào)通常都是頻度比較高的符號(hào)。即使查表出現(xiàn)編碼位長(zhǎng)大于k的情況，即：沒(méi)有命中符號(hào)。也可以根據(jù)查到的編碼位長(zhǎng)縮短正常解碼時(shí)查詢的范圍。 在實(shí)現(xiàn)的時(shí)候，如果對(duì)內(nèi)存占用的要求很高，可以省略快表中的符號(hào)項(xiàng)。解碼時(shí)先從快表中查到對(duì)應(yīng)的編碼位長(zhǎng)，再根據(jù)編碼位長(zhǎng)進(jìn)行正常的解碼。這樣速度會(huì)略慢一點(diǎn)。另外，在處理實(shí)際數(shù)據(jù)的時(shí)候，可以根據(jù)數(shù)據(jù)特點(diǎn)調(diào)整快表的位長(zhǎng)。例如，將快表位長(zhǎng)設(shè)為最大編碼位長(zhǎng)。在我們的例子里最大編碼位長(zhǎng)是5。這樣解碼每一個(gè)符號(hào)都只要一次查表。但是在最大編碼位長(zhǎng)較大的時(shí)候，這種方法會(huì)占用大量的內(nèi)存。所以實(shí)現(xiàn)的時(shí)候還要根據(jù)實(shí)際情況調(diào)整。還有，在解碼的時(shí)候同樣可以一次性讀取32位的數(shù)據(jù)。然后根據(jù)變量的高k位進(jìn)行查表。 6 限制編碼位長(zhǎng) 在前面編解碼的時(shí)候都假設(shè)了一個(gè)前提：編碼位長(zhǎng)不會(huì)超過(guò)32位。如果編碼位長(zhǎng)超過(guò)了32位，前面的編解碼過(guò)程將會(huì)出現(xiàn)錯(cuò)誤。那么哈夫曼編碼位長(zhǎng)最長(zhǎng)可以達(dá)到多少？這是一個(gè)非常有趣的問(wèn)題。學(xué)過(guò)算法的人都知道斐波那契數(shù)列，那么我們假設(shè)符號(hào)的頻度恰好為一個(gè)斐波那契數(shù)列。符號(hào)對(duì)應(yīng)的頻度如表6.1所示。 符號(hào) A B C D E F G H 表6.1 符號(hào)頻度為斐波那契數(shù)列 其中符號(hào)“A”、“B”、“C”的頻度都為1，“D”的頻度為前3個(gè)頻度之和。從“E”開(kāi)始頻度值為一個(gè)斐波那契數(shù)列。按照這樣的頻度生成的范式樹(shù)如圖6.1所示。
圖6.1中的范式樹(shù)可以被稱之為單邊范式樹(shù)。注意將它與單邊二叉樹(shù)相區(qū)別。根據(jù)上述規(guī)律，假設(shè)信息量為n的符號(hào)，其哈夫曼編碼位長(zhǎng)理論上最長(zhǎng)可以達(dá)到n - 1位。對(duì)于8位符號(hào)，信息量為256，其哈夫曼編碼位長(zhǎng)理論上最長(zhǎng)可以達(dá)到255位。這是一個(gè)相當(dāng)驚人的數(shù)據(jù)。但是這僅僅只是理論上的結(jié)果，我們還要考慮現(xiàn)實(shí)一點(diǎn)的問(wèn)題。 當(dāng)實(shí)際編碼位長(zhǎng)大于指定編碼位長(zhǎng)時(shí)稱之為位長(zhǎng)溢出。上面的例子中使用了8種符號(hào)以及一份46個(gè)符號(hào)的數(shù)據(jù)，讓實(shí)際編碼位長(zhǎng)達(dá)到了7位。如果要讓編碼位長(zhǎng)超過(guò)32位，就要使用34種符號(hào)。并構(gòu)造一份長(zhǎng)達(dá)12,752,042個(gè)符號(hào)的數(shù)據(jù)。這還只是一份人工數(shù)據(jù)。在現(xiàn)實(shí)的應(yīng)用中，符號(hào)通常用來(lái)表示特定的信息。符號(hào)與符號(hào)之間也具有一定的關(guān)系。出現(xiàn)像表6.1那樣的頻度十分罕見(jiàn)。 當(dāng)然，出現(xiàn)位長(zhǎng)溢出的概率很低不等于不會(huì)出現(xiàn)位長(zhǎng)溢出。解決位長(zhǎng)溢出的方法無(wú)外乎兩種，要么對(duì)計(jì)算出來(lái)的位長(zhǎng)進(jìn)行限制，要么采用無(wú)限制位長(zhǎng)的編解碼算法。很明顯采用無(wú)限制位長(zhǎng)的編解碼算法會(huì)嚴(yán)重拖慢編解碼的速度。那么只有采用限制位長(zhǎng)的方法。 限制位長(zhǎng)的方法也有兩種，第一種方法是在計(jì)算編碼位長(zhǎng)之前對(duì)符號(hào)頻度進(jìn)行調(diào)整，使之不會(huì)出現(xiàn)位長(zhǎng)溢出；另一種方法是在出現(xiàn)位長(zhǎng)溢出后對(duì)位長(zhǎng)進(jìn)行調(diào)整，使之滿足要求。限制位長(zhǎng)肯定會(huì)影響到壓縮率。第一種方法可以把壓縮率的損失降到最低，第二種方法次之。但第二種方法的速度比第一種方法快很多，而且它只是在出現(xiàn)溢出的時(shí)候才進(jìn)行調(diào)整。所以整體性能比第一種方法高。下面就來(lái)介紹第二種方法。 首先我們觀察圖2.3中的范式樹(shù)，假設(shè)現(xiàn)在要將編碼位長(zhǎng)限制到4位。那么調(diào)整需要從最右邊最下層的分支（以下簡(jiǎn)稱“右下分支”）開(kāi)始。根據(jù)哈夫曼樹(shù)和范式樹(shù)的規(guī)律，右下分支肯定是如圖6.2所示的樣式。
從圖2.3中的范式樹(shù)上查找小于第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)。過(guò)程如圖6.3 1) 2)所示。
上述的調(diào)整可以看出一個(gè)問(wèn)題：右下分支的葉子節(jié)點(diǎn)應(yīng)該是最下層的節(jié)點(diǎn)，占用最長(zhǎng)的位。而該葉子節(jié)點(diǎn)卻被調(diào)整到了較上層，占用較少的位。這樣對(duì)于壓縮率的損失較大。所以還要進(jìn)行下優(yōu)化調(diào)整。優(yōu)化調(diào)整時(shí)遵循這樣一個(gè)原則：在調(diào)整的時(shí)候，盡量保持符號(hào)原先的左右順序不變。在滿足上一條件的情況下，再按照范式樹(shù)的規(guī)范進(jìn)行調(diào)整。優(yōu)化調(diào)整后的范式樹(shù)如圖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)整完成的范式樹(shù)如圖6.3 4)所示。 當(dāng)然，范式哈夫曼算法在實(shí)現(xiàn)的時(shí)候并沒(méi)有生成一棵完整的樹(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)整，以模擬出上述在樹(shù)中調(diào)整的過(guò)程。注意，表2.3中的數(shù)據(jù)是經(jīng)過(guò)排序的。 在表中調(diào)整位長(zhǎng)的過(guò)程是這樣的：首先，從表的末尾向上查找位長(zhǎng)小于限制位長(zhǎng)的序號(hào)。這里是序號(hào)3。將該位長(zhǎng)加1，并設(shè)置倒數(shù)第二位的位長(zhǎng)為該位長(zhǎng)。然后將倒數(shù)第一位的位長(zhǎng)減1。最后再對(duì)位長(zhǎng)數(shù)據(jù)按大小整理。整理時(shí)要注意保持符號(hào)的順序不變。原先序號(hào)6的位長(zhǎng)被整理到了序號(hào)4。原先序號(hào)7的位長(zhǎng)被整理到了序號(hào)5。這時(shí)可以判斷末尾的位長(zhǎng)是否大于限制位長(zhǎng)。如果不大于，則調(diào)整完成。如果大于，就從原先序號(hào)3的下一位序號(hào)4開(kāi)始向上查找位長(zhǎng)小于限制位長(zhǎng)的序號(hào)。并重復(fù)剛才的調(diào)整過(guò)程，直到末尾的位長(zhǎng)小于等于限制位長(zhǎng)。整個(gè)過(guò)程如表6.2所示。 序號(hào) 符號(hào) 位長(zhǎng) 位長(zhǎng)調(diào)整 表6.2 位長(zhǎng)調(diào)整 可以看出在表中調(diào)整可以完美的模擬出在樹(shù)中的調(diào)整，而且速度還更快。觀察調(diào)整完的位長(zhǎng)后可以發(fā)現(xiàn)，“B”、“C”、“E”、“F”的位長(zhǎng)減小了，“H”的位長(zhǎng)沒(méi)有改變，而“G”的位長(zhǎng)增加了。這說(shuō)明該算法在控制壓縮率損失方面并不優(yōu)秀。但是，由于每次調(diào)整都是從較下層的節(jié)點(diǎn)開(kāi)始。如果下層節(jié)點(diǎn)能夠騰出足夠的位置，對(duì)于上層節(jié)點(diǎn)將不會(huì)有任何影響。這意味著，雖然該算法在壓縮率上會(huì)有損失，但仍然是可以被接受的。另外，由于只是在出現(xiàn)位長(zhǎng)溢出的時(shí)候進(jìn)行調(diào)整。對(duì)于沒(méi)有溢出的壓縮來(lái)講，將不會(huì)有任何影響。 7 碼表二次壓縮 7.1 指數(shù)哥倫布編碼 一般情況下，碼表數(shù)據(jù)會(huì)和壓縮輸出數(shù)據(jù)一起保存。范式哈夫曼算法只需要保存編碼位長(zhǎng)數(shù)據(jù)。位長(zhǎng)已經(jīng)限制在了32?？紤]到有的符號(hào)沒(méi)有出現(xiàn)，它們的位長(zhǎng)為0。那么，位長(zhǎng)數(shù)據(jù)的范圍就在0至32之間，每個(gè)位長(zhǎng)數(shù)據(jù)需要6位的空間。假設(shè)8位符號(hào)總共輸出256個(gè)位長(zhǎng)數(shù)據(jù)，需要占用192個(gè)字節(jié)。如果使用16位符號(hào)，則需要占用49,152個(gè)字節(jié)。所以，對(duì)于位長(zhǎng)數(shù)據(jù)進(jìn)行再次壓縮還是很有必要的。 從前面幾節(jié)的描述中可以發(fā)現(xiàn)，位長(zhǎng)數(shù)據(jù)都是一些數(shù)值比較小的數(shù)據(jù)。對(duì)于這種數(shù)據(jù)使用指數(shù)哥倫布編碼（Exp-Golomb Coding，以下簡(jiǎn)稱“EG編碼”）壓縮是比較合適的。Jukka Teuhola于1978年提出了EG編碼[4]。EG編碼也是一種變長(zhǎng)前綴編碼，它可以用來(lái)壓縮非負(fù)整數(shù)的數(shù)值數(shù)據(jù)。EG編碼利用較短的編碼表示較小的數(shù)值，利用較長(zhǎng)的編碼表示較大的數(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 表7.1 指數(shù)哥倫布編碼 對(duì)于位長(zhǎng)數(shù)據(jù)的壓縮，使用0階的EG編碼比較合適。0階EC編碼的編碼過(guò)程是這樣的：對(duì)于輸入的數(shù)值數(shù)據(jù)，例如Num。先將Num加1，然后計(jì)算Num最高位的“1”位于第幾位，將該數(shù)減1即是m。這相當(dāng)于是在計(jì)算log2Num。最后輸出m個(gè)“0”以及Num的低m + 1位。解碼過(guò)程與之相反：先從輸入數(shù)據(jù)中讀取“0”，直到遇到“1”。計(jì)算總共讀取了幾個(gè)“0”，賦值給m。然后從“1”開(kāi)始讀取m + 1個(gè)位，賦值給Num。最后將Num減1，即可解碼出數(shù)值。 EG編碼可以有效的壓縮數(shù)值數(shù)據(jù)，但是在實(shí)現(xiàn)的時(shí)候還有幾個(gè)問(wèn)題需要解決。首先觀察表2.2中的編碼位長(zhǎng)數(shù)據(jù)。可以發(fā)現(xiàn)一點(diǎn)：數(shù)值較大的數(shù)據(jù)出現(xiàn)次數(shù)較多。比如位長(zhǎng)5出現(xiàn)了4次。這是由于二叉樹(shù)的性質(zhì)決定的。對(duì)于一般的二叉樹(shù)來(lái)說(shuō)，下層葉子節(jié)點(diǎn)總是比上層葉子節(jié)點(diǎn)多。這就意味著，在位長(zhǎng)數(shù)據(jù)中數(shù)值較大的數(shù)據(jù)占大多數(shù)。這將不利于EG編碼壓縮。解決方法是對(duì)位長(zhǎng)數(shù)據(jù)進(jìn)行調(diào)整。根據(jù)剛才分析的特點(diǎn)，可以用以下的公式對(duì)編碼位長(zhǎng)數(shù)據(jù)進(jìn)行調(diào)整： 調(diào)整后數(shù)值 = 最大位長(zhǎng) - 當(dāng)前位長(zhǎng) + 1 將表2.2中的位長(zhǎng)數(shù)據(jù)按照上述公式進(jìn)行調(diào)整，結(jié)果如表7.2所示。 符號(hào) A B C D E F G H 表7.2 位長(zhǎng)數(shù)據(jù)調(diào)整 雖然在我們的例子里，這樣的調(diào)整沒(méi)有得到很好的效果。但是在符號(hào)較多的位長(zhǎng)表中，這樣的調(diào)整可以讓數(shù)據(jù)整體變小，并且讓較下層的葉子節(jié)點(diǎn)使用較小的數(shù)值。這就可以充分發(fā)揮出EG編碼的特點(diǎn)。 在實(shí)現(xiàn)的時(shí)候還有另外一個(gè)問(wèn)題。在有些數(shù)據(jù)中，符號(hào)并沒(méi)有完全出現(xiàn)。例如，對(duì)于8位符號(hào)總共有256種符號(hào)。在壓縮英文文檔或程序源代碼的時(shí)候，全文中大約只出現(xiàn)了80至90種符號(hào)。有大量的符號(hào)沒(méi)有出現(xiàn)，位長(zhǎng)為0，如果直接保存也會(huì)占用大量空間。這時(shí)可以用RLE（Run Length Encoding）算法壓縮一下。RLE算法是利用數(shù)據(jù)和重復(fù)次數(shù)來(lái)替換重復(fù)的數(shù)據(jù)。由于在現(xiàn)實(shí)的情況下，不為0的位長(zhǎng)重復(fù)的可能性很小。所以這里只對(duì)位長(zhǎng)為0的數(shù)據(jù)進(jìn)行壓縮。具體做法是：如果遇到為0的位長(zhǎng)就輸出0，然后輸出0重復(fù)的次數(shù)。即使為0的位長(zhǎng)只出現(xiàn)了一次，也要輸出一個(gè)0和一個(gè)1。一個(gè)例子如表7.3所示。 位長(zhǎng) 5 8 0 6 5 0 0 0 0 7 表7.3 位長(zhǎng)數(shù)據(jù)的RLE壓縮 綜上所述，在輸出碼表數(shù)據(jù)的時(shí)候，先輸出最大位長(zhǎng)。然后再依次輸出調(diào)整后的位長(zhǎng)數(shù)據(jù)。如果遇到為0的位長(zhǎng)就輸出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ì)位長(zhǎng)數(shù)據(jù)進(jìn)行了調(diào)整，但是這種調(diào)整不一定是最優(yōu)的。按照G方案的調(diào)整，最底層的葉子節(jié)點(diǎn)使用最小的數(shù)值。但是最底層不一定是出現(xiàn)最多葉子節(jié)點(diǎn)的層。所以更好的方案是將位長(zhǎng)數(shù)據(jù)使用范式哈夫曼算法再壓縮一遍。這稱之為二次壓縮。二次壓縮又會(huì)產(chǎn)生一份新的碼表，稱為二次碼表。這份碼表再使用G方案壓縮。 可以根據(jù)當(dāng)前最大位長(zhǎng)為二次壓縮的范式哈夫曼算法指定符號(hào)信息量。符號(hào)信息量等于最大位長(zhǎng)加1。在我們的例子里可以設(shè)為6。即：位長(zhǎng)數(shù)據(jù)只在0至5的范圍內(nèi)變化。另外，二次壓縮同樣使用RLE算法壓縮為0的位長(zhǎng)數(shù)據(jù)。但是，有一點(diǎn)需要注意。RLE算法需要輸出重復(fù)次數(shù)。0位長(zhǎng)出現(xiàn)的重復(fù)次數(shù)通常變化很大，特別是使用較多符號(hào)的數(shù)據(jù)中。所以重復(fù)次數(shù)不使用范式哈夫曼編碼，而使用EG編碼。 綜上所述，在輸出碼表數(shù)據(jù)的時(shí)候，先根據(jù)最大位長(zhǎng)建立范式哈夫曼編碼器。掃描一遍位長(zhǎng)數(shù)據(jù)，統(tǒng)計(jì)頻度分配編碼。隨后用EG編碼輸出最大位長(zhǎng)。接著用G方案輸出二次碼表。然后再依次用范式哈夫曼編碼輸出位長(zhǎng)數(shù)據(jù)。如果遇到為0的位長(zhǎng)就用范式哈夫曼編碼輸出0，然后用EG編碼輸出0重復(fù)的次數(shù)。在我實(shí)現(xiàn)的程序里，將該壓縮方案稱之為“H方案”。 現(xiàn)在使用卡爾加里語(yǔ)料庫(kù)（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) 表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下開(kāi)發(fā)，編譯通過(guò)并調(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ù)再寫入到文件中。解壓縮的過(guò)程也是如此。算法計(jì)時(shí)的時(shí)候，讀寫文件的時(shí)間并沒(méi)有計(jì)算在內(nèi)。只計(jì)算單純算法的耗時(shí)。另外，程序中使用API函數(shù)GetTickCount進(jìn)行計(jì)時(shí)。按照微軟官方的說(shuō)法，該函數(shù)有15ms（15毫秒）的誤差。 現(xiàn)在使用卡爾加里語(yǔ)料庫(kù)（The Calgary Corpus[5]）中的18個(gè)文件，以及大型語(yǔ)料庫(kù)（The Large Corpus[5]）中的3個(gè)文件，進(jìn)行測(cè)試。測(cè)試結(jié)果如表8.1和表8.2所示。 文件 輸入大小 輸出大小 壓縮率 bpc 編碼耗時(shí) 解碼耗時(shí) 表8.1 卡爾加里語(yǔ)料庫(kù)壓縮測(cè)試 文件 輸入大小 輸出大小 壓縮率 bpc 編碼耗時(shí) 解碼耗時(shí) 表8.2 大型語(yǔ)料庫(kù)壓縮測(cè)試 以上測(cè)試數(shù)據(jù)中的壓縮率以及bpc（Bit Per Char）采用以下公式進(jìn)行計(jì)算： 壓縮率 = ((輸入大小 - 輸出大小) * 100) div 輸入大小 測(cè)試程序使用8位符號(hào)進(jìn)行壓縮，保存碼表的時(shí)候使用了H方案，在解壓縮的時(shí)候使用了8位快表。 觀察測(cè)試數(shù)據(jù)可以發(fā)現(xiàn)，范式哈夫曼算法的速度還是很快的。對(duì)于數(shù)百KB的數(shù)據(jù)，無(wú)論是壓縮還是解壓縮耗時(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ì)于使用百萬(wàn)量級(jí)符號(hào)的數(shù)據(jù)，這份碼表會(huì)占用很大的數(shù)據(jù)空間。 9 結(jié)束語(yǔ) 范式哈夫曼算法以其優(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.canterbury.ac.nz/descriptions/. 附錄：項(xiàng)目說(shuō)明 1 程序項(xiàng)目 本程序項(xiàng)目是論文《范式哈夫曼算法的分析與實(shí)現(xiàn)》（以下簡(jiǎn)稱“《范》”）的配套程序。本程序項(xiàng)目同時(shí)作為免費(fèi)開(kāi)源程序進(jìn)行發(fā)布。本程序項(xiàng)目中的代碼無(wú)需任何授權(quán)或許可即可用于個(gè)人和商業(yè)目的。使用者一切后果自負(fù)。 本程序項(xiàng)目在Delphi 7.0下開(kāi)發(fā)，編譯通過(guò)并且調(diào)試正常。本程序項(xiàng)目提供了一個(gè)文件到文件的，范示哈夫曼算法的壓縮程序。本程序項(xiàng)目中還提供了相關(guān)測(cè)試代碼，以分析范式哈夫曼算法的運(yùn)行過(guò)程。 本程序項(xiàng)目中的主要文件及相關(guān)說(shuō)明如表1.1所示。 文件 說(shuō)明 表1.1 項(xiàng)目主要文件說(shuō)明 在程序項(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文件 由于范式哈夫曼算法輸出變長(zhǎng)位的數(shù)據(jù)，所以我編寫了這個(gè)單元文件，提供了位讀寫的可擴(kuò)展緩沖區(qū)操作。在這個(gè)單元文件里我定義了一個(gè)緩沖區(qū)類型TMBBuffer。同時(shí)，我編寫了一系列的函數(shù)，提供對(duì)這個(gè)類型緩沖區(qū)的讀寫操作。通過(guò)這些函數(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ù)。在范式哈夫曼算法編解碼的過(guò)程中，主要調(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)部分的開(kāi)頭，添加了相應(yīng)的說(shuō)明注釋。有興趣的讀者可以到單元文件中查看，這里不再重復(fù)。 3 CanonicalHuffman.pas文件 我在這個(gè)單元文件里編寫了范式哈夫曼算法的實(shí)現(xiàn)代碼。在這個(gè)單元文件中一共定義了3個(gè)類。其中，TCHEncode實(shí)現(xiàn)了編碼過(guò)程，TCHDecode實(shí)現(xiàn)了解碼過(guò)程，TCHCoding提供了對(duì)TCHEncode和TCHDecode的簡(jiǎn)單封裝。 TCHEncode類實(shí)現(xiàn)了范式哈夫曼算法的編碼過(guò)程。注意，TCHEncode類不負(fù)責(zé)符號(hào)頻度的統(tǒng)計(jì)工作。頻度統(tǒng)計(jì)工作應(yīng)該由調(diào)用TCHEncode類的代碼完成。在TCHEncode類中的AllocCode方法實(shí)現(xiàn)了編碼位長(zhǎng)計(jì)算和編碼分配兩個(gè)過(guò)程。對(duì)應(yīng)于論文《范》中的第3節(jié)和第4節(jié)。TCHEncode類中的LengthLimited方法實(shí)現(xiàn)了限制編碼位長(zhǎng)的過(guò)程。對(duì)應(yīng)于論文《范》中的第6節(jié)。TCHEncode類中的SaveBitLenG和SaveBitLenH兩個(gè)方法實(shí)現(xiàn)了碼表二次壓縮的過(guò)程。對(duì)應(yīng)于論文《范》中的第7節(jié)。其中，SaveBitLenG使用G方案，對(duì)應(yīng)第7.1節(jié)；SaveBitLenH使用H方案，對(duì)應(yīng)第7.2節(jié)。TCHEncode類的其它方法說(shuō)明見(jiàn)單元文件中的相關(guān)注釋。 TCHDecode類實(shí)現(xiàn)了范式哈夫曼算法的解碼過(guò)程。TCHDecode類中的Construct方法實(shí)現(xiàn)了解碼表的構(gòu)建和快表的構(gòu)建兩個(gè)過(guò)程。對(duì)應(yīng)于論文《范》中的第5節(jié)。TCHDecode類中的LoadBitLenG和LoadBitLenH兩個(gè)方法實(shí)現(xiàn)了碼表解壓縮的過(guò)程。對(duì)應(yīng)于論文《范》中的第7節(jié)。TCHDecode類的其它方法說(shuō)明見(jiàn)單元文件中的相關(guān)注釋。 TCHCoding類實(shí)現(xiàn)了范式哈夫曼算法的編解碼過(guò)程。TCHCoding類是對(duì)TCHEncode和TCHDecode的簡(jiǎn)單封裝。TCHCoding類提供了一個(gè)緩沖區(qū)到緩沖區(qū)的壓縮與解壓縮過(guò)程。TCHCoding類中的Encode方法是以字節(jié)為單位從緩沖區(qū)中讀取數(shù)據(jù)進(jìn)行壓縮，然后保存到另一緩沖區(qū)中。TCHCoding類中的Decode方法是從緩沖區(qū)中讀取壓縮數(shù)據(jù)進(jìn)行解壓縮，然后保存到另一緩沖區(qū)中。TCHCoding類中的Encode16和Decode16兩個(gè)方法與上述兩個(gè)方法類似。只不過(guò)這兩個(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ì)輸出位長(zhǎng)整理的整個(gè)過(guò)程。TCHEncode類中的SaveBitLenG和SaveBitLenH會(huì)輸出碼表壓縮情況。TCHDecode. Construct會(huì)輸出解碼表和快表的內(nèi)容。TCHDecode類中的LoadBitLenG和LoadBitLenH會(huì)輸出碼表解壓縮情況。 在本單元文件中可以修改常量CH_MAXLENGTH，這個(gè)常量就是限制位長(zhǎng)的大小。在測(cè)試的時(shí)候可以將這個(gè)常量調(diào)小，以觀察TCHEncode. LengthLimited方法的調(diào)整過(guò)程。 在本程序項(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 表4.1 符號(hào)與編碼對(duì)應(yīng)關(guān)系 現(xiàn)在對(duì)該文件進(jìn)行測(cè)試。在程序中選擇“范式哈夫曼算法（8位符號(hào)測(cè)試）”算法。注意：由于采用H方案保存碼表，輸出信息會(huì)有兩份。一份是數(shù)據(jù)壓縮的編碼表，一份是碼表壓縮的編碼表。程序輸出結(jié)果如下： ================================================================== 數(shù)據(jù)種數(shù)：8 數(shù)據(jù)種數(shù)：4 設(shè)定符號(hào)容量：6種 設(shè)定符號(hào)容量：256種 編碼器內(nèi)存占用：2080B ≈ 2KB ≈ 0MB 編碼器內(nèi)存占用：80B ≈ 0KB ≈ 0MB 操作完成，耗時(shí)：15 ================================================================== 數(shù)據(jù)種數(shù)：4 最大位長(zhǎng)：3 快表位長(zhǎng)：3 輸入碼表大?。℅）：27位≈3字節(jié) 數(shù)據(jù)種數(shù)：8 最大位長(zhǎng)：5 快表位長(zhǎng)：5 輸入碼表大小（H）：107位≈13字節(jié) 解碼器內(nèi)存占用：1604B ≈ 1KB ≈ 0MB 解碼器內(nèi)存占用：484B ≈ 0KB ≈ 0MB 操作完成，耗時(shí)：47 比較文件： 葉葉 |
聯(lián)系客服
