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

文國知

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

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

文國知

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

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

Huffman編碼;自適應;無損壓縮

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

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

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

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

表1 數(shù)據(jù)串abcddbb的概率統(tǒng)計

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

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

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

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

2 自適應Huffman編碼過程

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

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

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

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

自適應Huffman編碼算法程序如下所示。

初始化Huffman樹：

對每一個輸入符號

{

對符號編碼;

更新Huffman樹;

}

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

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

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

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

［3］ 黎洪松.數(shù)字視頻技術及其應用［M］.北京：清華大學出版社，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.