哈夫曼編碼的原理及C實現(xiàn)

1、哈夫曼編碼的原理及C+實現(xiàn)哈夫曼編碼（Huffman Coding）是一種非常經(jīng)典的編碼方式，實現(xiàn)起來也很簡單，在實際的筆試面試過程中有可能會遇到，這里介紹一下它的原理和一個使用優(yōu)先隊列的實現(xiàn)版本。一 編碼原理哈夫曼編碼是一種可變長的編碼，它依據(jù)字符出現(xiàn)的概率來決定字符編碼的長度，使得出現(xiàn)概率大的字符編碼長度短，出現(xiàn)概率小的字符的編碼長度長，于是可以減少整體的編碼的長度。哈弗曼編碼時首先根據(jù)待編碼的文本統(tǒng)計出每個字符出現(xiàn)的概率，組成初始的節(jié)點。然后每次取出概率最小的兩個節(jié)點，新建一個節(jié)點，使得新建節(jié)點的左右兒子為選取的兩個節(jié)點，并且其概率是兩個節(jié)點概率之和，把新建的節(jié)點再放進所有節(jié)點中重新選擇

2、最小的兩個節(jié)點。重復(fù)此過程直到只剩一個節(jié)點，這個就是哈夫曼樹的根節(jié)點。以下以字符串"aaaaaabbbbccddd"為例進行說明，為了方便，以字符出現(xiàn)的頻數(shù)來代替頻率（實際中通常使用的是頻率，二者效果上是一樣的），經(jīng)過統(tǒng)計，可以知道每個字符出現(xiàn)的頻數(shù)為abcd6423具體建樹過程如下：（1）首先節(jié)點權(quán)值為6、4、2、3，選擇最小的2和3，組成一個根節(jié)點為5的組合節(jié)點。（2）當(dāng)前節(jié)點權(quán)值為6、4、5，選擇最小的4和5，組成一個根節(jié)點為9的組合節(jié)點。（3）當(dāng)前節(jié)點權(quán)值為6、9，選擇最小的6和9，組成一個根節(jié)點為15的組合節(jié)點。（4）當(dāng)前節(jié)點權(quán)值為15，只有一個節(jié)點，哈夫曼樹建立

3、完成。圖示如下：要從哈夫曼樹得到每個字符的編碼，只要在哈夫曼樹中從根節(jié)點遍歷到該字符節(jié)點，每次向左走時加一個0，向右走時加一個1，最終得到的字符串即為該字符的編碼字符串。如從上圖可以看到，a的編碼為0，b的編碼為10，c的編碼為110，d的編碼為111。 當(dāng)遇到一個新的字符串時，比如說"abcd"，要對其編碼，只需要把其中的每個字符相應(yīng)地替換成其編碼字符串即可。 當(dāng)已知一個編碼后的字符串，比如說"010110111"，要對其解碼時，只需從左到右依次掃描該編碼串，當(dāng)讀到的串在哈弗曼編碼表里有對應(yīng)的字符時即解碼為該字符，然后繼續(xù)掃描。在這個例子中，讀到第一個

4、0時即可解碼為a，讀到10時可以解碼為b，以此類推，最終得到解碼后的結(jié)果為abcd。哈夫曼編碼之所以可以這樣解碼，是因為它是一種前綴編碼，任何一個字符的編碼都不會是另一個字符編碼的前綴。于是給定一個編碼后的串，其解碼的結(jié)果是唯一的。二 代碼實現(xiàn)這里的哈夫曼樹的節(jié)點主要包含兩個成員：字符及其頻率，另外還必須有其左右兒子指針，父親節(jié)點指針可以看情況添加，這里暫時不考慮。為了方便，還添加了一個構(gòu)造函數(shù)，可以給成員賦默認(rèn)值。struct node /哈夫曼樹節(jié)點 char ch; /字符 double freq; /出現(xiàn)頻率 node *lchild, *rchild; /左右兒子 node(char

5、 c = 0, double f = 0, node *l = NULL, node *r = NULL) : ch(c), freq(f), lchild(l), rchild(r); 為了提高效率，程序中使用了STL中的優(yōu)先隊列來選擇權(quán)值最小的節(jié)點。隊列的成員是節(jié)點的指針，為了選擇權(quán)值最小的節(jié)點，需要自己定義比較的規(guī)則，以下是定義比較規(guī)則的仿函數(shù)，實質(zhì)就是一個重載了括號運算符的類。注意實現(xiàn)最小的權(quán)值優(yōu)先，仿函數(shù)里應(yīng)該使用的是大于運算。struct cmp /仿函數(shù)，實現(xiàn)最小優(yōu)先隊列 bool operator()(node*& a, node*& b) return a-&

6、gt;freq > b->freq; ;然后是具體的建樹過程。首先需要統(tǒng)計字符出現(xiàn)的次數(shù)，可以非常方便地使用STL的map實現(xiàn)。然后構(gòu)造初始節(jié)點送入優(yōu)先隊列，再循環(huán)取出最小的兩個節(jié)點，生成新的節(jié)點放入隊列。直到隊列只剩一個節(jié)點，即為樹的根節(jié)點。node* createTree(string str) /對一段文本構(gòu)建哈夫曼樹 /統(tǒng)計字符集及其出現(xiàn)頻數(shù) map<char, int> charSet; for (int i = 0; i < str.length(); i+) charSetstri+; /查看統(tǒng)計結(jié)果 /for(map<char, int>

7、;:iterator p = charSet.begin(); p != charSet.end(); p+) / cout << p->first << " " << p->second << endl; /初始節(jié)點進入優(yōu)先隊列 priority_queue<node*, vector<node*>, cmp> que; for(map<char,int>:iterator p = charSet.begin(); p != charSet.end(); p+) que.pus

8、h(new node(p->first, (double)p->second / str.length(); /每次取出頻率最小的兩個節(jié)點，生成一個新的節(jié)點并重新入隊 while (que.size() > 1) node *l = que.top(); que.pop(); node *r = que.top(); que.pop(); node *newnode = new node(0, l->freq + r->freq, l, r); que.push(newnode); return que.top();得到哈夫曼樹之后基本就完成了，接下來可以遍歷哈夫

9、曼樹得到每個字符的編碼串。注意每次向左走時加0，向右走時加1，到達葉子節(jié)點即為該字符的編碼。這里只是簡單打印了編碼表的信息，沒有保存起來，如果需要可以再次使用STL的map進行保存。void printInfo(const node *tree, string code) /遞歸打印編碼信息 if (tree->lchild = NULL && tree->rchild = NULL) cout << tree->ch << ": " << code << endl; return; if (

10、tree->lchild != NULL) printInfo(tree->lchild, code + '0'); if (tree->rchild != NULL) printInfo(tree->rchild, code + '1');解碼時可以在遍歷編碼串的同時沿著哈夫曼樹走，到達葉子節(jié)點時即得到一個解碼字符，同時再次回到根節(jié)點繼續(xù)遍歷。最后得到解碼的結(jié)果。string decode(const node *tree, string str) /解碼 string ret = "" const node *p

11、= tree; for (int i = 0; i < str.length(); i+) p = stri = '0' ? p->lchild : p->rchild; if (p->lchild = NULL && p->rchild = NULL) /得到一個字符 ret += p->ch, p = tree; return ret;因為這里的節(jié)點都是使用new運算符動態(tài)申請得到，不再使用時需要釋放掉申請到的資源，以免造成內(nèi)存泄露。void deleteTree(node *tree) /釋放哈夫曼樹申請的節(jié)點 if (

12、tree->lchild != NULL) deleteTree(tree->lchild); if (tree->rchild != NULL) deleteTree(tree->rchild); delete(tree);下面是一個簡單的測試?yán)?，看程序是否正常運行。int main () string encodeStr = "aaaaaabbbbccddd" node *tree = createTree(encodeStr); printInfo(tree, ""); string decodeStr = "010110111" string str = decod