文國知

(武漢工業(yè)學(xué)院數(shù)理科學(xué)系，湖北武漢430023)

基于C語言的自適應(yīng)Huffman編碼算法分析及實現(xiàn)研究

文國知

(武漢工業(yè)學(xué)院數(shù)理科學(xué)系，湖北武漢430023)

通過C語言程序，動態(tài)統(tǒng)計信源符號概率，逐步構(gòu)造Huffman編碼樹，實現(xiàn)了自適應(yīng)Huffman編碼，解決了靜態(tài)編碼樹不能根據(jù)信源符號的局部變化做出相應(yīng)變化的主要問題。結(jié)果表明，自適應(yīng)Huffman編碼算法壓縮率很大，能進一步提高數(shù)據(jù)傳輸?shù)男省?/p>

Huffman編碼;自適應(yīng);無損壓縮

隨著信息技術(shù)的快速發(fā)展，日常需要處理或者傳輸?shù)臄?shù)據(jù)越來越多，由于數(shù)字化的多媒體信息尤其是數(shù)字音頻、視頻信號的數(shù)據(jù)量特別龐大，大數(shù)據(jù)量的信息會給存儲器的存儲容量、通訊干線信道的帶寬以及計算機的處理速度增加極大的壓力。如何采用有效的數(shù)據(jù)壓縮技術(shù)來節(jié)省存儲空間和網(wǎng)絡(luò)傳送時間已越來越引起人們的重視［1-3］。自適應(yīng)Huffman編碼方法，就是根據(jù)離散信源符號的產(chǎn)生概率，動態(tài)對信源符號進行編碼，使產(chǎn)生概率小的信源符號編的碼字長，產(chǎn)生概率大的信源符號編的碼字短，這樣就可以達到提高信息傳輸效率的目的［4］。

1 靜態(tài)Huffman編碼樹的構(gòu)造原理

Huffman編碼樹是按照信源符號權(quán)重值的大小將信源符號進行排序，取出權(quán)重值最小的兩個信源符號作為葉節(jié)點組成一棵子樹，子樹的權(quán)重值為兩個葉節(jié)點即權(quán)重值最小的兩個信源符號權(quán)重值之和;然后將新產(chǎn)生的子樹放回原來的集合，仍然按照信源符號權(quán)重值的大小將信源符號進行排序。重復(fù)以上方法，直至信源符號集合中只剩下一個符號。

以abcddbb作為待編碼的原始信源數(shù)據(jù)串符號為例。首先，統(tǒng)計出a、b、c、d四個符號在原始數(shù)據(jù)串中的權(quán)重，結(jié)果如表1所示。

表1 數(shù)據(jù)串a(chǎn)bcddbb的概率統(tǒng)計

按照前面提到的構(gòu)造方法，可獲得基于表1權(quán)重統(tǒng)計的靜態(tài)Huffman編碼樹，如圖1所示。

圖1 靜態(tài)Huffman編碼樹

從Huffman編碼樹的根結(jié)點出發(fā)，經(jīng)過右子樹、左子樹、左子樹三步，到達包含字符a的葉結(jié)點，獲得a字符的二進制編碼：100。下一個字符b，從根節(jié)點出發(fā)向左子樹前進一步，達到b的葉節(jié)點，二進制編碼為0。類似，將所有的信源數(shù)據(jù)經(jīng)編碼后，得到編碼結(jié)果為：1000101111100。

靜態(tài)Huffman編碼算法給出的編碼樹構(gòu)造方法，要求在實際編碼之前統(tǒng)計被編碼對象中符號出現(xiàn)的概率，并據(jù)此進行編碼樹的構(gòu)造，這在許多實際應(yīng)用場合是不能接受的，同時這種方法也不能對字符串局部統(tǒng)計規(guī)律發(fā)生變化時做出反應(yīng)。因此，為改進該編碼算法，提出了自適應(yīng)Huffman編碼方案。

2 自適應(yīng)Huffman編碼過程

編碼樹初始化時，由于只對信源數(shù)據(jù)流進行一次掃描，不可能預(yù)先知道各符號的出現(xiàn)概率。為對所有符號一致，令Huffman編碼樹初始狀態(tài)只包含一個葉結(jié)點，記為符號NYT，權(quán)重值為0。將一個新符號插入編碼樹時，相應(yīng)符號的出現(xiàn)次數(shù)增加了1，編碼樹中各符號的出現(xiàn)概率發(fā)生了改變。原有Huffman編碼樹已經(jīng)不一定符合具有最小加權(quán)路徑長度這一條件，需要進行調(diào)整，以保持合法Huffman編碼樹的狀態(tài)。

仍以abcddbb作為待編碼的原始信源數(shù)據(jù)串為例，自適應(yīng)Huffman編碼過程如圖2所示。

通過觀察以上步驟，容易發(fā)現(xiàn)自適應(yīng)Huffman編碼的幾個特征：①步驟13的編碼樹與靜態(tài)Huffman編碼樹基本相同，除NYT節(jié)點和符號a節(jié)點組成的子樹替代靜態(tài)Huffman編碼樹中的符號a的葉節(jié)點之外;②每一次輸入新的符號之前，Huffman編碼樹都處于完整可用的正常狀態(tài);③同一個輸入符號，可能產(chǎn)生多種不同的輸出;④同樣輸出結(jié)果，可能由不同的輸入產(chǎn)生。

3 自適應(yīng)Huffman壓縮編碼的C語言實現(xiàn)及程序結(jié)果

自適應(yīng)Huffman編碼算法程序如下所示。

初始化Huffman樹：

對每一個輸入符號

{

對符號編碼;

更新Huffman樹;

}

對一個輸入符號進行Huffman編碼并更新編碼樹的流程圖如圖3所示，自適應(yīng)Huffman編碼算法的程序結(jié)果如圖4所示。

由此可見，自適應(yīng)Huffman壓縮編碼算法在壓縮比上盡管不能和有損壓縮相比，但它改進了靜態(tài)Huffman編碼算法，更大程度上壓縮了圖像網(wǎng)絡(luò)傳輸?shù)娜哂嘈畔⒍鴾p小了網(wǎng)絡(luò)傳輸?shù)男畔⒘?，從而能進一步提高通信質(zhì)量和網(wǎng)絡(luò)傳輸數(shù)據(jù)的效率。

［1］ 陳衍儀.圖像壓縮的分形理論和方法［M］.北京：國防工業(yè)出版社，1997：216-232.

［2］ 馬小虎.多媒體數(shù)據(jù)壓縮標準及實現(xiàn)［M］.北京：電子工業(yè)出版杜，1996：194-198.

［3］ 黎洪松.數(shù)字視頻技術(shù)及其應(yīng)用［M］.北京：清華大學(xué)出版社，1988：375-397.

［4］ 傅組蕓.信息論與編碼［M］.北京：電子工業(yè)出版社，2007：259-267.

An algorithm to achieve adaptive Huffman coding with C language

WEN Guo-zhi
(Department of Mathematics and Physics ，Wuhan Polytechnic University，Wuhan 430023，China)

The algorithm of adaptive Huffman coding is studied by dynamical statistics of the probability of source symbols and construction of the Huffman coding tree step by step with the C language.A solution is proposed about static source code tree which could not make the corresponding revision when the source symbol changes in the local.The results show that adaptive Huffman coding algorithm could further improve the compression ratio and enhance the efficiency of data transmission.

Huffman coding;adaptive;lossless compression

TN 911.21

A

1009-4881(2011)02-0053-05

10.3969/j.issn.1009-4881.2011.02.014

2010-11-19.

2011-03-25.

文國知(1973 －)，男，博士研究生，E-mail：wenguozhi@hotmail.com.