[科普中國]-H碼

關(guān)于霍夫曼編碼

霍夫曼編碼方案是由David A Huffman在1952年開發(fā)的。這個算法依據(jù)數(shù)據(jù)的出現(xiàn)頻率來編碼數(shù)據(jù)從而可達到數(shù)據(jù)壓縮的目的。用于編碼數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是一棵加權(quán)的二進制樹，又叫霍夫曼樹。

霍夫曼樹有幾個特性：

1.霍夫曼樹必須是一棵二進制樹；

2.霍夫曼樹是加權(quán)的，在數(shù)據(jù)流中出現(xiàn)頻繁的元素在樹的頂部，而很少出現(xiàn)的元素沉到樹的底部；

3.霍夫曼樹的每一個左邊的分支分配一個0(或1)值，而每一個右邊的分支賦值為1(或O)。

為了構(gòu)造一棵霍夫曼樹，需對數(shù)據(jù)進行兩步操作。首先，構(gòu)造一個唯一數(shù)據(jù)元素集和它們的頻率的列表。這個列表按頻率的升值排列。就是說，出現(xiàn)頻率最高的數(shù)據(jù)元素排在表的下部。然后，構(gòu)造實際的霍夫曼樹。選擇頻率最低的兩個元素組成樹的葉。兩片葉的父節(jié)點是它們的頻率之和。這棵樹被插入到列表中(由父節(jié)點的值來決定插到列表中的位置)，而剛才用于組成這棵樹的兩個葉子被從列表中移除。繼續(xù)這個過程直到列表中只留下一個元素，它就是最終的霍夫曼樹的父節(jié)點。

為了將霍夫曼樹用于編碼數(shù)據(jù)，必須建立一種能唯一確定樹中的每一個值的方法。具體做法是把樹的每一個左邊分支賦值為0，而把每一個右邊分支賦值為1。從樹的根開始，找到每一個葉．把沿途經(jīng)過的左、右分支的值按順序排列，就可以用1和0的序列來唯一地標(biāo)識樹中的每一個元素了。

對于數(shù)據(jù)壓縮最后要做的是，遍歷原始數(shù)據(jù)的每一個元素，把與每一個數(shù)據(jù)元素相關(guān)的霍夫曼代碼寫到輸出文件。因為起碼大多數(shù)數(shù)據(jù)元素的霍夫曼表示比它們本來的表示位數(shù)要少，于是達到壓縮的目的。為了此后解碼的需要，原來的編碼信息(霍夫曼樹和所生成的數(shù)據(jù)表)也必須存儲在輸出文件中。1

哈夫曼編碼是依據(jù)符號出現(xiàn)的概率對符號進行編碼，需要對原始數(shù)據(jù)掃描兩遍。第一遍掃描要精確統(tǒng)計原始圖像中每個灰度值出現(xiàn)的概率，第二遍是建立哈夫曼二叉樹并進行編碼，故數(shù)據(jù)壓縮和還原速度較慢，但此法有效簡單，且編碼效率高，所以在一些圖像壓縮標(biāo)準(zhǔn)中被普遍采用。2

特點主要特點如下。

(1)Huffman編碼的構(gòu)造順序明確，但碼不是唯一的。因為在為兩個分支賦值時，可以是左支(或上支)為0，也可以是右支(或下支)為0，造成編碼的不惟一。此外，當(dāng)兩個符號的概率相等時，誰前誰后也是隨機的，構(gòu)造出來的碼字就不是惟一的。

(2)Huffman編碼的字長參差不齊，硬件實現(xiàn)不是很方便。

(3)Huffman編碼在概率分布很不均勻時能夠具有顯著的效果，而在信源分布均勻時，一般不使用Huffman編碼。

(4)對信源進行Huffman編碼后，形成了一個Huffman編碼表。解碼時，必須參照Huffman編碼表才能正確譯碼。

理論研究表明，Huffman編碼是一種接近壓縮比上限的編碼方法，因此它被廣泛用于多種壓縮算法之中。3

步驟Huffman編碼的基本步驟如下。

(1)進行數(shù)據(jù)統(tǒng)計，統(tǒng)計不同信息符號出現(xiàn)的概率。

(2)將信號源的符號按照出現(xiàn)概率遞減的順序排列。

(3)將最下面的兩個最小出現(xiàn)概率進行合并相加，得到的結(jié)果作為新符號的出現(xiàn)概率。

(4)重復(fù)進行步驟1和2直到概率相加的結(jié)果等于1為止。

(5)在合并運算時，概率大的符號用編碼0表示，概率小的符號用編碼1表示。

(6)記錄概率為1處到當(dāng)前信號源符號之間的0，l序列，從而得到每個符號的編碼。3