哈夫曼算法原理

　　1952年， David A. Huffman提出了一個不同的算法，這個算法可以為任何的可能性提供出一個理想的樹。香農(nóng)-范諾編碼（Shanno-Fano）是從樹的根節(jié)點到葉子節(jié)點所進行的的編碼，哈夫曼編碼算法卻是從相反的方向，暨從葉子節(jié)點到根節(jié)點的方向編碼的。

　　1.為每個符號建立一個葉子節(jié)點，并加上其相應(yīng)的發(fā)生頻率

　　2.當(dāng)有一個以上的節(jié)點存在時，進行下列循環(huán)：

　　1）把這些節(jié)點作為帶權(quán)值的二叉樹的根節(jié)點，左右子樹為空

　　2）選擇兩棵根結(jié)點權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且至新的二叉樹的根結(jié)點的權(quán)值為其左右子樹上根結(jié)點的權(quán)值之和。

　　3）把權(quán)值最小的兩個根節(jié)點移除

　　4）將新的二叉樹加入隊列中。

　　5）最后剩下的節(jié)點暨為根節(jié)點，此時二叉樹已經(jīng)完成。

　　哈夫曼樹的應(yīng)用

　　哈夫曼編碼：

　　哈夫曼樹可以直接應(yīng)用于通信及數(shù)據(jù)傳送中的二進制編碼。設(shè)： D=｛d1，d2，d3…dn｝為需要編碼的字符集合。

　　W=｛w1，w2，w3，…wn｝為D中各字符出現(xiàn)的頻率。 現(xiàn)要對D中的字符進行二進制編碼，使得：

　?。?） 按給出的編碼傳輸文件時，通信編碼的總長最短。

　　（2） 若di不等于dj，則di的編碼不可能是dj的編碼的開始部分（前綴）。

　　滿足上述要求的二進制編碼稱為最優(yōu)前綴編碼。 上述要求的第一條是為了提高傳輸?shù)乃俣?，第二條是為了保證傳輸?shù)?a target="_blank">信息在譯碼時無二性，所以在字符的編碼中間不需要添加任意的分割符。

　　對于這個問題，可以利用哈夫曼樹加以解決：用d1，d2，d3…dn作為外部結(jié)點，用w1，w2，w3…wn作為外部結(jié)點的權(quán)，構(gòu)造哈夫曼樹。在哈夫曼樹中把從每個結(jié)點引向其左子結(jié)點的邊標(biāo)上二進制數(shù)“0”，把從每個結(jié)點引向右子節(jié)點的邊標(biāo)上二進制數(shù)“1”，從根到每個葉結(jié)點的路徑上的二進制數(shù)連接起來，就是這個葉結(jié)點所代表字符的最優(yōu)前綴編碼。通常把這種編碼稱為哈夫曼編碼。例如：

　　D=｛d1，d2，d3，d4，d5，d6，d7，d8，d9，d10，d11，d12，d13｝ W=｛2，3，5，7，11，13，17，19，23，29，31，37，41｝ 利用哈夫曼算法構(gòu)造出如下圖所示的哈夫曼樹：

　　從而得到各字符的編碼為：

　　d1:1011110 d2:1011111

　　d3:101110 d4:10110

　　d5:0100 d6:0101

　　d7:1010 d8:000

　　d9:001 d10:011

　　d11:100 d12:110

　　d13:111

　　編碼的結(jié)果是，出現(xiàn)頻率大的字符其編碼較短，出現(xiàn)頻率較小的字符其編碼較長。