C++實現哈夫曼樹(Huffman Tree)

來自專欄數據結構筆記6 人贊了文章

在了解哈夫曼編碼之前先來認識一下哈夫曼樹，哈夫曼樹作為數據結構中重要的一種，是我們必須要了解的，首先它是樹的一種，那麼它和普通的樹有什麼區別呢？

一、哈夫曼樹(Huffman Tree)的定義

首先給定n個權值作為n個葉子結點，構造一棵二叉樹，若該樹的WPL(帶權路徑)長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。比如下面描述的這一種實例，通過學生成績的分布概率，來知道學生查找成績的頻次，然後我們需要設計一種效率最高（也就是查找所需的時間越小）=深度*頻率（比例），這樣的樹我們稱為是最優的一棵樹，也就是我們的哈夫曼樹(Huffman Tree)。

那麼怎麼樣才可以使我們的效率最高呢，我們看到了上面的圖示，將頻次（比例）最小的放在了樹的第一層，這樣顯然不是我們想要的，會使得效率變得非常低，這裡的WPL是3.15。那麼如何使它的效率達到最高呢？如何我們就會想到將它倒過來，最小的放在最下面，可是其實這樣仍然不是我們想要的，因為樹的深度我們其實可以調節，並不用一次只放置一個兒子節點，於是我們想到這樣。

明顯的，WPL減小了，於是這樣一系列的問題就是我們要說的哈夫曼樹的問題。

二、如何構造哈夫曼樹（Huffman Tree）

那麼怎麼樣來構造出我們想要的哈夫曼樹呢？方法很簡單，只需要在我們已有的權值（例子里的頻次）中，每次都找到2個最小的，將它們構造成一顆二叉樹，再插入我們已經構造好的二叉樹中，將每個值都插完後，我們的哈夫曼樹就構造完成了。直接上圖：

比如權值分別為12345的5個節點

首先找到2個權值最小的1、2，構造一棵樹

然後再找3將其插入

最後是4和5

完成後如下圖

那我們的代碼如何實現呢？如果我們要按如上的方法實現哈夫曼樹，首先我們要找到的就是最小值，如何找到最小值一定是我們需要面對的最關鍵的問題。這裡有2種方法：

1、先將所有的權值排序，如何再建立哈夫曼樹。

2、先建立最小堆，每次從堆頂選元素來建立哈夫曼樹。

這2種方法里，我們傾向於使用第二種方法，因為第二種方法的時間複雜度比較小，只有O(NlogN)。

//c++實現struct TreeNode{ HuffmanTree left; HuffmanTree right; int weight;};HuffmanTree Huffman(MinHeap H){ HuffmanTree T=malloc(sizeof(struct TreeNode)); for(int i=1;i<H->size;i++){ T->left=Delete(H); T->right=Delete(H); T->weight=T->left->weight+T->right->weight; Insert(H,T) } return T;}

三、哈夫曼編碼和其實現？

先來一波官方解釋（可以略過哈~）：

在數據通信中，需要將傳送的文字轉換成二進位的字元串，用0，1碼的不同排列來表示字元。例如，需傳送的報文為「AFTER DATA EAR ARE ART AREA」，這裡用到的字符集為「A，E，R，T，F，D」，各字母出現的次數為{8，4，5，3，1，1}。現要求為這些字母設計編碼。要區別6個字母，最簡單的二進位編碼方式是等長編碼，固定採用3位二進位，可分別用000、001、010、011、100、101對「A，E，R，T，F，D」進行編碼發送，當對方接收報文時再按照三位一分進行解碼。顯然編碼的長度取決報文中不同字元的個數。若報文中可能出現26個不同字元，則固定編碼長度為5。然而，傳送報文時總是希望總長度儘可能短。在實際應用中，各個字元的出現頻度或使用次數是不相同的，如A、B、C的使用頻率遠遠高於X、Y、Z，自然會想到設計編碼時，讓使用頻率高的用短碼，使用頻率低的用長碼，以優化整個報文編碼。

為使不等長編碼為前綴編碼(即要求一個字元的編碼不能是另一個字元編碼的前綴)，可用字符集中的每個字元作為葉子結點生成一棵編碼二叉樹，為了獲得傳送報文的最短長度，可將每個字元的出現頻率作為字元結點的權值賦予該結點上，顯然字使用頻率越小權值越小，權值越小葉子就越靠下，於是頻率小編碼長，頻率高編碼短，這樣就保證了此樹的最小帶權路徑長度效果上就是傳送報文的最短長度。因此，求傳送報文的最短長度問題轉化為求由字符集中的所有字元作為葉子結點，由字元出現頻率作為其權值所產生的哈夫曼樹的問題。利用哈夫曼樹來設計二進位的前綴編碼，既滿足前綴編碼的條件，又保證報文編碼總長最短。

看完上面，稍微了解了一下哈夫曼編碼，我們如何去設計一個哈夫曼編碼，來保證空間使用的最小，來看看下面的例子：

首先，要給出這個例子的答案，我們會想到ASCII碼，由於ASCII碼是8位制，所以我們需要的空間是58*8=464位，更聰明的一點想到使用3進位碼，因為3進位可以用來描述8個字元，這裡只有7個字元，我們得到的答案是58*3=174位。但是如果我們用哈夫曼編碼呢？？出現頻率低的就用長一些的編碼，高的就用短一些的，使用這樣的不等長編碼，能做到嗎？但是問題來了，比如當我們給a編碼00，e 01，i 11，s 1， t 0。假設我們這樣編碼，那如果系統遇到了000110這樣的編碼，返回的字元是aest還是tait呢？這就涉及到了編碼的二義性。有的編碼就變成了另一種編碼的前綴碼。如何避免二義性呢，我們可以用樹來做，使樹的左分支為0，右分支為1，只要當我們的字元只在葉子結點上的時候，就可以完美的避免二義性了。

可是怎樣才能使WPL最小呢？這時我們就要根據頻率來構造一顆哈夫曼樹，問題就解決了~例如下面的例子，我們可以根據頻率，來構造一顆哈夫曼樹，然後每個字元都會在葉子結點上，這樣就完美的解決了我們的問題，實現了哈夫曼編碼，達到了浪費空間最小的目的。