您好,登錄后才能下訂單哦!
這篇文章主要講解了“C++哈夫曼樹的原理是什么及怎么實現(xiàn)”,文中的講解內(nèi)容簡單清晰,易于學(xué)習(xí)與理解,下面請大家跟著小編的思路慢慢深入,一起來研究和學(xué)習(xí)“C++哈夫曼樹的原理是什么及怎么實現(xiàn)”吧!
什么是哈夫曼樹?
把權(quán)值不同的n
個結(jié)點構(gòu)造成一棵二叉樹,如果此樹滿足以下幾個條件:
此 n 個結(jié)點為二叉樹的葉結(jié)點 。
權(quán)值較大的結(jié)點離根結(jié)點較近,權(quán)值較小的結(jié)點離根結(jié)點較遠(yuǎn)。
該樹的帶權(quán)路徑長度是所有可能構(gòu)建的二叉樹中最小的。
則稱符合上述條件的二叉樹為最優(yōu)二叉樹,也稱為哈夫曼樹(Huffman Tree)。
構(gòu)建哈夫曼樹的目的是什么?
用來解決在通信系統(tǒng)中如何使用最少的二進(jìn)制位編碼字符信息。
哈夫曼樹產(chǎn)生的背景:
在通信系統(tǒng)中傳遞一串字符串文本時,需要對這一串字符串文本信息進(jìn)行二進(jìn)制編碼。編碼時如何保證所用到的bit
位是最少的,或保證整個編碼后的傳輸長度最短。
現(xiàn)假設(shè)字符串由ABCD 4
個字符組成,最直接的想法是使用 2
個bit
位進(jìn)行等長編碼,如下表格所示:
字符 | 編碼 |
---|---|
A | 00 |
B | 01 |
C | 10 |
D | 11 |
傳輸ABCD
字符串一次時,所需bit
為 2
位,當(dāng)通信次數(shù)達(dá)到 n
次時,則需要的總傳輸長度為 n*2
。當(dāng)字符串的傳輸次數(shù)為 1000
次時,所需要傳輸?shù)目傞L度為 2000
個bit
。
使用等長編碼時,如果傳輸?shù)膱笪闹杏?nbsp;26
個不同字符時,因需要對每一個字符進(jìn)行編碼,至少需要 5
位bit
。
但在實際應(yīng)用中,各個字符的出現(xiàn)頻率或使用次數(shù)是不相同的,如A、B、C
的使用頻率遠(yuǎn)遠(yuǎn)高于X、Y、Z
。使用等長編碼特點是無論字符出現(xiàn)的頻率差異有多大,每一個字符都得使用相同的bit
位。
哈夫曼的設(shè)計思想:
對字符串信息進(jìn)行編碼設(shè)計時,讓使用頻率高的字符使用短碼
,使用頻率低的用長碼
,以優(yōu)化整個信息編碼的長度。
基于這種簡單、樸素的想法設(shè)計出來的編碼也稱為不等長編碼
。
哈夫曼不等長編碼的具體思路如下:
如現(xiàn)在要發(fā)送僅由A、B、C、D 4
個字符組成的報文信息 ,A
字符在信息中占比為 50%
,B
的占比是 20%
,C
的占比是 15%
, D
的 占比是10%
。
不等長編碼的樸實思想是字符
的占比越大,所用的bit
位就少,占比越小,所用bit
位越多。如下為每一個字符使用的bit
位數(shù):
A
使用 1
位bit
編碼。
B
使用 2
位 bit
編碼。
C
使用 3
位 bit
編碼。
D
使用 3
位 bit
編碼。
具體編碼如下表格所示:
字符 | 占比 | 編碼 |
---|---|---|
A | 0.5 | 0 |
B | 0.2 | 10 |
C | 0.15 | 110 |
D | 0.1 | 111 |
如此編碼后,是否真的比前面的等長編碼所使用的總bit
位要少?
計算結(jié)果=0.5*1+0.2*2+0.15*3+0.1*3=1.65
。
先計算每一個字符在報文信息中的占比乘以字符所使用的bit
位。
然后對上述每一個字符計算后的結(jié)果進(jìn)行相加。
顯然,編碼ABCD
只需要 1.65
個bit
,比等長編碼用到的2 個 bit
位要少 。當(dāng)傳輸信息量為 1000
時,總共所需要的bit
位=1.65*1000=1650 bit
。
哈夫曼編碼和哈夫曼樹有什么關(guān)系?
因為字符的編碼是通過構(gòu)建一棵自下向上的二叉樹推導(dǎo)出來的,如下圖所示:
哈夫曼樹的特點:
信息結(jié)點都是葉子結(jié)點。
葉子結(jié)點具有權(quán)值。如上二叉樹,A
結(jié)點權(quán)值為0.5
,B
結(jié)點權(quán)值為0.2
,C
結(jié)點權(quán)值為0.15
,D
結(jié)點權(quán)值為 0.1
。
哈夫曼編碼為不等長前綴編碼(即要求一個字符的編碼不能是另一個字符編碼的前綴)。
從根結(jié)點開始,為左右分支分別編號0
和1
,然后順序連接從根結(jié)點到葉結(jié)點所有分支上的編號得到字符的編碼。
相信大家對哈夫曼樹有了一個大概了解,至于如何通過構(gòu)建哈夫曼樹,咱們繼續(xù)再聊。
在構(gòu)建哈夫曼樹之前,先了解幾個相關(guān)概念:
路徑和路徑長度:在一棵樹中,從一個結(jié)點往下可以達(dá)到的孩子或?qū)O子結(jié)點之間的通路,稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點的層數(shù)為1
,則從根結(jié)點到第L
層結(jié)點的路徑長度為L-1
。
結(jié)點的權(quán)及帶權(quán)路徑長度:若將樹中結(jié)點賦給一個有著某種含義的數(shù)值,則這個數(shù)值稱為該結(jié)點的權(quán)。結(jié)點的帶權(quán)路徑長度為:從根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。
樹的帶權(quán)路徑長度:樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點的帶權(quán)路徑長度之和,記為WPL
。
如有權(quán)值為{3,4,9,15}
的 4
個結(jié)點,則可構(gòu)造出不同的二叉樹,其帶權(quán)路徑長度也會不同。如下 3
種二叉樹中,B
的樹帶權(quán)路徑長度是最小的。
哈夫曼樹
的構(gòu)建過程就是要保證樹的帶權(quán)路徑長度
最小。
那么,如何構(gòu)建二叉樹,才能保證構(gòu)建出來的二叉樹的帶權(quán)路徑長度最???
如有一字符串信息由 ABCDEFGH 8個字符組成,每一個字符的權(quán)值分別為{3,6,12,9,4,8,21,22}
,構(gòu)建最優(yōu)哈夫曼樹的流程:
1.以每一個結(jié)點為根結(jié)點構(gòu)建一個單根二叉樹,二叉樹的左右子結(jié)點為空,根結(jié)點的權(quán)值為每個結(jié)點的權(quán)值。并存儲到一個樹集合中。
2.從樹集合中選擇根結(jié)點的權(quán)值最小的 2
個樹。重新構(gòu)建一棵新二叉樹,讓剛選擇出來的2
棵樹的根結(jié)點成為這棵新樹的左右子結(jié)點,新樹的根結(jié)點的權(quán)值為 2
個左右子結(jié)點權(quán)值的和。構(gòu)建完成后從樹集合中刪除原來 2
個結(jié)點,并把新二叉樹放入樹集合中。
如下圖所示。權(quán)值為 3
和4
的結(jié)點為新二叉樹的左右子結(jié)點,新樹根結(jié)點的權(quán)值為7
。
3.重復(fù)第二步,直到樹集合中只有一個根結(jié)點為止。
當(dāng)集合中只存在一個根結(jié)點時,停止構(gòu)建,并且為最后生成樹的每一個非葉子結(jié)點的左結(jié)點分支標(biāo)注0
,右結(jié)點分支標(biāo)注1
。如下圖所示:
通過上述從下向上
的思想構(gòu)建出來的二叉樹,可以保證權(quán)值較小的結(jié)點離根結(jié)點較遠(yuǎn),權(quán)值較大的結(jié)點離根結(jié)點較近。最終二叉樹的帶權(quán)路徑長度: WPL=(3+4)*5+6*4+(8+9+12)*3+(21+22)*2=232
。并且此樹的帶權(quán)路徑長度是所有可能構(gòu)建出來的二叉樹中最小的。
上述的構(gòu)建思想即為哈夫曼樹設(shè)計思想,不同權(quán)值的字符編碼就是結(jié)點路徑上0
和1
的順序組合。如下表所述,權(quán)值越大,其編碼越小,權(quán)值越小,其編碼越大。其編碼長度即從根結(jié)點到此葉結(jié)點的路徑長度。
字符 | 權(quán)值 | 編碼 |
---|---|---|
A | 3 | 11110 |
B | 6 | 1110 |
C | 12 | 110 |
D | 9 | 001 |
E | 4 | 11111 |
F | 8 | 000 |
G | 21 | 01 |
H | 22 | 10 |
可以把權(quán)值不同的結(jié)點分別存儲在優(yōu)先隊列(Priority Queue)中,并且給與權(quán)重較低的結(jié)點較高的優(yōu)先級(Priority)。
具體實現(xiàn)哈夫曼樹算法如下:
1.把n
個結(jié)點存儲到優(yōu)先隊列中,則n
個節(jié)點都有一個優(yōu)先權(quán)Pi
。這里是權(quán)值越小,優(yōu)先權(quán)越高。
2.如果隊列內(nèi)的節(jié)點數(shù)>1
,則:
從隊列中移除兩個最小的結(jié)點。
產(chǎn)生一個新節(jié)點,此節(jié)點為隊列中移除節(jié)點的父節(jié)點,且此節(jié)點的權(quán)重值為兩節(jié)點之權(quán)值之和,把新結(jié)點加入隊列中。
重復(fù)上述過程,最后留在優(yōu)先隊列里的結(jié)點為哈夫曼樹的根節(jié)點(root
)。
完整代碼:
#include <iostream> #include <queue> #include <vector> using namespace std; //樹結(jié)點 struct TreeNode { //結(jié)點權(quán)值 float weight; //左結(jié)點 TreeNode *lelfChild; //右結(jié)點 TreeNode *rightChild; //初始化 TreeNode(float w) { weight=w; lelfChild=NULL; rightChild=NULL; } }; //為優(yōu)先隊列提供比較函數(shù) struct comp { bool operator() (TreeNode * a, TreeNode * b) { //由大到小排列 return a->weight > b->weight; } }; //哈夫曼樹類 class HfmTree { private: //優(yōu)先隊列容器 priority_queue<TreeNode *,vector<TreeNode *>,comp> hfmQueue; public: //構(gòu)造函數(shù),構(gòu)建單根結(jié)點樹 HfmTree(int weights[8]) { for(int i=0; i<8; i++) { //創(chuàng)建不同權(quán)值的單根樹 TreeNode *tn=new TreeNode(weights[i]); hfmQueue.push(tn); } } //顯示隊列中的最一個結(jié)點 TreeNode* showHfmRoot() { TreeNode *tn; while(!hfmQueue.empty()) { tn= hfmQueue.top(); hfmQueue.pop(); } return tn; } //構(gòu)建哈夫曼樹 void create() { //重復(fù)直到隊列中只有一個結(jié)點 while(hfmQueue.size()!=1) { //從優(yōu)先隊列中找到權(quán)值最小的 2 個單根樹 TreeNode *minFirst=hfmQueue.top(); hfmQueue.pop(); TreeNode *minSecond=hfmQueue.top(); hfmQueue.pop(); //創(chuàng)建新的二叉樹 TreeNode *newRoot=new TreeNode(minFirst->weight+minSecond->weight); newRoot->lelfChild=minFirst; newRoot->rightChild=minSecond; //新二叉樹放入隊列中 hfmQueue.push(newRoot); } } //按前序遍歷哈夫曼樹的所有結(jié)點 void showHfmTree(TreeNode *root) { if(root!=NULL) { cout<<root->weight<<endl; showHfmTree(root->lelfChild); showHfmTree(root->rightChild); } } //析構(gòu)函數(shù) ~HfmTree() { //省略 } }; //測試 int main(int argc, char** argv) { //不同權(quán)值的結(jié)點 int weights[8]= {3,6,12,9,4,8,21,22}; //調(diào)用構(gòu)造函數(shù) HfmTree hfmTree(weights); //創(chuàng)建哈夫曼樹 hfmTree.create(); //前序方式顯示哈夫曼樹 TreeNode *root= hfmTree.showHfmRoot(); hfmTree.showHfmTree(root); return 0; }
顯示結(jié)果:
上述輸出結(jié)果,和前文的演示結(jié)果是一樣的。
此算法的時間復(fù)雜度為O(nlogn)
。因為有n
個結(jié)點,所以樹總共有2n-1
個節(jié)點,使用優(yōu)先隊列每個循環(huán)須O(log n)
。
除了上文的使用優(yōu)先隊列之外,還可以使用一維數(shù)組的存儲方式實現(xiàn)。
在哈夫曼樹中,葉子結(jié)點有 n
個,非葉子結(jié)點有 n-1
個,使用數(shù)組保存哈夫曼樹上所的結(jié)點需要 2n-1
個存儲空間 。其算法思路和前文使用隊列的思路差不多。直接上代碼:
#include <iostream> using namespace std; //葉結(jié)點數(shù)量 const unsigned int n=8; //一維數(shù)組長度 const unsigned int m= 2*n -1; //樹結(jié)點 struct TreeNode { //權(quán)值 float weight; //父結(jié)點 int parent; //左結(jié)點 int leftChild; //右結(jié)點 int rightChild; }; class HuffmanTree { public: //創(chuàng)建一維數(shù)組 TreeNode hfmNodes[m+1]; public: //構(gòu)造函數(shù) HuffmanTree(int weights[8]); ~HuffmanTree( ) { } void findMinNode(int k, int &s1, int &s2); void showInfo() { for(int i=0; i<m; i++) { cout<<hfmNodes[i].weight<<endl; } } }; HuffmanTree::HuffmanTree(int weights[8]) { //前2 個權(quán)值最小的結(jié)點 int firstMin; int secondMin; //初始化數(shù)組中的結(jié)點 for(int i = 1; i <= m; i++) { hfmNodes[i].weight = 0; hfmNodes[i].parent = -1; hfmNodes[i].leftChild = -1; hfmNodes[i].rightChild = -1; } //前 n 個是葉結(jié)點 for(int i = 1; i <= n; i++) hfmNodes[i].weight=weights[i-1]; for(int i = n + 1; i <=m; i++) { this->findMinNode(i-1, firstMin, secondMin); hfmNodes[firstMin].parent = i; hfmNodes[secondMin].parent = i; hfmNodes[i].leftChild = firstMin; hfmNodes[i].rightChild = secondMin; hfmNodes[i].weight = hfmNodes[firstMin].weight + hfmNodes[secondMin].weight; } } void HuffmanTree::findMinNode(int k, int & firstMin, int & secondMin) { hfmNodes[0].weight = 32767; firstMin=secondMin=0; for(int i=1; i<=k; i++) { if(hfmNodes[i].weight!=0 && hfmNodes[i].parent==-1) { if(hfmNodes[i].weight < hfmNodes[firstMin].weight) { //如果有比第一小還要小的,則原來的第一小變成第二小 secondMin = firstMin; //新的第一小 firstMin = i; } else if(hfmNodes[i].weight < hfmNodes[secondMin].weight) //如果僅比第二小的小 secondMin = i; } } } int main() { int weights[8]= {3,6,12,9,4,8,21,22}; HuffmanTree huffmanTree(weights); huffmanTree.showInfo(); return 1; }
測試結(jié)果:
感謝各位的閱讀,以上就是“C++哈夫曼樹的原理是什么及怎么實現(xiàn)”的內(nèi)容了,經(jīng)過本文的學(xué)習(xí)后,相信大家對C++哈夫曼樹的原理是什么及怎么實現(xiàn)這一問題有了更深刻的體會,具體使用情況還需要大家實踐驗證。這里是億速云,小編將為大家推送更多相關(guān)知識點的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。