徐愛蕓

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

關(guān)鍵詞：Huffman編碼;最優(yōu)二叉樹;無損壓縮

Huffman編碼根據(jù)消息出現(xiàn)概率的分布特性進(jìn)行統(tǒng)計(jì)，尋找概率與碼字長度間的最優(yōu)匹配，利用數(shù)據(jù)的統(tǒng)計(jì)冗余進(jìn)行壓縮，基于符號(hào)出現(xiàn)概率的不同賦予長短不一的碼字，出現(xiàn)概率越大的符號(hào)，相應(yīng)的碼越短;出現(xiàn)概率越小的符號(hào)，其碼越長。算法用一串二進(jìn)制位（稱作位碼）來代替每個(gè)字符，再將這些位碼寫進(jìn)壓縮后的文件。利用位碼壓縮的關(guān)鍵之處是選擇最優(yōu)二叉樹，在Huffman樹中沒有一個(gè)位碼是另一個(gè)位碼的前綴，每一個(gè)字符都在樹的葉子結(jié)點(diǎn)中出現(xiàn)。

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

1編碼步驟

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

（1）將信源符號(hào)按其出現(xiàn)的概率，由大到小順序排列;

（2）將兩個(gè)最小的概率的信源符號(hào)進(jìn)行組合相加，并重復(fù)這一步驟，始終將較大的概率分支放在上部，直到只剩下一個(gè)信源符號(hào)且概率達(dá)到1.0為止;

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

（4）畫出由每個(gè)信源符號(hào)到概率1處的路徑，記下沿路徑的1和0;

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

2 Huffman編碼設(shè)計(jì)

例如要壓縮字符串“abaadffbghadffda”，首先統(tǒng)計(jì)各字符出現(xiàn)的概率：

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

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

構(gòu)造Huffman樹，樹從最下層的結(jié)點(diǎn)開始構(gòu)造，選取概率最小和次小的兩個(gè)符號(hào)作為左右子樹構(gòu)造一棵新的二叉樹，新二叉樹根結(jié)點(diǎn)的權(quán)值為其左右子樹根結(jié)點(diǎn)權(quán)值之和。重復(fù)這一過程，最后得到一個(gè)橫放的碼樹即Huffman樹。

Huffman編碼就是將從根結(jié)點(diǎn)出發(fā)到葉結(jié)點(diǎn)的路徑上各左、右分支的編碼順序排列就得到了該葉子結(jié)點(diǎn)所對應(yīng)的字符的二進(jìn)制前綴編碼，每個(gè)字符轉(zhuǎn)換為一個(gè)唯一的二進(jìn)制位串，則該字符串中每個(gè)字符的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）壓縮比

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

（2）時(shí)間空間效率高

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

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

（4）Huffman編碼的實(shí)現(xiàn)方法有很多，比如說MATLAB實(shí)現(xiàn)，C語言實(shí)現(xiàn)等。

4 Huffman編碼不足

（1）Huffman編碼要精確統(tǒng)計(jì)出每個(gè)符號(hào)出現(xiàn)的概率，通常要進(jìn)行兩次掃描：第一遍掃描產(chǎn)生統(tǒng)計(jì)結(jié)果，第二次掃描完成編碼，所以編碼速度相對慢。

（2）Huffman編碼只能用整數(shù)來表示單個(gè)符號(hào)而不能用小數(shù)。

（3）只有當(dāng)信息源各符號(hào)出現(xiàn)的概率很不平均的時(shí)候，霍夫曼編碼的效果才明顯。

（4）哈夫曼方法構(gòu)造出來的碼不是唯一的。

5譯碼

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

結(jié)束語

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

參考文獻(xiàn)

[1]孟彩霞.計(jì)算機(jī)軟件基礎(chǔ)，西安電子科技大學(xué)出版社，2015.1.

[2]李忠月.數(shù)據(jù)結(jié)構(gòu)與算法（C語言版）.北京大學(xué)出版社，2019.3.