哈夫曼樹的介紹
Huffman Tree,中文名是哈夫曼樹或霍夫曼樹,它是最優(yōu)二叉樹。
定義:給定n個(gè)權(quán)值作為n個(gè)葉子結(jié)點(diǎn),構(gòu)造一棵二叉樹,若樹的帶權(quán)路徑長度達(dá)到最小,則這棵樹被稱為哈夫曼樹。 這個(gè)定義里面涉及到了幾個(gè)陌生的概念,下面就是一顆哈夫曼樹,我們來看圖解答。
?。?) 路徑和路徑長度
定義:在一棵樹中,從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩子或?qū)O子結(jié)點(diǎn)之間的通路,稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點(diǎn)的層數(shù)為1,則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長度為L-1。
例子:100和80的路徑長度是1,50和30的路徑長度是2,20和10的路徑長度是3。
?。?) 結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長度
定義:若將樹中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值,則這個(gè)數(shù)值稱為該結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長度為:從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長度與該結(jié)點(diǎn)的權(quán)的乘積。
例子:節(jié)點(diǎn)20的路徑長度是3,它的帶權(quán)路徑長度= 路徑長度 * 權(quán) = 3 * 20 = 60。
?。?) 樹的帶權(quán)路徑長度
定義:樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和,記為WPL。
例子:示例中,樹的WPL= 1*100 + 2*50 + 3*20 + 3*10 = 100 + 100 + 60 + 30 = 290。
比較下面兩棵樹
上面的兩棵樹都是以{10, 20, 50, 100}為葉子節(jié)點(diǎn)的樹。
左邊的樹WPL=2*10 + 2*20 + 2*50 + 2*100 = 360
右邊的樹WPL=290
左邊的樹WPL 》 右邊的樹的WPL。你也可以計(jì)算除上面兩種示例之外的情況,但實(shí)際上右邊的樹就是{10,20,50,100}對應(yīng)的哈夫曼樹。至此,應(yīng)該對哈夫曼樹的概念有了一定的了解了,下面看看如何去構(gòu)造一棵哈夫曼樹。
哈夫曼樹的圖文解析
假設(shè)有n個(gè)權(quán)值,則構(gòu)造出的哈夫曼樹有n個(gè)葉子結(jié)點(diǎn)。 n個(gè)權(quán)值分別設(shè)為 w1、w2、…、wn,哈夫曼樹的構(gòu)造規(guī)則為:
1. 將w1、w2、…,wn看成是有n 棵樹的森林(每棵樹僅有一個(gè)結(jié)點(diǎn));
2. 在森林中選出根結(jié)點(diǎn)的權(quán)值最小的兩棵樹進(jìn)行合并,作為一棵新樹的左、右子樹,且新樹的根結(jié)點(diǎn)權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和;
3. 從森林中刪除選取的兩棵樹,并將新樹加入森林;
4. 重復(fù)(02)、(03)步,直到森林中只剩一棵樹為止,該樹即為所求得的哈夫曼樹。
以{5,6,7,8,15}為例,來構(gòu)造一棵哈夫曼樹。
第1步:創(chuàng)建森林,森林包括5棵樹,這5棵樹的權(quán)值分別是5,6,7,8,15。
第2步:在森林中,選擇根節(jié)點(diǎn)權(quán)值最小的兩棵樹(5和6)來進(jìn)行合并,將它們作為一顆新樹的左右孩子(誰左誰右無關(guān)緊要,這里,我們選擇較小的作為左孩子),并且新樹的權(quán)值是左右孩子的權(quán)值之和。即,新樹的權(quán)值是11。 然后,將“樹5”和“樹6”從森林中刪除,并將新的樹(樹11)添加到森林中。
第3步:在森林中,選擇根節(jié)點(diǎn)權(quán)值最小的兩棵樹(7和8)來進(jìn)行合并。得到的新樹的權(quán)值是15。 然后,將“樹7”和“樹8”從森林中刪除,并將新的樹(樹15)添加到森林中。
第4步:在森林中,選擇根節(jié)點(diǎn)權(quán)值最小的兩棵樹(11和15)來進(jìn)行合并。得到的新樹的權(quán)值是26。 然后,將“樹11”和“樹15”從森林中刪除,并將新的樹(樹26)添加到森林中。
第5步:在森林中,選擇根節(jié)點(diǎn)權(quán)值最小的兩棵樹(15和26)來進(jìn)行合并。得到的新樹的權(quán)值是41。 然后,將“樹15”和“樹26”從森林中刪除,并將新的樹(樹41)添加到森林中。
此時(shí),森林中只有一棵樹(樹41)。這棵樹就是我們需要的哈夫曼樹!
哈夫曼樹是一種樹形結(jié)構(gòu),用哈夫曼樹的方法解編程題的算法就叫做哈夫曼算法。樹并不是指植物,而是一種數(shù)據(jù)結(jié)構(gòu),因?yàn)槠浯娣欧绞筋H有點(diǎn)象一棵樹有樹叉因而稱為樹。 最簡哈夫曼樹是由德國數(shù)學(xué)家馮。哈夫曼 發(fā)現(xiàn)的,此樹的特點(diǎn)就是引出的路程最短。
哈夫曼算法
哈夫曼樹是一種樹形結(jié)構(gòu),用哈夫曼樹的方法解編程題的算法就叫做哈夫曼算法。樹并不是指植物,而是一種數(shù)據(jù)結(jié)構(gòu)。
定義:它是由n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹中帶權(quán)路徑長度最短的二叉樹。因?yàn)檫@種樹最早由哈夫曼(Huffman)研究,所以稱為哈夫曼樹,又叫最優(yōu)二叉樹。
構(gòu)造哈夫曼樹
?。踙tml] view plain copy/*
* 創(chuàng)建Huffman樹
*
* @param 權(quán)值數(shù)組
*/
public Huffman(int a[]) {
HuffmanNode parent = null;
MinHeap heap;
// 建立數(shù)組a對應(yīng)的最小堆
heap = new MinHeap(a);
for(int i=0; i《a.length-1; i++) {
HuffmanNode left = heap.dumpFromMinimum(); // 最小節(jié)點(diǎn)是左孩子
HuffmanNode right = heap.dumpFromMinimum(); // 其次才是右孩子
// 新建parent節(jié)點(diǎn),左右孩子分別是left/right;
// parent的大小是左右孩子之和
parent = new HuffmanNode(left.key+right.key, left, right, null);
left.parent = parent;
right.parent = parent;
// 將parent節(jié)點(diǎn)數(shù)據(jù)拷貝到“最小堆”中
heap.insert(parent);
}
mRoot = parent;
// 銷毀最小堆
heap.destroy();
}
首先創(chuàng)建最小堆,然后進(jìn)入for循環(huán)。
每次循環(huán)時(shí):
?。?) 首先,將最小堆中的最小節(jié)點(diǎn)拷貝一份并賦值給left,然后重塑最小堆(將最小節(jié)點(diǎn)和后面的節(jié)點(diǎn)交換位置,接著將“交換位置后的最小節(jié)點(diǎn)”之前的全部元素重新構(gòu)造成最小堆);
(2) 接著,再將最小堆中的最小節(jié)點(diǎn)拷貝一份并將其賦值right,然后再次重塑最小堆;
?。?) 然后,新建節(jié)點(diǎn)parent,并將它作為left和right的父節(jié)點(diǎn);
(4) 接著,將parent的數(shù)據(jù)復(fù)制給最小堆中的指定節(jié)點(diǎn)。
哈夫曼算法原理
1952年, David A. Huffman提出了一個(gè)不同的算法,這個(gè)算法可以為任何的可能性提供出一個(gè)理想的樹。香農(nóng)-范諾編碼(Shanno-Fano)是從樹的根節(jié)點(diǎn)到葉子節(jié)點(diǎn)所進(jìn)行的的編碼,哈夫曼編碼算法卻是從相反的方向,暨從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的方向編碼的。
1.為每個(gè)符號建立一個(gè)葉子節(jié)點(diǎn),并加上其相應(yīng)的發(fā)生頻率
2.當(dāng)有一個(gè)以上的節(jié)點(diǎn)存在時(shí),進(jìn)行下列循環(huán):
1)把這些節(jié)點(diǎn)作為帶權(quán)值的二叉樹的根節(jié)點(diǎn),左右子樹為空
2)選擇兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹,且至新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹上根結(jié)點(diǎn)的權(quán)值之和。
3)把權(quán)值最小的兩個(gè)根節(jié)點(diǎn)移除
4)將新的二叉樹加入隊(duì)列中。
5)最后剩下的節(jié)點(diǎn)暨為根節(jié)點(diǎn),此時(shí)二叉樹已經(jīng)完成。
哈夫曼樹的應(yīng)用
哈夫曼編碼:
哈夫曼樹可以直接應(yīng)用于通信及數(shù)據(jù)傳送中的二進(jìn)制編碼。設(shè): D={d1,d2,d3…dn}為需要編碼的字符集合。
W={w1,w2,w3,…wn}為D中各字符出現(xiàn)的頻率。 現(xiàn)要對D中的字符進(jìn)行二進(jìn)制編碼,使得:
?。?) 按給出的編碼傳輸文件時(shí),通信編碼的總長最短。
?。?) 若di不等于dj,則di的編碼不可能是dj的編碼的開始部分(前綴)。
滿足上述要求的二進(jìn)制編碼稱為最優(yōu)前綴編碼。 上述要求的第一條是為了提高傳輸?shù)乃俣龋诙l是為了保證傳輸?shù)?a target="_blank">信息在譯碼時(shí)無二性,所以在字符的編碼中間不需要添加任意的分割符。
對于這個(gè)問題,可以利用哈夫曼樹加以解決:用d1,d2,d3…dn作為外部結(jié)點(diǎn),用w1,w2,w3…wn作為外部結(jié)點(diǎn)的權(quán),構(gòu)造哈夫曼樹。在哈夫曼樹中把從每個(gè)結(jié)點(diǎn)引向其左子結(jié)點(diǎn)的邊標(biāo)上二進(jìn)制數(shù)“0”,把從每個(gè)結(jié)點(diǎn)引向右子節(jié)點(diǎn)的邊標(biāo)上二進(jìn)制數(shù)“1”,從根到每個(gè)葉結(jié)點(diǎn)的路徑上的二進(jìn)制數(shù)連接起來,就是這個(gè)葉結(jié)點(diǎn)所代表字符的最優(yōu)前綴編碼。通常把這種編碼稱為哈夫曼編碼。例如:
D={d1,d2,d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13} W={2,3,5,7,11,13,17,19,23,29,31,37,41} 利用哈夫曼算法構(gòu)造出如下圖所示的哈夫曼樹:
從而得到各字符的編碼為:
d1:1011110 d2:1011111
d3:101110 d4:10110
d5:0100 d6:0101
d7:1010 d8:000
d9:001 d10:011
d11:100 d12:110
d13:111
編碼的結(jié)果是,出現(xiàn)頻率大的字符其編碼較短,出現(xiàn)頻率較小的字符其編碼較長。
哈夫曼算法實(shí)現(xiàn)
實(shí)現(xiàn)的時(shí)候我們用vector《bool》記錄每個(gè)char的編碼;用map《char,vector《bool》》表示整個(gè)字典;
就得到了下面的代碼(下面有兩個(gè),一對一錯(cuò)):
先放出來這個(gè)錯(cuò)的,以示警戒:
[cpp] view plain copy/************************************************************************/
/* File Name: Huffman.cpp
* @Function: Lossless Compression
@Author: Sophia Zhang
@Create Time: 2012-9-26 10:40
@Last Modify: 2012-9-26 11:10
*/
/************************************************************************/
#include“iostream”
#include “queue”
#include “map”
#include “string”
#include “iterator”
#include “vector”
#include “algorithm”
using namespace std;
#define NChar 8 //suppose use at most 8 bits to describe all symbols
#define Nsymbols 1《《NChar //can describe 256 symbols totally (include a-z, A-Z)
typedef vector《bool》 Huff_code;//8 bit code of one char
map《char,Huff_code》 Huff_Dic; //huffman coding dictionary
class HTree
{
public :
HTree* left;
HTree* right;
char ch;
int weight;
HTree(){left = right = NULL; weight=0;}
HTree(HTree* l,HTree* r,int w,char c){left = l; right = r; weight=w; ch=c;}
~HTree(){delete left; delete right;}
int Getweight(){return weight?weight:left-》weight+right-》weight;}
bool Isleaf(){return !left && !right; }
bool operator 《 (const HTree tr) const
{
return tr.weight 《 weight;
}
};
HTree* BuildTree(int *frequency)
{
priority_queue《HTree*》 QTree;
for (int i=0;i《Nsymbols;i++)
{
if(frequency[i])
QTree.push(new HTree(NULL,NULL,frequency[i],(char)i));
}
//build
while (QTree.size()》1)
{
HTree* lc = QTree.top();
QTree.pop();
HTree* rc = QTree.top();
QTree.pop();
HTree* parent = new HTree(lc,rc,parent-》Getweight(),(char)256);
QTree.push(parent);
}
//return tree root
return QTree.top();
}
void Huffman_Coding(HTree* root, Huff_code& curcode)
{
if(root-》Isleaf())
{
Huff_Dic[root-》ch] = curcode;
return;
}
Huff_code& lcode = curcode;
Huff_code& rcode = curcode;
lcode.push_back(false);
rcode.push_back(true);
Huffman_Coding(root-》left,lcode);
Huffman_Coding(root-》right,rcode);
}
int main()
{
int freq[Nsymbols] = {0};
char *str = “this is the string need to be compressed”;
//statistic character frequency
while (*str!=‘\0’)
freq[*str++]++;
//build tree
HTree* r = BuildTree(freq);
Huff_code nullcode;
nullcode.clear();
Huffman_Coding(r,nullcode);
for(map《char,Huff_code》::iterator it = Huff_Dic.begin(); it != Huff_Dic.end(); it++)
{
cout《《(*it).first《《‘\t’;
Huff_code vec_code = (*it).second;
for (vector《bool》::iterator vit = vec_code.begin(); vit!=vec_code.end();vit++)
{
cout《《(*vit)《《endl;
}
}
}
上面這段代碼,我運(yùn)行出來不對。在調(diào)試的時(shí)候發(fā)現(xiàn)了一個(gè)問題,就是QTree優(yōu)先隊(duì)列中的排序出了問題,說來也是,上面的代碼中,我重載小于號是對HTree object做的;而實(shí)際上我建樹時(shí)用的是指針,那么優(yōu)先級隊(duì)列中元素為指針時(shí)該怎么辦呢?
那我們將friend bool operator 》(Node node1,Node node2)修改為friend bool operator 》(Node* node1,Node* node2),也就是傳遞的是Node的指針行不行呢?
答案是不可以,因?yàn)楦鶕?jù)c++primer中重載操作符中講的“程序員只能為類類型或枚舉類型的操作數(shù)定義重載操作符,在把操作符聲明為類的成員時(shí),至少有一個(gè)類或枚舉類型的參數(shù)按照值或者引用的方式傳遞”,也就是說friend bool operator 》(Node* node1,Node* node2)形參中都是指針類型的是不可以的。我們只能再建一個(gè)類,用其中的重載()操作符作為優(yōu)先隊(duì)列的比較函數(shù)。
就得到了下面正確的代碼:
?。踓pp] view plain copy/************************************************************************/
/* File Name: Huffman.cpp
* @Function: Lossless Compression
@Author: Sophia Zhang
@Create Time: 2012-9-26 10:40
@Last Modify: 2012-9-26 12:10
*/
/************************************************************************/
#include“iostream”
#include “queue”
#include “map”
#include “string”
#include “iterator”
#include “vector”
#include “algorithm”
using namespace std;
#define NChar 8 //suppose use 8 bits to describe all symbols
#define Nsymbols 1《《NChar //can describe 256 symbols totally (include a-z, A-Z)
typedef vector《bool》 Huff_code;//8 bit code of one char
map《char,Huff_code》 Huff_Dic; //huffman coding dictionary
/************************************************************************/
/* Tree Class elements:
*2 child trees
*character and frequency of current node
*/
/************************************************************************/
class HTree
{
public :
HTree* left;
HTree* right;
char ch;
int weight;
HTree(){left = right = NULL; weight=0;ch =‘\0’;}
HTree(HTree* l,HTree* r,int w,char c){left = l; right = r; weight=w; ch=c;}
~HTree(){delete left; delete right;}
bool Isleaf(){return !left && !right; }
};
/************************************************************************/
/* prepare for pointer sorting*/
/*because we cannot use overloading in class HTree directly*/
/************************************************************************/
class Compare_tree
{
public:
bool operator () (HTree* t1, HTree* t2)
{
return t1-》weight》 t2-》weight;
}
};
/************************************************************************/
/* use priority queue to build huffman tree*/
/************************************************************************/
HTree* BuildTree(int *frequency)
{
priority_queue《HTree*,vector《HTree*》,Compare_tree》 QTree;
//1st level add characters
for (int i=0;i《Nsymbols;i++)
{
if(frequency[i])
QTree.push(new HTree(NULL,NULL,frequency[i],(char)i));
}
//build
while (QTree.size()》1)
{
HTree* lc = QTree.top();
QTree.pop();
HTree* rc = QTree.top();
QTree.pop();
HTree* parent = new HTree(lc,rc,lc-》weight+rc-》weight,(char)256);
QTree.push(parent);
}
//return tree root
return QTree.top();
}
/************************************************************************/
/* Give Huffman Coding to the Huffman Tree*/
/************************************************************************/
void Huffman_Coding(HTree* root, Huff_code& curcode)
{
if(root-》Isleaf())
{
Huff_Dic[root-》ch] = curcode;
return;
}
Huff_code lcode = curcode;
Huff_code rcode = curcode;
lcode.push_back(false);
rcode.push_back(true);
Huffman_Coding(root-》left,lcode);
Huffman_Coding(root-》right,rcode);
}
int main()
{
int freq[Nsymbols] = {0};
char *str = “this is the string need to be compressed”;
//statistic character frequency
while (*str!=‘\0’)
freq[*str++]++;
//build tree
HTree* r = BuildTree(freq);
Huff_code nullcode;
nullcode.clear();
Huffman_Coding(r,nullcode);
for(map《char,Huff_code》::iterator it = Huff_Dic.begin(); it != Huff_Dic.end(); it++)
{
cout《《(*it).first《《‘\t’;
std::copy(it-》second.begin(),it-》second.end(),std::ostream_iterator《bool》(cout));
cout《《endl;
}
}
評論
查看更多