哈夫曼樹【最優二叉樹】【Huffman】

【轉載】隻為讓價值共享，如有侵權敬請見諒！

一、哈夫曼樹的概念和定義

什麼是哈夫曼樹？

讓我們先舉一個例子。

判定樹：

        在很多問題的處理過程中，需要進行大量的條件判斷，這些判斷結構的設計直接影響着程式的執行效率。例如，編制一個程式，将百分制轉換成五個等級輸出。大家可能認為這個程式很簡單，并且很快就可以用下列形式編寫出來：

1. if(score<60)  
2.     cout<<"Bad"<<endl;  
3. else if(score<70)  
4.     cout<<"Pass"<<endl  
5. else if(score<80)  
6.     cout<<"General"<<endl;  
7. else if(score<90)  
8.     cout<<"Good"<<endl;  
9. else  
10.     cout<<"Very good!"<<endl;  

若考慮上述程式所耗費的時間，就會發現該程式的缺陷。在實際中，學生成績在五個等級上的分布是不均勻的。當學生百分制成績的錄入量很大時，上述判定過程需要反複調用，此時程式的執行效率将成為一個嚴重問題。

但在實際應用中，往往各個分數段的分布并不是均勻的。下面就是在一次考試中某門課程的各分數段的分布情況： 

下面我們就利用哈夫曼樹尋找一棵最佳判定樹，即總的比較次數最少的判定樹。

第一種構造方式：

第二種構造方式：

這兩種方式，顯然後者的判定過程的效率要比前者高。在也沒有别地判定過程比第二種方式的效率更高。

我們稱判定過程最優的二叉樹為哈夫曼樹，又稱最優二叉樹

===================================================================================================

 定義哈夫曼樹之前先說明幾個與哈夫曼樹有關的概念：

路徑： 樹中一個結點到另一個結點之間的分支構成這兩個結點之間的路徑。

路徑長度：路徑上的分枝數目稱作路徑長度。

樹的路徑長度：從樹根到每一個結點的路徑長度之和。

結點的帶權路徑長度：在一棵樹中，如果其結點上附帶有一個權值，通常把該結點的路徑長度與該結點上的權值

                                                              之積稱為該結點的帶權路徑長度（weighted path length）

  什麼是權值?( From 百度百科 )

    　計算機領域中（

資料結構

）

　　權值就是定義的路徑上面的值。可以這樣了解為節點間的距離。通常指字元對應的二進制編碼出現的機率。

　　至于

霍夫曼

樹中的權值可以了解為：權值大表明出現機率大！

　　一個結點的權值實際上就是這個結點子樹在整個樹中所占的比例.

　　abcd四個

葉子結點

的權值為7,5,2,4. 這個7,5,2,4是根據實際情況得到的,比如說從一段文本中統計出abcd四個字母出現的次數分别為7,5,2,4. 說a結點的權值為7,意思是說a結點在系統中占有7這個份量.實際上也可以化為百分比來表示,但反而麻煩,實際上是一樣的.

樹的帶權路徑長度：如果樹中每個葉子上都帶有一個權值，則把樹中所有葉子的帶權路徑長度之和稱為樹的帶

                                   權路徑長度。

             設某二叉樹有n個帶權值的葉子結點，則該二叉樹的帶權路徑長度記為：

公式中，Wk為第k個葉子結點的權值；Lk為該結點的路徑長度。

示例：

======================================================================================================

一般來說，用n（n>0）個帶權值的葉子來構造二叉樹，限定二叉樹中除了這n個葉子外隻能出現度為2的結點。

那麼符合這樣條件的二叉樹往往可構造出許多顆，

其中帶權路徑長度最小的二叉樹就稱為哈夫曼樹或最優二叉樹

===============================================================================

  二、哈夫曼樹的構造

根據哈弗曼樹的定義，一棵二叉樹要使其WPL值最小，必須使權值越大的葉子結點越靠近根結點，而權值越小的葉子結點

越遠離根結點。

哈弗曼依據這一特點提出了一種構造最優二叉樹的方法，其基本思想如下：

下面示範了用Huffman算法構造一棵Huffman樹的過程：

三、哈夫曼樹的在編碼中的應用

在電文傳輸中，需要将電文中出現的每個字元進行二進制編碼。在設計編碼時需要遵守兩個原則：

（1）發送方傳輸的二進制編碼，到接收方解碼後必須具有唯一性，即解碼結果與發送方發送的電文完全一樣；

（2）發送的二進制編碼盡可能地短。下面我們介紹兩種編碼的方式。

1. 等長編碼

            這種編碼方式的特點是每個字元的編碼長度相同（編碼長度就是每個編碼所含的二進制位數）。假設字元集隻含有4個字元A，B，C，D，用二進制兩位表示的編碼分别為00，01，10，11。若現在有一段電文為：ABACCDA，則應發送二進制序列：00010010101100，總長度為14位。當接收方接收到這段電文後，将按兩位一段進行譯碼。這種編碼的特點是譯碼簡單且具有唯一性，但編碼長度并不是最短的。

2. 不等長編碼

            在傳送電文時，為了使其二進制位數盡可能地少，可以将每個字元的編碼設計為不等長的，使用頻度較高的字元配置設定一個相對比較短的編碼，使用頻度較低的字元配置設定一個比較長的編碼。例如，可以為A，B，C，D四個字元分别配置設定0，00，1，01，并可将上述電文用二進制序列：000011010發送，其長度隻有9個二進制位，但随之帶來了一個問題，接收方接到這段電文後無法進行譯碼，因為無法斷定前面4個0是4個A，1個B、2個A，還是2個B，即譯碼不唯一，是以這種編碼方法不可使用。

是以，為了設計長短不等的編碼，以便減少電文的總長，還必須考慮編碼的唯一性，即在建立不等長編碼時必須使任何一個字元的編碼都不是另一個字元的字首，這宗編碼稱為字首編碼（prefix  code）

（1）利用字元集中每個字元的使用頻率作為權值構造一個哈夫曼樹；

（2）從根結點開始，為到每個葉子結點路徑上的左分支賦予0，右分支賦予1，并從根到葉子方向形成該葉子結點的編碼

例題：

假設一個文本檔案TFile中隻包含7個字元{A，B，C，D，E，F，G}，這7個字元在文本中出現的次數為{5，24，7，17，34，5，13}

利用哈夫曼樹可以為檔案TFile構造出符合字首編碼要求的不等長編碼

具體做法：

1. 将TFile中7個字元都作為葉子結點，每個字元出現次數作為該葉子結點的權值

2. 規定哈夫曼樹中所有左分支表示字元0，所有右分支表示字元1,将依次從根結點到每個葉子結點所經過的分支的二進制位的序列作為該

     結點對應的字元編碼

3. 由于從根結點到任何一個葉子結點都不可能經過其他葉子，這種編碼一定是字首編碼，哈夫曼樹的帶權路徑長度正好是檔案TFile編碼

    的總長度

通過哈夫曼樹來構造的編碼稱為哈弗曼編碼（huffman code）

[cpp] 

view plain copy

1. #include<iostream>  
2. #include<cstdio>  
3. #include<cstring>  
4. using namespace std;  
5. #define N 10         // 帶編碼字元的個數，即樹中葉結點的最大個數  
6. #define M (2*N-1)    // 樹中總的結點數目  
7. class HTNode{        // 樹中結點的結構  
8. public:   
9.     unsigned int weight;  
10.     unsigned int parent,lchild,rchild;  
11. };                      
12. class HTCode{  
13. public:  
14.     char data;      // 待編碼的字元  
15.     int weight;     // 字元的權值  
16.     char code[N];   // 字元的編碼  
17. };  
18. void Init(HTCode hc[], int *n){  
19. // 初始化，讀入待編碼字元的個數n，從鍵盤輸入n個字元和n個權值  
20.     int i;  
21.     printf("input n = ");  
22.     scanf("%d",&(*n));  
23.     printf("\ninput %d character\n",*n);  
24.     fflush(stdin);  
25.     for(i=1; i<=*n; ++i)  
26.         scanf("%c",&hc[i].data);  
27.     printf("\ninput %d weight\n",*n);  
29.         scanf("%d",&(hc[i].weight) );  
31. }//  
32. void Select(HTNode ht[], int k, int *s1, int *s2){  
33. // ht[1...k]中選擇parent為0，并且weight最小的兩個結點，其序号由指針變量s1，s2訓示  
35.     for(i=1; i<=k && ht[i].parent != 0; ++i){   
36.         ; ;  
37.     }  
38.     *s1 = i;  
39.     for(i=1; i<=k; ++i){  
40.         if(ht[i].parent==0 && ht[i].weight<ht[*s1].weight)  
41.             *s1 = i;  
44.         if(ht[i].parent==0 && i!=*s1)  
45.             break;  
47.     *s2 = i;  
49.         if(ht[i].parent==0 && i!=*s1 && ht[i].weight<ht[*s2].weight)  
50.             *s2 = i;  
52. }  
53. void HuffmanCoding(HTNode ht[],HTCode hc[],int n){  
54. // 構造Huffman樹ht，并求出n個字元的編碼  
55.     char cd[N];  
56.     int i,j,m,c,f,s1,s2,start;  
57.     m = 2*n-1;  
58.     for(i=1; i<=m; ++i){  
59.         if(i <= n)  
60.             ht[i].weight = hc[i].weight;  
61.         else  
62.             ht[i].parent = 0;  
63.         ht[i].parent = ht[i].lchild = ht[i].rchild = 0;  
65.     for(i=n+1; i<=m; ++i){  
66.         Select(ht, i-1, &s1, &s2);  
67.         ht[s1].parent = i;  
68.         ht[s2].parent = i;  
69.         ht[i].lchild = s1;  
70.         ht[i].rchild = s2;  
71.         ht[i].weight = ht[s1].weight+ht[s2].weight;  
73.     cd[n-1] = '\0';  
74.     for(i=1; i<=n; ++i){  
75.         start = n-1;  
76.         for(c=i,f=ht[i].parent; f; c=f,f=ht[f].parent){  
77.             if(ht[f].lchild == c)  
78.                 cd[--start] = '0';  
79.             else  
80.                 cd[--start] = '1';  
81.         }  
82.         strcpy(hc[i].code, &cd[start]);  
85. int main()  
86. {  
87.     int i,m,n,w[N+1];  
88.     HTNode ht[M+1];  
89.     HTCode hc[N+1];  
90.     Init(hc, &n);     // 初始化  
91.     HuffmanCoding(ht,hc,n);   // 構造Huffman樹，并形成字元的編碼  
92.     for(i=1; i<=n; ++i)    
93.         printf("\n%c---%s",hc[i].data,hc[i].code);    
94.     printf("\n");  
95.     return 0;  
96. }  uffman