赫夫曼編碼的原理及改進算法

魏莉

（山西廣播電視大學 山西省太原市 030027）

1 引言

在信息大爆炸的今天，壓縮技術對于節(jié)約存儲空間，減少傳輸時間，節(jié)省寶貴的流量，特別有價值。壓縮技術的起源可追溯到1948年，美國數(shù)學家、信息論的創(chuàng)始人克勞德·香農(nóng)（Claude Shannon）將熱力學的熵引入到信息論中，稱為香農(nóng)信息熵。信息熵編碼法是一種無損數(shù)據(jù)壓縮的方法，常見的熵編碼技術有赫夫曼編碼和算術編碼。無損壓縮是一種可逆的壓縮，它保留了原始的信息，解壓可完全恢復原始的信息，不會丟失任何信息。香農(nóng)和計算機先驅羅伯特·法諾（Robert Fano）于1948年提出香農(nóng)-法諾編碼（Shannon-Fano coding），它是一種基于信息符號集及概率而構建前綴碼的技術，用于數(shù)據(jù)壓縮領域。香農(nóng)通過算術證明了肯定有更好的壓縮技術存在，法諾的學生實現(xiàn)了優(yōu)化壓縮的問題。這個學生就是美國數(shù)學家大衛(wèi)·赫夫曼（David A.Huffman），赫夫曼編碼是他1952年在麻省理工讀書期間發(fā)表的論文中提出的，該方法實用高效，并沿用至今[1]。

2 赫夫曼編碼

2.1 赫夫曼編碼原理

赫夫曼編碼是一種可變字長編碼（Variable Length Coding,VLC），該方法完全依據(jù)字符出現(xiàn)概率來構造異字頭的平均長度最短的碼字[2,3]。Huffman 編碼是一種特殊的最優(yōu)前綴代碼，通常用于無損數(shù)據(jù)壓縮。赫夫曼編碼的輸出可以看作是編碼源符號的變長編碼表。該算法從源符號的每個概率(權重)中得出，概率大的符號通常用更少的位表示。赫夫曼編碼通過創(chuàng)建最優(yōu)二叉樹(赫夫曼樹)來實現(xiàn)，約定左、右分支，分別代表0 和1。

比如有一段文字內(nèi)容為“釘釘板板釘釘鐵釘釘鐵板鐵板釘鐵釘”要網(wǎng)絡傳輸給別人，顯然用二進制的字符0、1 來表示。這段文字可以用兩位的二進制數(shù)據(jù)表示即可，00 代表“釘”，10 代表“鐵”，01 代表“板”，這樣傳輸?shù)臄?shù)據(jù)編碼后為000001010000100000100 11001001000，總長32，對方接收時可以按照2 位一分來譯碼。 “釘”、“鐵”和“板”的出現(xiàn)頻率是不相同的，分別為0.5、0.25 和0.25。依據(jù)赫夫曼編碼的思想，設計“釘”、“鐵”和“板”的編碼分別為0、10 和11，赫夫曼編碼是前綴編碼，譯碼時不會出現(xiàn)二義性。再次編碼，001111001000101110110100，共24 個字符。也就是說，數(shù)據(jù)被壓縮了，節(jié)約了四分之一的存儲和傳輸成本。隨著字符的增加和多字符權重的不同，這種壓縮會更加顯出其優(yōu)勢。

赫夫曼編碼算法流程如圖1所示。

第一步：概率統(tǒng)計。赫夫曼編碼就是變長編碼，發(fā)送概率大的編碼短，發(fā)送概率小的編碼長。設定需要編碼的字符集為{d1，d2，…dn}，各個字符在電文中出現(xiàn)的次數(shù)或頻率集合為{w1，w2，…wn}，以d1，d2，…dn作為葉子結點，以w1，w2，…wn作為相應葉子結點的權值來構造一棵赫夫曼樹。

圖1：赫夫曼編碼算法流程圖

第二步：構造赫夫曼樹。構造赫夫曼樹的算法是一種貪心算法。貪心算法是指求解問題的時候，總是選擇當前看來最好的。構造赫夫曼樹的時候，貪心的地方在于總是選取當前權值最小的兩個結點來進行合并生成新結點。根據(jù)給定的n 個權值{w1, w2,……wn}，構造n 棵只有根結點的二叉樹。在森林中選取兩棵根結點權值最小的樹作左右子樹，構造一棵新的二叉樹，置新二叉樹根結點權值為其左右子樹根結點權值之和。在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中。重復上述兩步，直到只含一棵樹為止，這棵樹即赫夫曼樹。選擇權值最小的兩個結點，合并生成父結點，權值為左右子樹之和。然后將父結點加入到集合中，繼續(xù)選擇權值最小的兩個結點。重復下去。這是個遞歸的過程。

第三步：壓縮編碼，赫夫曼樹構造完成后標記左支代表0，右支代表1。對每個葉子結點，將從葉子結點到根結點所經(jīng)過的所有路徑分支的0 和1 的組合序列變?yōu)樵摻Y點對應的字符的編碼，這就是赫夫曼編碼。

第四步：解碼輸出，是壓縮編碼的逆過程，無損壓縮的優(yōu)點在于無信息丟失恢復原貌。

2.2 赫夫曼編碼的實現(xiàn)

定義赫夫曼樹結點的結構體類型HTNode，結構體中包括結點權值（weight）、雙親（parent）、左孩子（lch）和右孩子（rch）結點。下面是對赫夫曼算法的代碼實現(xiàn)，用C 語言對非遞歸遍歷赫夫曼樹求解赫夫曼編碼，降低了空間和時間復雜度。定義每個結點赫夫曼編碼的結構類型Hcode，用字符型數(shù)組cd[ ]存放赫夫曼編碼。

3 赫夫曼算法的改進

赫夫曼編碼是一種對源字符進行可變成長編碼，變長編碼表通過源字符出現(xiàn)概率得到的，赫夫曼編碼的主要思想就是概率高的用短編碼，概率小的用長編碼。赫夫曼編碼的方法就是對赫夫曼樹按左0 右1 對Huffman 樹的所有分支編號。使用赫夫曼編碼有其局限性，每個字符的編碼長度必須為整數(shù)，源字符集的概率分布若不是2-n的形式，則無法達到熵極限，并且輸入字符數(shù)受限于字符編碼表。

3.1 范式赫夫曼編碼

赫夫曼編碼是一種高效的數(shù)據(jù)壓縮技術，也存在其不足之處，在數(shù)據(jù)傳輸過程中，編碼器需要保存或傳輸赫夫曼編碼樹，存儲空間開銷大。1973年牛頓·范勒（Newton Faller）提出一種降低赫夫曼樹存儲空間的技術，稱為范式赫夫曼編碼[4]。目前很多流行的壓縮方法如GZIB、PNG、JPEG、MPEG 等都是基于此技術。

范式赫夫曼編碼的核心思想是在某種約定的情況下，解碼器能動態(tài)地通過很少的數(shù)據(jù)便能重構出赫夫曼編碼樹，不需要任何附加的空間存儲數(shù)據(jù)。一種約定是數(shù)字序列屬性（numerical sequence property），要求相同長度的字符是連續(xù)整數(shù)的二進制形式。例如，假設碼字長度為3 的最小值為010，那么其他長度為3 的字符必為001、100、110 等。另一個約定：為了降低空間開銷，長度為i 第一個字符f(i)能從長度為i-1 的最后一個字符得出，即f(i)= 2(f(i-1)+1)。經(jīng)過上述的兩種約定，解碼器即可恢復整棵赫夫曼編碼樹的結構。

3.2 適應性赫夫曼編碼

適應性赫夫曼編碼（Adaptive Huffman coding）又稱動態(tài)赫夫曼編碼，是基于靜態(tài)的赫夫曼編碼的技術[5]。靜態(tài)的赫夫曼編碼最大的缺點就是需要事先掃描原始數(shù)據(jù)，對各字符出現(xiàn)的概率進行統(tǒng)計，利用概率結果創(chuàng)建赫夫曼樹，然后再掃描原始數(shù)據(jù)對其進行編碼，并保存編碼信息。在網(wǎng)絡通信中，這將會引起較大延時，增加空間開銷，降低數(shù)據(jù)壓縮的速度。很多情況數(shù)據(jù)是動態(tài)產(chǎn)生，實時變化的，比如車載GPS 定位、氣象衛(wèi)星云圖等。

適應性赫夫曼編碼不需要事先統(tǒng)計概率構造赫夫曼樹，而是隨著編碼的進行，逐步構造赫夫曼樹，對符號的統(tǒng)計是動態(tài)進行的。在編碼過程中，同一個符號的編碼可能發(fā)現(xiàn)改變，編碼長度也可能變化。初始化編碼樹的時候，只需要單遍掃描數(shù)據(jù)，編碼樹的初始狀態(tài)只包含一個葉子結點，包含符合NYT（Not Yet Transmitted,尚未傳送）。當一個尚未包含在編碼樹種的符號需要被編碼時，系統(tǒng)就輸出NYT 編碼，然后跟著符號的原始表達。當解碼器解碼到NYT 之后，可知以下的內(nèi)容不是赫夫曼編碼。

3.3 赫夫曼編碼與其他算法結合

波蘭計算機科學家Jarek Duda 于2014年提出不對稱數(shù)字系統(tǒng)（Asymmetric numeral systems,ANS）[6]，是結合了赫夫曼編碼速度和算術編碼壓縮率的一種無損壓縮編碼，其理論基礎源于信息熵理論。熵越高，信息越多，一個事件所包含的信息量和它的概率的倒數(shù)呈正相關，平均1 比特信息要1 比特消息存儲。該方法同赫夫曼編碼相同之處是也依靠概率分布的來實現(xiàn)信息的保存，編碼速度與赫夫曼編碼同樣快，但是壓縮率高。

4 結語

赫夫曼編碼被廣泛應用于數(shù)據(jù)文件壓縮，壓縮率通常在20%至90%之間，當源數(shù)據(jù)各符號出現(xiàn)的概率很不平均的時候，赫夫曼編碼的壓縮效果更明顯。本文結合實例分析了赫夫曼算法的原理，給出了一種改進的非遞歸的算法實現(xiàn)，降低了算法的時間和時間復雜度；并且介紹了幾種基于赫夫曼編碼的改進算法，分析了各種算法的原理。目前數(shù)據(jù)壓縮算法眾多并在不斷改進，很多問題可以根據(jù)實際情況結合不同壓縮算法，以到達數(shù)據(jù)準確、高效和安全的傳輸。