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

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

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

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

4、0時(shí)即可解碼為a，讀到10時(shí)可以解碼為b，以此類推，最終得到解碼后的結(jié)果為abcd。哈夫曼編碼之所以可以這樣解碼，是因?yàn)樗且环N前綴編碼，任何一個(gè)字符的編碼都不會(huì)是另一個(gè)字符編碼的前綴。于是給定一個(gè)編碼后的串，其解碼的結(jié)果是唯一的。二 代碼實(shí)現(xiàn)這里的哈夫曼樹的節(jié)點(diǎn)主要包含兩個(gè)成員：字符及其頻率，另外還必須有其左右兒子指針，父親節(jié)點(diǎn)指針可以看情況添加，這里暫時(shí)不考慮。為了方便，還添加了一個(gè)構(gòu)造函數(shù)，可以給成員賦默認(rèn)值。struct node /哈夫曼樹節(jié)點(diǎn) 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)先隊(duì)列來選擇權(quán)值最小的節(jié)點(diǎn)。隊(duì)列的成員是節(jié)點(diǎn)的指針，為了選擇權(quán)值最小的節(jié)點(diǎn)，需要自己定義比較的規(guī)則，以下是定義比較規(guī)則的仿函數(shù)，實(shí)質(zhì)就是一個(gè)重載了括號(hào)運(yùn)算符的類。注意實(shí)現(xiàn)最小的權(quán)值優(yōu)先，仿函數(shù)里應(yīng)該使用的是大于運(yùn)算。struct cmp /仿函數(shù)，實(shí)現(xiàn)最小優(yōu)先隊(duì)列 bool operator()(node*& a, node*& b) return a-&

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

7、;:iterator p = charSet.begin(); p != charSet.end(); p+) / cout << p->first << " " << p->second << endl; /初始節(jié)點(diǎn)進(jìn)入優(yōu)先隊(duì)列 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(); /每次取出頻率最小的兩個(gè)節(jié)點(diǎn)，生成一個(gè)新的節(jié)點(diǎn)并重新入隊(duì) 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、曼樹得到每個(gè)字符的編碼串。注意每次向左走時(shí)加0，向右走時(shí)加1，到達(dá)葉子節(jié)點(diǎn)即為該字符的編碼。這里只是簡(jiǎn)單打印了編碼表的信息，沒有保存起來，如果需要可以再次使用STL的map進(jìn)行保存。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');解碼時(shí)可以在遍歷編碼串的同時(shí)沿著哈夫曼樹走，到達(dá)葉子節(jié)點(diǎn)時(shí)即得到一個(gè)解碼字符，同時(shí)再次回到根節(jié)點(diǎn)繼續(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) /得到一個(gè)字符 ret += p->ch, p = tree; return ret;因?yàn)檫@里的節(jié)點(diǎn)都是使用new運(yùn)算符動(dòng)態(tài)申請(qǐng)得到，不再使用時(shí)需要釋放掉申請(qǐng)到的資源，以免造成內(nèi)存泄露。void deleteTree(node *tree) /釋放哈夫曼樹申請(qǐng)的節(jié)點(diǎn) if (

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