快捷導(dǎo)航

漫談C++哈夫曼樹(shù)的原理及實(shí)現(xiàn)

更新時(shí)間：2022年08月19日 16:47:37 作者：一枚大果殼

給定N個(gè)權(quán)值作為N個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹(shù)，若該樹(shù)的帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱(chēng)這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱(chēng)為哈夫曼樹(shù)(Huffman?Tree)。本文將通過(guò)圖片為大家詳細(xì)講講C++哈夫曼樹(shù)的原理及實(shí)現(xiàn)，需要的可以參考一下

1. 前言

什么是哈夫曼樹(shù)？

把權(quán)值不同的n個(gè)結(jié)點(diǎn)構(gòu)造成一棵二叉樹(shù)，如果此樹(shù)滿(mǎn)足以下幾個(gè)條件：

此 n 個(gè)結(jié)點(diǎn)為二叉樹(shù)的葉結(jié)點(diǎn) 。
權(quán)值較大的結(jié)點(diǎn)離根結(jié)點(diǎn)較近，權(quán)值較小的結(jié)點(diǎn)離根結(jié)點(diǎn)較遠(yuǎn)。
該樹(shù)的帶權(quán)路徑長(zhǎng)度是所有可能構(gòu)建的二叉樹(shù)中最小的。

則稱(chēng)符合上述條件的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱(chēng)為哈夫曼樹(shù)(Huffman Tree)。

構(gòu)建哈夫曼樹(shù)的目的是什么？

用來(lái)解決在通信系統(tǒng)中如何使用最少的二進(jìn)制位編碼字符信息。

本文將和大家聊聊哈夫曼樹(shù)的設(shè)計(jì)思想以及構(gòu)建過(guò)程。

2. 設(shè)計(jì)思路

哈夫曼樹(shù)產(chǎn)生的背景：

在通信系統(tǒng)中傳遞一串字符串文本時(shí)，需要對(duì)這一串字符串文本信息進(jìn)行二進(jìn)制編碼。編碼時(shí)如何保證所用到的bit位是最少的，或保證整個(gè)編碼后的傳輸長(zhǎng)度最短。

現(xiàn)假設(shè)字符串由ABCD 4個(gè)字符組成，最直接的想法是使用 2 個(gè)bit位進(jìn)行等長(zhǎng)編碼，如下表格所示：

字符	編碼
A	00
B	01
C	10
D	11

傳輸ABCD字符串一次時(shí)，所需bit為 2位，當(dāng)通信次數(shù)達(dá)到 n次時(shí)，則需要的總傳輸長(zhǎng)度為 n*2。當(dāng)字符串的傳輸次數(shù)為 1000次時(shí)，所需要傳輸?shù)目傞L(zhǎng)度為 2000個(gè)bit。

使用等長(zhǎng)編碼時(shí)，如果傳輸?shù)膱?bào)文中有 26 個(gè)不同字符時(shí)，因需要對(duì)每一個(gè)字符進(jìn)行編碼，至少需要 5位bit。

但在實(shí)際應(yīng)用中，各個(gè)字符的出現(xiàn)頻率或使用次數(shù)是不相同的，如A、B、C的使用頻率遠(yuǎn)遠(yuǎn)高于X、Y、Z。使用等長(zhǎng)編碼特點(diǎn)是無(wú)論字符出現(xiàn)的頻率差異有多大，每一個(gè)字符都得使用相同的bit位。

哈夫曼的設(shè)計(jì)思想：

對(duì)字符串信息進(jìn)行編碼設(shè)計(jì)時(shí)，讓使用頻率高的字符使用短碼，使用頻率低的用長(zhǎng)碼，以?xún)?yōu)化整個(gè)信息編碼的長(zhǎng)度。
基于這種簡(jiǎn)單、樸素的想法設(shè)計(jì)出來(lái)的編碼也稱(chēng)為不等長(zhǎng)編碼。

哈夫曼不等長(zhǎng)編碼的具體思路如下：

如現(xiàn)在要發(fā)送僅由A、B、C、D 4 個(gè)字符組成的報(bào)文信息，A字符在信息中占比為 50%，B的占比是 20%，C的占比是 15%， D的占比是10%。

不等長(zhǎng)編碼的樸實(shí)思想是字符的占比越大，所用的bit位就少，占比越小，所用bit位越多。如下為每一個(gè)字符使用的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

如此編碼后，是否真的比前面的等長(zhǎng)編碼所使用的總bit位要少？

計(jì)算結(jié)果=0.5*1+0.2*2+0.15*3+0.1*3=1.65。

先計(jì)算每一個(gè)字符在報(bào)文信息中的占比乘以字符所使用的bit位。

然后對(duì)上述每一個(gè)字符計(jì)算后的結(jié)果進(jìn)行相加。

顯然，編碼ABCD只需要 1.65 個(gè)bit ，比等長(zhǎng)編碼用到的2 個(gè) bit位要少。當(dāng)傳輸信息量為 1000時(shí)，總共所需要的bit位=1.65*1000=1650 bit。

哈夫曼編碼和哈夫曼樹(shù)有什么關(guān)系？

因?yàn)樽址木幋a是通過(guò)構(gòu)建一棵自下向上的二叉樹(shù)推導(dǎo)出來(lái)的，如下圖所示：

哈夫曼樹(shù)的特點(diǎn)：

信息結(jié)點(diǎn)都是葉子結(jié)點(diǎn)。
葉子結(jié)點(diǎn)具有權(quán)值。如上二叉樹(shù)，A結(jié)點(diǎn)權(quán)值為0.5，B結(jié)點(diǎn)權(quán)值為0.2，C結(jié)點(diǎn)權(quán)值為0.15，D結(jié)點(diǎn)權(quán)值為 0.1。
哈夫曼編碼為不等長(zhǎng)前綴編碼（即要求一個(gè)字符的編碼不能是另一個(gè)字符編碼的前綴）。
從根結(jié)點(diǎn)開(kāi)始，為左右分支分別編號(hào)0和1，然后順序連接從根結(jié)點(diǎn)到葉結(jié)點(diǎn)所有分支上的編號(hào)得到字符的編碼。

相信大家對(duì)哈夫曼樹(shù)有了一個(gè)大概了解，至于如何通過(guò)構(gòu)建哈夫曼樹(shù)，咱們繼續(xù)再聊。

3. 構(gòu)建思路

在構(gòu)建哈夫曼樹(shù)之前，先了解幾個(gè)相關(guān)概念：

路徑和路徑長(zhǎng)度：在一棵樹(shù)中，從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩子或?qū)O子結(jié)點(diǎn)之間的通路，稱(chēng)為路徑。通路中分支的數(shù)目稱(chēng)為路徑長(zhǎng)度。若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長(zhǎng)度為L-1。
結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長(zhǎng)度：若將樹(shù)中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值，則這個(gè)數(shù)值稱(chēng)為該結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積。
樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)的帶權(quán)路徑長(zhǎng)度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記為WPL。

如有權(quán)值為{3,4,9,15}的 4 個(gè)結(jié)點(diǎn)，則可構(gòu)造出不同的二叉樹(shù)，其帶權(quán)路徑長(zhǎng)度也會(huì)不同。如下 3 種二叉樹(shù)中，B的樹(shù)帶權(quán)路徑長(zhǎng)度是最小的。

哈夫曼樹(shù)的構(gòu)建過(guò)程就是要保證樹(shù)的帶權(quán)路徑長(zhǎng)度最小。

那么，如何構(gòu)建二叉樹(shù)，才能保證構(gòu)建出來(lái)的二叉樹(shù)的帶權(quán)路徑長(zhǎng)度最??？

如有一字符串信息由 ABCDEFGH 8個(gè)字符組成，每一個(gè)字符的權(quán)值分別為{3,6,12,9,4,8,21,22}，構(gòu)建最優(yōu)哈夫曼樹(shù)的流程：

1.以每一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)構(gòu)建一個(gè)單根二叉樹(shù)，二叉樹(shù)的左右子結(jié)點(diǎn)為空，根結(jié)點(diǎn)的權(quán)值為每個(gè)結(jié)點(diǎn)的權(quán)值。并存儲(chǔ)到一個(gè)樹(shù)集合中。

2.從樹(shù)集合中選擇根結(jié)點(diǎn)的權(quán)值最小的 2 個(gè)樹(shù)。重新構(gòu)建一棵新二叉樹(shù)，讓剛選擇出來(lái)的2 棵樹(shù)的根結(jié)點(diǎn)成為這棵新樹(shù)的左右子結(jié)點(diǎn)，新樹(shù)的根結(jié)點(diǎn)的權(quán)值為 2 個(gè)左右子結(jié)點(diǎn)權(quán)值的和。構(gòu)建完成后從樹(shù)集合中刪除原來(lái) 2個(gè)結(jié)點(diǎn)，并把新二叉樹(shù)放入樹(shù)集合中。

如下圖所示。權(quán)值為 3和4的結(jié)點(diǎn)為新二叉樹(shù)的左右子結(jié)點(diǎn)，新樹(shù)根結(jié)點(diǎn)的權(quán)值為7。

3.重復(fù)第二步，直到樹(shù)集合中只有一個(gè)根結(jié)點(diǎn)為止。

當(dāng)集合中只存在一個(gè)根結(jié)點(diǎn)時(shí)，停止構(gòu)建，并且為最后生成樹(shù)的每一個(gè)非葉子結(jié)點(diǎn)的左結(jié)點(diǎn)分支標(biāo)注0，右結(jié)點(diǎn)分支標(biāo)注1。如下圖所示：

通過(guò)上述從下向上的思想構(gòu)建出來(lái)的二叉樹(shù)，可以保證權(quán)值較小的結(jié)點(diǎn)離根結(jié)點(diǎn)較遠(yuǎn)，權(quán)值較大的結(jié)點(diǎn)離根結(jié)點(diǎn)較近。最終二叉樹(shù)的帶權(quán)路徑長(zhǎng)度： WPL=(3+4)*5+6*4+(8+9+12)*3+(21+22)*2=232 。并且此樹(shù)的帶權(quán)路徑長(zhǎng)度是所有可能構(gòu)建出來(lái)的二叉樹(shù)中最小的。

上述的構(gòu)建思想即為哈夫曼樹(shù)設(shè)計(jì)思想，不同權(quán)值的字符編碼就是結(jié)點(diǎn)路徑上0和1的順序組合。如下表所述，權(quán)值越大，其編碼越小，權(quán)值越小，其編碼越大。其編碼長(zhǎng)度即從根結(jié)點(diǎn)到此葉結(jié)點(diǎn)的路徑長(zhǎng)度。

字符	權(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

4. 編碼實(shí)現(xiàn)

4.1 使用優(yōu)先隊(duì)列

可以把權(quán)值不同的結(jié)點(diǎn)分別存儲(chǔ)在優(yōu)先隊(duì)列（Priority Queue）中，并且給與權(quán)重較低的結(jié)點(diǎn)較高的優(yōu)先級(jí)（Priority）。

具體實(shí)現(xiàn)哈夫曼樹(shù)算法如下：

1.把n個(gè)結(jié)點(diǎn)存儲(chǔ)到優(yōu)先隊(duì)列中，則n個(gè)節(jié)點(diǎn)都有一個(gè)優(yōu)先權(quán)Pi。這里是權(quán)值越小，優(yōu)先權(quán)越高。

2.如果隊(duì)列內(nèi)的節(jié)點(diǎn)數(shù)>1，則：

從隊(duì)列中移除兩個(gè)最小的結(jié)點(diǎn)。
產(chǎn)生一個(gè)新節(jié)點(diǎn)，此節(jié)點(diǎn)為隊(duì)列中移除節(jié)點(diǎn)的父節(jié)點(diǎn)，且此節(jié)點(diǎn)的權(quán)重值為兩節(jié)點(diǎn)之權(quán)值之和，把新結(jié)點(diǎn)加入隊(duì)列中。
重復(fù)上述過(guò)程，最后留在優(yōu)先隊(duì)列里的結(jié)點(diǎn)為哈夫曼樹(shù)的根節(jié)點(diǎn)（root）。

完整代碼：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
//樹(shù)結(jié)點(diǎn)
struct TreeNode {
	//結(jié)點(diǎn)權(quán)值
	float weight;
	//左結(jié)點(diǎn)
	TreeNode *lelfChild;
	//右結(jié)點(diǎn)
	TreeNode *rightChild;
    //初始化
	TreeNode(float w) {
		weight=w;
		lelfChild=NULL;
		rightChild=NULL;
    }
};
//為優(yōu)先隊(duì)列提供比較函數(shù)
struct comp {
	bool operator() (TreeNode * a, TreeNode * b) {
        //由大到小排列
		return a->weight > b->weight; 
	}
};

//哈夫曼樹(shù)類(lèi)
class HfmTree {
	private:
         //優(yōu)先隊(duì)列容器
		priority_queue<TreeNode *,vector<TreeNode *>,comp> hfmQueue;
	public:
		//構(gòu)造函數(shù)，構(gòu)建單根結(jié)點(diǎn)樹(shù)
		HfmTree(int weights[8]) {
			for(int i=0; i<8; i++) {
				//創(chuàng)建不同權(quán)值的單根樹(shù)
				TreeNode *tn=new TreeNode(weights[i]);
				hfmQueue.push(tn);
			}
		}
		//顯示隊(duì)列中的最一個(gè)結(jié)點(diǎn)
		TreeNode* showHfmRoot() {
			TreeNode *tn;
			while(!hfmQueue.empty()) {
				tn= hfmQueue.top();
				hfmQueue.pop();
			}
			return tn;
		}
		//構(gòu)建哈夫曼樹(shù)
		void create() {
             //重復(fù)直到隊(duì)列中只有一個(gè)結(jié)點(diǎn)
			while(hfmQueue.size()!=1) {
				//從優(yōu)先隊(duì)列中找到權(quán)值最小的 2 個(gè)單根樹(shù)
				TreeNode *minFirst=hfmQueue.top();
				hfmQueue.pop();
				TreeNode *minSecond=hfmQueue.top();
				hfmQueue.pop();
				//創(chuàng)建新的二叉樹(shù)
				TreeNode *newRoot=new TreeNode(minFirst->weight+minSecond->weight);
				newRoot->lelfChild=minFirst;
				newRoot->rightChild=minSecond;
				//新二叉樹(shù)放入隊(duì)列中
				hfmQueue.push(newRoot);
			}
		}
		//按前序遍歷哈夫曼樹(shù)的所有結(jié)點(diǎn)
		void showHfmTree(TreeNode *root) {
			if(root!=NULL) {
				cout<<root->weight<<endl;
				showHfmTree(root->lelfChild);
				showHfmTree(root->rightChild);
			}
		}
		//析構(gòu)函數(shù)
		~HfmTree() {
            //省略
		}
};

//測(cè)試
int main(int argc, char** argv) {
	//不同權(quán)值的結(jié)點(diǎn)
	int weights[8]= {3,6,12,9,4,8,21,22};
    //調(diào)用構(gòu)造函數(shù)
	HfmTree hfmTree(weights);
    //創(chuàng)建哈夫曼樹(shù)
	hfmTree.create();
    //前序方式顯示哈夫曼樹(shù)
	TreeNode *root= hfmTree.showHfmRoot();
	hfmTree.showHfmTree(root);
	return 0;
}

顯示結(jié)果：

上述輸出結(jié)果，和前文的演示結(jié)果是一樣的。

此算法的時(shí)間復(fù)雜度為O（nlogn）。因?yàn)橛?code>n個(gè)結(jié)點(diǎn)，所以樹(shù)總共有2n-1個(gè)節(jié)點(diǎn)，使用優(yōu)先隊(duì)列每個(gè)循環(huán)須O（log n）。

4.2 使用一維數(shù)組

除了上文的使用優(yōu)先隊(duì)列之外，還可以使用一維數(shù)組的存儲(chǔ)方式實(shí)現(xiàn)。

在哈夫曼樹(shù)中，葉子結(jié)點(diǎn)有 n個(gè)，非葉子結(jié)點(diǎn)有 n-1個(gè)，使用數(shù)組保存哈夫曼樹(shù)上所的結(jié)點(diǎn)需要 2n-1個(gè)存儲(chǔ)空間。其算法思路和前文使用隊(duì)列的思路差不多。直接上代碼：

#include <iostream>
using namespace std;
//葉結(jié)點(diǎn)數(shù)量
const unsigned int n=8;
//一維數(shù)組長(zhǎng)度
const unsigned int m= 2*n -1;
//樹(shù)結(jié)點(diǎn)
struct TreeNode {
	//權(quán)值
	float weight;
	//父結(jié)點(diǎn)
	int parent;
	//左結(jié)點(diǎn)
	int leftChild;
	//右結(jié)點(diǎn)
	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 個(gè)權(quán)值最小的結(jié)點(diǎn)
	int firstMin;
	int  secondMin;
	//初始化數(shù)組中的結(jié)點(diǎn)
	for(int i = 1; i <= m; i++) {
		hfmNodes[i].weight = 0;
		hfmNodes[i].parent = -1;
		hfmNodes[i].leftChild = -1;
		hfmNodes[i].rightChild = -1;
	}
	//前 n 個(gè)是葉結(jié)點(diǎn)
	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) { 
                  //如果有比第一小還要小的，則原來(lái)的第一小變成第二小
				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;
}

測(cè)試結(jié)果：