喬 雨，嵇 浩

（1.南京工業(yè)大學(xué)浦江學(xué)院 計算機與通信工程學(xué)院，江蘇 南京 211200；2.亞信科技（成都）有限公司，四川 成都 610000）

0 引 言

隨著信息的爆炸式增長，需要傳播和存儲的信息量也隨之增長。為了提升傳播效率和節(jié)省存儲空間，各種壓縮文件的軟件應(yīng)運而生，如WinRAR等[1]。數(shù)據(jù)壓縮技術(shù)可以應(yīng)用在通信數(shù)據(jù)的傳輸、文件數(shù)據(jù)的存儲、圖像信息的隱藏與提取等多個領(lǐng)域。一般來說，整個壓縮過程可能是有損壓縮和無損壓縮的混合，哈夫曼算法便是其中一種經(jīng)典的無損壓縮方法，得到了廣泛的研究和應(yīng)用[2]。本文對哈夫曼算法的壓縮原理進行深入地研究，針對其壓縮過程中存在的不足之處做出改進，進一步提升哈夫曼算法在壓縮過程中的效果。

1 相關(guān)工作

1.1 哈夫曼編碼算法介紹

哈夫曼編碼是一種性能較優(yōu)的無損數(shù)據(jù)壓縮方法，在計算機科學(xué)領(lǐng)域，這種壓縮方法被廣泛用于壓縮文本、圖像和許多其他數(shù)據(jù)[3]。哈夫曼編碼過程大致可以分為兩個階段：第一階段先通過統(tǒng)計每個符號出現(xiàn)的概率，并將其作為符號的權(quán)重值；第二個階段通過構(gòu)造哈夫曼樹，將較短的編碼被分配給高概率的符號，較長的編碼則分配給出現(xiàn)概率較低的符號。算法過程描述如下：

Step1：將每個給定的符號作為一個葉子節(jié)點，并為其確定權(quán)值；

Step2：合并兩個權(quán)值最低的節(jié)點；

Step3：節(jié)點的左分支標記為代碼“0”，右分支標記為代碼“1”；

Step4：計算Step2中合并后兩個節(jié)點的概率之和；

Step5：在樹中添加另一個節(jié)點，并執(zhí)行Step2～Step4；

Step6：在完成哈夫曼樹的構(gòu)造后，分別計算樹中葉子節(jié)點的熵值、平均長度值和冗余值。

例如，有6個不同符號A、B、C、D、E、F，每個符號出現(xiàn)的頻數(shù)見表1所列。

表1 符號頻數(shù)表

將各符號出現(xiàn)的頻數(shù)作為權(quán)值構(gòu)造出如圖1所示的哈夫曼樹，若將樹中的左分支標記為“0”，右分支標記為“1”，則該哈夫曼樹中的各節(jié)點編碼后的結(jié)果見表2所列。

上述的靜態(tài)哈夫曼編碼過程需要讀取兩次文件中的原始數(shù)據(jù)和權(quán)值表，存在較大的時間開銷[4]。動態(tài)哈夫曼編碼算法改進了靜態(tài)哈夫曼編碼中的不足之處，只需要在算法的第一階段利用已編碼符號的權(quán)值來構(gòu)造哈夫曼樹，不需要重復(fù)讀取權(quán)值表。因此，動態(tài)哈夫曼編碼算法的關(guān)鍵步驟在于如何統(tǒng)計所有待編碼數(shù)據(jù)中符號的出現(xiàn)次數(shù)。由于符號出現(xiàn)的概率在不同的數(shù)據(jù)段中分布是不同的，并且在編碼過程中會發(fā)生變化。因此，為了使算法能及時更新各符號的概率分布，文獻[5]對哈夫曼編碼進行改進，引入帶有緩沖窗口的哈夫曼編碼，來提高動態(tài)哈夫曼編碼的性能。

圖1 哈夫曼樹示例

表2 符號編碼表

1.2 哈夫曼編碼算法研究現(xiàn)狀

哈夫曼編碼算法自1952年被提出后得到了行業(yè)內(nèi)的高度關(guān)注，其在數(shù)據(jù)壓縮領(lǐng)域的應(yīng)用更是成為研究的熱點。文獻[6]在傳統(tǒng)哈夫曼編碼的基礎(chǔ)上，提出一種自適應(yīng)算法，該算法基于動態(tài)變化的查找表來構(gòu)建哈夫曼樹，進而提高哈夫曼編碼算法的效率。張鳳林等人提出在構(gòu)建哈夫曼樹的過程中利用堆排序來代替原來的排序方式，實驗結(jié)果顯示改進后的哈夫曼樹的構(gòu)建效率更高[7]。而文獻[8]則是面向具體的應(yīng)用系統(tǒng)，提出基于熵編碼的哈夫曼編碼改進算法，該算法利用固定奇偶碼取代動態(tài)生成哈夫曼樹的過程，使得編碼和譯碼的過程更加簡單，并保持可觀的壓縮效率。

在實際應(yīng)用過程中，除了對哈夫曼編碼算法本身的改進，同時衍生出了其他哈夫曼編碼算法，如基于最小方差的哈夫曼編碼算法[9]和基于范式的哈夫曼編碼算法[10]。基于最小方差的哈夫曼算法是通過調(diào)整哈夫曼樹構(gòu)建過程中的中間結(jié)果的排序，使得最終的哈夫曼編碼長度的方差最小。這是由于編碼過程中的緩沖區(qū)大小受到編碼長度的方差值的影響，方差越小，所需的緩沖區(qū)越小。因此，基于最小方差的哈夫曼編碼算法能夠有效降低緩沖區(qū)的空間大小，提升算法整體性能?；诜妒降墓蚵幋a算法則提供一種限制編碼的壓縮方式，即對字符的編碼均需小于或者等于設(shè)置的最大編碼長度，相應(yīng)的解碼過程根據(jù)特定的編碼方式進行解碼，達到節(jié)省存儲空間的目的。

文獻[11]則提出了基于緩沖窗口的哈夫曼編碼算法，該算法通過使用固定大小的窗口緩沖區(qū)來存放當前時間段出現(xiàn)的符號，隨著文件中符號的依次讀入，節(jié)點的權(quán)值隨之進行更新。當緩沖窗口已滿時，則刪除窗口中最早存入的符號；同時更新與新進符號相關(guān)聯(lián)的節(jié)點權(quán)重值，并調(diào)整哈夫曼樹的形態(tài)。

基于上述的算法過程可以動態(tài)地生成一棵哈夫曼樹，而由于符號的編碼長度與樹的深度成正比，因此，隨著緩沖窗口中非重復(fù)符號的數(shù)量不斷增加，依賴于這些符號的哈夫曼樹的深度隨之增加，這也就導(dǎo)致了符號的編碼長度不斷變長。最壞的情況下，符號的最大編碼長度將達到（非重復(fù)符號的數(shù)量-1）位，如第1.1節(jié)中的示例描述。從表2和表3可知，符號E、F出現(xiàn)的頻數(shù)只比緩沖窗口內(nèi)其他的符號少一次，但是其哈夫曼編碼的長度為5，體現(xiàn)了改編碼方式的低效性，即使它們的頻率相對較低。因此，在這種情況下，基于緩沖窗口的哈夫曼編碼性能并不好。另一方面，基于緩沖窗口的哈夫曼算法的性能與窗口的大小有著直接的關(guān)系，因為在算法中使用的是固定大小的窗口，這導(dǎo)致該算法不能很好地適應(yīng)不同類型的數(shù)據(jù)源。本文將對基于緩沖窗口的哈夫曼算法進行改進。

1.3 算法評價指標

（1）信息熵

信息熵[12]是指消息中包含信息量的平均值，可以表示為：

式中參數(shù)b是對數(shù)的底數(shù)。

（2）編碼的平均長度

將符號出現(xiàn)的概率與該符號的編碼長度值進行求積操作，就可以得到哈夫曼編碼的平均長度，可表示為：

（3）信息冗余度

信息冗余度[13]在信息論中是指傳輸?shù)男畔⒌谋忍財?shù)與實際信息的比特數(shù)之差，即式（2）與式（1）的差，可表示為：

2 基于緩沖窗口的雙哈夫曼編碼算法（DHBW）介紹

為了解決上述提到的編碼低效性和緩沖窗口無法自主地調(diào)整到最佳大小的問題，本文對基于緩沖窗口的哈夫曼算法進行了兩個方面的改進。

2.1 限制緩沖窗口中符號種類的數(shù)量

DHBW算法中利用緩沖窗口來存儲符號編碼，該緩沖窗口中對不同符號的數(shù)量設(shè)置了閾值。需要說明的是，窗口中限制了不同符號的數(shù)量，而不是限制所有符號的數(shù)量。這是因為每個符號經(jīng)過哈夫曼算法編碼后的長度取決于不同符號的數(shù)量，與符號的總數(shù)量無關(guān)。緩沖窗口模型如圖2所示。

圖2 緩沖窗口模型

當緩沖窗口中不同符號的數(shù)量超過所設(shè)的閾值時，則重復(fù)刪除最早的符號，直到不同符號的個數(shù)在閾值內(nèi)。算法的步驟描述如下：

在傳統(tǒng)的哈夫曼算法中通常采用數(shù)組等結(jié)構(gòu)來進行存儲，這種存儲結(jié)構(gòu)不易擴充，導(dǎo)致緩沖窗口的大小不能很好地適應(yīng)不同類型的數(shù)據(jù)源。例如，緩沖窗口的大小size（N）=16，在進行編碼時，如果編碼位長度超過16位時就會發(fā)生數(shù)據(jù)溢出。因此，在本文提出的DHBW算法中利用線性鏈表[7]作為緩沖窗口的存儲結(jié)構(gòu)。這種改進能夠使得算法中的緩沖窗口不受編碼位數(shù)影響，只與內(nèi)存大小有關(guān)。

2.2 基于緩沖窗口的雙哈夫曼算法

在基于緩沖窗口的哈夫曼算法中，通常將不在窗口中編碼的符號用轉(zhuǎn)義碼分開，然后用8位ASCII碼進行編碼，這樣雖然能夠縮短編碼后的長度，但是當字符種類非常多時，仍存在編碼后的碼長過長的情況。為了進一步提升壓縮效果，本文提出一種基于緩沖窗口的雙哈夫曼算法，這里的“雙”是指進行一次哈夫曼編碼后，在編碼的結(jié)果上再進行二次哈夫曼編碼，算法過程如下：

Step1：將每個給定的符號作為一個葉子節(jié)點，并為其確定權(quán)值；

Step2：合并兩個權(quán)值最低的節(jié)點；

Step3：節(jié)點的左分支標記為代碼“0”，右分支標記為代碼“1”；

Step4：計算Step2中合并后兩個節(jié)點的概率之和；

Step5：在樹中添加另一個節(jié)點，并執(zhí)行Step2～Step4；

Step6：哈夫曼樹構(gòu)造完成后，分別計算樹中葉子節(jié)點的熵值、平均長度值和冗余值；

Step7：在哈夫曼樹生成后，根據(jù)左右分支的標記得出每個符號的編碼，現(xiàn)在將這些代碼字連接起來得到一個字符串；

Step8：將Step7中符號編碼進行連接，形成一個只含有“0”和“1”的字符串，并且計算出該字符串中“0”和“1”的概率；

Step9：重復(fù)Step1～Step6。

這里以A、B、C、D、E、F這6個字符為例，字符的出現(xiàn)次數(shù)（視為權(quán)重值）見表3所列。

表3 符號頻數(shù)表

利用上述的算法過程對表3中的字符進行處理，得到了如圖3所示的哈夫曼樹。其中，哈夫曼樹中的每個節(jié)點左子樹標記為“0”，右子樹標記為“1”，則得到見表4所列的編碼序列。

圖3 由表3構(gòu)造出的哈夫曼樹

表4 符號編碼序列表

根據(jù)第1.3節(jié)中的評價指標，分別計算該例子中的熵、平均長度和冗余度的值，結(jié)果見表5所列。

表5 哈夫曼編碼的評價指標結(jié)果

在對原始符號進行一次哈夫曼編碼后，將6位字符的編碼進行連接，得到字符串“01000110101101100”，可以看到編碼后的結(jié)果是只含有“0”和“1”的形式，且出現(xiàn)的概率分別為9/17和8/17?；诒疚腄HBW算法的思路，接下來將針對該結(jié)果進行二次哈夫曼編碼。同樣地，先根據(jù)符號出現(xiàn)的概率構(gòu)造一棵只含有“0”和“1”的哈夫曼樹，如圖4所示。

圖4 二次構(gòu)造的哈夫曼樹

根據(jù)左子樹標記為“0”，右子樹標記為“1”，得到見表6所列的編碼序列；接著，分別計算二次編碼后的熵、平均長度和冗余度的值，結(jié)果見表7所列。

表6 符號編碼表

以上結(jié)合具體的例子詳細闡述了雙哈夫曼編碼的原理和過程，分別對比采用一次哈夫曼編碼和二次哈夫曼編碼的結(jié)果見表5和表7所列，從表中可以看出經(jīng)過二次編碼后的編碼長度和信息冗余度均有下降，提升了有效信息的占比。

表7 哈夫曼編碼的評價指標結(jié)果

3 實驗過程與結(jié)果

為了驗證本文提出的DHBW算法的有效性，分別與哈夫曼算法（Huffman）、基于緩沖窗口的哈夫曼算法（Windowed Huffman）進行壓縮率和壓縮速率的比較。選取不同類型、不同大小的文件，分別采用三種壓縮算法進行壓縮。

3.1 實驗環(huán)境

實驗是在操作系統(tǒng)為Windows 8.1，英特爾酷睿i7處理器，8 GB內(nèi)存的環(huán)境下，利用Eclipse作為開發(fā)環(huán)境。實驗數(shù)據(jù)采用了DOC、TXT和C++格式的文件，文件中的數(shù)據(jù)為英文文本，并包含部分數(shù)字。

3.2 實驗結(jié)果與分析

（1）壓縮率比較

選取大小為5 MB，15 MB，25 MB的文件，格式分別為DOC、TXT和C++的文件數(shù)據(jù)進行哈夫曼壓縮、基于緩沖窗口的哈夫曼壓縮和基于緩沖窗口的雙哈夫曼壓縮，得出的實驗結(jié)果見表8所列[14]，其中：

壓縮率=（1-壓縮文件大小/輸入文件大小）×100%

表8 不同算法的壓縮率比較

由表8可以看出，本文提出的DHBW算法比傳統(tǒng)的哈夫曼算法的壓縮率分別降低6.6%，7.3%，6.06%；比基于緩沖窗口的哈夫曼算法的壓縮率分別降低4.4%，2.67%，3.32%。由此可認為基于緩沖窗口的雙哈夫曼壓縮算法能夠提升文件的壓縮率。

（2）壓縮速率比較

在使用三種壓縮算法進行文件壓縮時記錄了壓縮的時間性能，即平均壓縮速率，結(jié)果見表9所列。從表中可以看出，本文提出的DHBW算法在壓縮速率低于對比的兩種算法，這是因為提出的DHBW算法需要進行3次數(shù)據(jù)掃描，因此會導(dǎo)致算法的整體壓縮速率較低。

表9 三種算法的平均壓縮速率 MB/s

4 結(jié) 語

本文在基于緩沖窗口的哈夫曼壓縮算法基礎(chǔ)上進行了兩個方面的改進，首先，對緩沖窗口中不同符號的數(shù)量進行限制，以此來提升動態(tài)生成哈夫曼樹的性能；其次，在一次哈夫曼編碼的基礎(chǔ)上再次進行只含有“0”和“1”哈夫曼編碼，進一步降低字符的編碼長度。實驗結(jié)果證明，本文改進后的DHBW算法能夠降低文件的壓縮效果，但是需要耗費更多的時間。在未來的研究過程中，可以從提升壓縮速率的角度出發(fā)，在保證壓縮率的基礎(chǔ)上也能保持較高的壓縮速率。