霍夫曼編碼實現方法的研究

摘要：在信息爆炸的今天，數據壓縮的重要性不言而喻，基本過程有三步：建模表達、二次量化和熵編碼。其中熵編碼又稱為冗余度壓縮。而統計編碼又是熵編碼的重要內容，其主要包括霍夫曼（Huffman）編碼、游程編碼、二進制信源編碼、算術編碼、LZW編碼等。本文以Huffman編碼作為熵編碼的一種代表，介紹關于Huffman編碼的具體實現方法。

關鍵詞：Huffman編碼；二叉樹；權值

中圖分類號：G642.0？搖 文獻標志碼：A ？搖文章編號：1674-9324（2013）26-0248-02

一、引言

1.數值傳輸系統模型如圖1所示。

2.信源編碼：主要是解決有效性的問題。通過對信源的壓縮、擾亂、加密等一系列處理，力求用最少的數碼傳遞最大的信息量，使信號更適宜傳輸。

3.數據壓縮：就是以最少的數碼表示信源所發的信號，減少容納給定消息集合或數據采樣集合的信號空間。

二、統計編碼

對于各種信源都通用的可逆壓縮（無失真編碼）方法，因為大多數計算機文件都不允許在壓縮過程中丟失信息。這類方法主要利用信息或信息序列出現的概率的分布特性，注重尋找概率與碼字長度問題的最優匹配，這叫做統計編碼或概率匹配編碼。而霍夫曼（Huffman）編碼就是其中具有代表性的一種編碼方案[1]。

三、霍夫曼（Huffman）編碼原理

Huffman編碼是1952年為文本文件而建立的，是一種統計編碼。它完全依據字符出現的概率來構造平均長度最短的異字頭碼字，屬于無損壓縮編碼。Huffman編碼的碼長是變化的，對于出現概率高的信息，編碼的長度較短；而對于出現概率低的信息，編碼長度較長。這樣，處理全部信息的總碼長一定小于實際信息的符號長度[2]。方法、步驟：（1）將信號源的符號出現的概率（在此稱為權值）{w1，w2，...，wn}構造成n棵二叉樹集合F={T1，T2，...，Tn}，其中每棵二叉樹Ti中只有一個帶權為wi的根結點，其左右子樹均為空。（2）在F中選取兩棵根結點的權值最小的樹作為左右子樹構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和。（3）在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中。（4）重復（2）和（3），直到F只含一棵樹為止。這棵樹便是霍夫曼（Huffman）樹。（5）在合并中約定權值小的根結點在左子樹上，權值大的在右子樹上。然后在每個左分支上標記為“0”，右分支上標記為“1”。最后記錄從霍夫曼（Huffman）樹的根結點到每個葉子結點所經過的分支上的“0”或“1”的序列，從而得到每個符號的Huffman編碼。[3]

上述編碼的平均碼字長度R=（2+2+2+3+3）/5=2.4。說明：由于“1”和“0”的指定是任意的，故由上述過程編出的最佳碼不是唯一的，但其平均碼長是一樣的，故不影響編碼效率與數據壓縮性能。

四、Huffman編碼的具體實現

//——-以下部分代碼是在Huffman樹上從根逆向求每個字符的Huffman編碼——-HC=（HuffmanCode）malloc（（n+1）*sizeof（char*））；

cd=（char*）malloc（n*sizeof（char））；cdn-1]=“.parent；f！=0；c=f，f=HTf].parent）

if（HTf].lchild==c）cd——start]=“0”；elsecd——start]=“1”；

HCi]=（char*）malloc（n-start）*sizeof（char））；

Strcpy（HCi]，cdstart]）；

}free（cd）；

}//HuffmanCoding

五、結論

Huffamn編碼的實現方法有很多種，本文只是概述了基于數據結構的Huffman編碼的算法思想。

雖然Huffman編碼優點非常突出，但通過作者的研究發現，在具體的實現過程中，其局限性也不容忽視。因此，在今后對Huffman編碼的研究與應用中，應該揚長避短，更好發揮此編碼的自身優勢。

參考文獻：

[1]吳樂南.數據壓縮[M].北京：電子工業出版社，2003.

[2]嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京：清華大學出版社，1997.

[3]王永剛.奇妙的二叉樹[D].程序員，2003，（9）.