哈夫曼算法原理

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

　　1.為每個符號建立一個葉子節點，并加上其相應的發生頻率

　　2.當有一個以上的節點存在時，進行下列循環：

　　1）把這些節點作為帶權值的二叉樹的根節點，左右子樹為空

　　2）選擇兩棵根結點權值最小的樹作為左右子樹構造一棵新的二叉樹，且至新的二叉樹的根結點的權值為其左右子樹上根結點的權值之和。

　　3）把權值最小的兩個根節點移除

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

　　5）最后剩下的節點暨為根節點，此時二叉樹已經完成。

　　哈夫曼樹的應用

　　哈夫曼編碼：

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

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

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

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

　　滿足上述要求的二進制編碼稱為最優前綴編碼。 上述要求的第一條是為了提高傳輸的速度，第二條是為了保證傳輸的信息在譯碼時無二性，所以在字符的編碼中間不需要添加任意的分割符。

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

　　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｝ 利用哈夫曼算法構造出如下圖所示的哈夫曼樹：

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

　　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

　　編碼的結果是，出現頻率大的字符其編碼較短，出現頻率較小的字符其編碼較長。