一種基于緩沖窗口的雙哈夫曼壓縮算法

喬 雨，嵇 浩

（1.南京工業(yè)大學(xué)浦江學(xué)院 計算機(jī)與通信工程學(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]。本文對哈夫曼算法的壓縮原理進(jìn)行深入地研究，針對其壓縮過程中存在的不足之處做出改進(jìn)，進(jìn)一步提升哈夫曼算法在壓縮過程中的效果。

1 相關(guān)工作

1.1 哈夫曼編碼算法介紹

哈夫曼編碼是一種性能較優(yōu)的無損數(shù)據(jù)壓縮方法，在計算機(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é)點的左分支標(biāo)記為代碼“0”，右分支標(biāo)記為代碼“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所示的哈夫曼樹，若將樹中的左分支標(biāo)記為“0”，右分支標(biāo)記為“1”，則該哈夫曼樹中的各節(jié)點編碼后的結(jié)果見表2所列。

上述的靜態(tài)哈夫曼編碼過程需要讀取兩次文件中的原始數(shù)據(jù)和權(quán)值表，存在較大的時間開銷[4]。動態(tài)哈夫曼編碼算法改進(jìn)了靜態(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ā)生變化。因此，為了使算法能及時更新各符號的概率分布，文獻(xiàn)[5]對哈夫曼編碼進(jìn)行改進(jìn)，引入帶有緩沖窗口的哈夫曼編碼，來提高動態(tài)哈夫曼編碼的性能。

圖1 哈夫曼樹示例

表2 符號編碼表

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

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

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

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

基于上述的算法過程可以動態(tài)地生成一棵哈夫曼樹，而由于符號的編碼長度與樹的深度成正比，因此，隨著緩沖窗口中非重復(fù)符號的數(shù)量不斷增加，依賴于這些符號的哈夫曼樹的深度隨之增加，這也就導(dǎo)致了符號的編碼長度不斷變長。最壞的情況下，符號的最大編碼長度將達(dá)到（非重復(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ù)源。本文將對基于緩沖窗口的哈夫曼算法進(jìn)行改進(jìn)。

1.3 算法評價指標(biāo)

（1）信息熵

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

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

（2）編碼的平均長度

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

（3）信息冗余度

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

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

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

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

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

圖2 緩沖窗口模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表3 符號頻數(shù)表

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

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

表4 符號編碼序列表

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

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

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

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

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

表6 符號編碼表

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

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

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

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

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ù)為英文文本，并包含部分?jǐn)?shù)字。

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

（1）壓縮率比較

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

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

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

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

（2）壓縮速率比較

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

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

4 結(jié) 語

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