HUFFMAN編碼技術應用研究

徐愛蕓

摘要：現代社會每天產生海量級的信息，而這些信息的存儲和傳輸需要大量的存儲空間，信息本身有很大的的冗余度，因此信息必須采用壓縮技術處理。Huffman編碼是一種流行而又高效的無損編碼，利用Huffman編碼就可能比普通的編碼方法使用的碼數少，提高了編碼的有效性。

關鍵詞：Huffman編碼;最優二叉樹;無損壓縮

Huffman編碼根據消息出現概率的分布特性進行統計，尋找概率與碼字長度間的最優匹配，利用數據的統計冗余進行壓縮，基于符號出現概率的不同賦予長短不一的碼字，出現概率越大的符號，相應的碼越短;出現概率越小的符號，其碼越長。算法用一串二進制位（稱作位碼）來代替每個字符，再將這些位碼寫進壓縮后的文件。利用位碼壓縮的關鍵之處是選擇最優二叉樹，在Huffman樹中沒有一個位碼是另一個位碼的前綴，每一個字符都在樹的葉子結點中出現。

Huffman編碼一般用來壓縮多媒體信息，如文本、程序文件和特色的圖像等，實現對數據的無損壓縮。解碼時，在消息和碼字之間找到明確的一一對應關系，恢復時能準確無誤地再現出來，完全恢復原始數據而不引起任何失真。

1編碼步驟

Huffman編碼是一種一致性編碼法，以Huffman樹即帶權路徑長度最小的二叉樹構建變長最佳編碼，其步驟如下：

（1）將信源符號按其出現的概率，由大到小順序排列;

（2）將兩個最小的概率的信源符號進行組合相加，并重復這一步驟，始終將較大的概率分支放在上部，直到只剩下一個信源符號且概率達到1.0為止;

（3）對每對組合的上邊一個指定為1，下邊一個指定為0;

（4）畫出由每個信源符號到概率1處的路徑，記下沿路徑的1和0;

（5）對于每個信源符號都寫出1、0序列，就得到非等長的Huffman碼。

2 Huffman編碼設計

例如要壓縮字符串“abaadffbghadffda”，首先統計各字符出現的概率：

a： 5/16，b：2 /16，d：3 /16，f： 4/16，g： 1/16，h：1/16

上述原字符的二進制編碼為 ： 01100001 01100010 01100001 01100001 01100100 01100110 01100110 01100010 01100111 01101000 01100001 01100100 01100110 01100110 01100100 01100001，共128bit。

構造Huffman樹，樹從最下層的結點開始構造，選取概率最小和次小的兩個符號作為左右子樹構造一棵新的二叉樹，新二叉樹根結點的權值為其左右子樹根結點權值之和。重復這一過程，最后得到一個橫放的碼樹即Huffman樹。

Huffman編碼就是將從根結點出發到葉結點的路徑上各左、右分支的編碼順序排列就得到了該葉子結點所對應的字符的二進制前綴編碼，每個字符轉換為一個唯一的二進制位串，則該字符串中每個字符的Huffman編碼為： a：11，b：011，d：00，f： 10，g： 0100，h：0101

原字符串的Huffman編碼為：11 011 11 11 00 10 10 011 0100 0101 11 00 10 10 00 11，共38bit。

3 Huffman編碼分析

（1）壓縮比

壓縮比是壓縮前后所需的信息存儲量之比，上面的例子中可以計算出壓縮比為：38/128=30%，所以說Huffman編碼在數據壓縮中的壓縮效果是非常好的，只要Huffman編碼表基于大量概率統計，其編碼效果是足夠好的。

（2）時間空間效率高

Huffman編碼是最佳變長碼，得到的是最短的編碼長度，有效節省空間。

（3）Huffman編碼是無失真的數據壓縮編碼，解碼之后可以無失真的恢復原信息。

（4）Huffman編碼的實現方法有很多，比如說MATLAB實現，C語言實現等。

4 Huffman編碼不足

（1）Huffman編碼要精確統計出每個符號出現的概率，通常要進行兩次掃描：第一遍掃描產生統計結果，第二次掃描完成編碼，所以編碼速度相對慢。

（2）Huffman編碼只能用整數來表示單個符號而不能用小數。

（3）只有當信息源各符號出現的概率很不平均的時候，霍夫曼編碼的效果才明顯。

（4）哈夫曼方法構造出來的碼不是唯一的。

5譯碼

解碼時，將碼字用碼值代替。解碼時必須參照這一Huffman編碼表才能正確譯碼，所以在信源的存儲與傳輸過程中必須首先存儲或傳輸這一Huffman編碼表。

結束語

Huffman編碼是最佳變長碼，編碼的效率高，它依賴于信源的統計特性，如果消息數很大，需要存儲的碼表也要很大，會影響存儲量、編碼以及譯碼速度等性能。

參考文獻

[1]孟彩霞.計算機軟件基礎，西安電子科技大學出版社，2015.1.

[2]李忠月.數據結構與算法（C語言版）.北京大學出版社，2019.3.