哈夫曼樹(shù)定義為：給定n個(gè)權(quán)值作為n個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹(shù)，若帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱(chēng)這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱(chēng)為哈夫曼樹(shù)(Huffman tree)。
1、那么什么是權(quán)值？什么是路徑長(zhǎng)度？什么是帶權(quán)路徑長(zhǎng)度呢？
權(quán)值：哈夫曼樹(shù)的權(quán)值是自己定義的，他的物理意義表示數(shù)據(jù)出現(xiàn)的次數(shù)、頻率。可以用樹(shù)的每個(gè)結(jié)點(diǎn)數(shù)據(jù)域data存放一個(gè)特定的數(shù)表示它的值。
路徑長(zhǎng)度：在一棵樹(shù)中，從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩子或子孫結(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(zhǎng)-1。
結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積。 樹(shù)中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，WPL=sigma(w*l)
2、哈夫曼樹(shù)的構(gòu)造過(guò)程。（結(jié)合圖例）
假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹(shù)有n個(gè)葉子結(jié)點(diǎn)。 n個(gè)權(quán)值分別設(shè)為 w1、w2、…、wn，則哈夫曼樹(shù)的構(gòu)造規(guī)則為：
(1) 將w1、w2、…，wn看成是有n 棵樹(shù)的森林(每棵樹(shù)僅有一個(gè)結(jié)點(diǎn))；
(2) 在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹(shù)合并，作為一棵新樹(shù)的左、右子樹(shù)，且新樹(shù)的根結(jié)點(diǎn)權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和；
(3)從森林中刪除選取的兩棵樹(shù)，并將新樹(shù)加入森林；
(4)重復(fù)(2)、(3)步，直到森林中只剩一棵樹(shù)為止，該樹(shù)即為所求得的哈夫曼樹(shù)
3、哈夫曼樹(shù)的應(yīng)用：哈夫曼編碼（前綴編碼）
哈夫曼編碼
在數(shù)據(jù)通信中，通常需要把要傳送的文字轉(zhuǎn)換為由二進(jìn)制字符0和1組成的二進(jìn)制串，這個(gè)過(guò)程被稱(chēng)之為編碼(Encoding)。例如，假設(shè)要傳送的電文為DCBBADD，電文中只有A、B、C、D四種字符，若這四個(gè)字符采用表(a)所示的編碼方案，則電文的代碼為11100101001111，代碼總長(zhǎng)度為14。若采用表(b) 所示的編碼方案，則電文的代碼為0110101011100，代碼總長(zhǎng)度為13。
字符集的不同編碼方案
哈夫曼樹(shù)可用于構(gòu)造總長(zhǎng)度最短的編碼方案。具體構(gòu)造方法如下：
設(shè)需要編碼的字符集為{d1,d2,…,dn}，各個(gè)字符在電文中出現(xiàn)的次數(shù)或頻率集合為{w1,w2,…,wn}。以d1,d2,…,dn作為葉子結(jié)點(diǎn)，以w1,w2,…,wn作為相應(yīng)葉子結(jié)點(diǎn)的權(quán)值來(lái)構(gòu)造一棵哈夫曼樹(shù)。規(guī)定哈夫曼樹(shù)中的左分支代表0，右分支代表1，則從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)所經(jīng)過(guò)的路徑分支組成的0和1的序列便為該結(jié)點(diǎn)對(duì)應(yīng)字符的編碼就是哈夫曼編碼(Huffman Encoding)。
在建立不等長(zhǎng)編碼中，必須使任何一個(gè)字符的編碼都不是另一個(gè)編碼的前綴，這樣才能保證譯碼的唯一性。例如，若字符A的編碼是00，字符B的編碼是001，那么字符A的編碼就成了字符B的編碼的后綴。這樣，對(duì)于代碼串001001，在譯碼時(shí)就無(wú)法判定是將前兩位碼00譯成字符A還是將前三位碼001譯成B。這樣的編碼被稱(chēng)之為具有二義性的編碼，二義性編碼是不唯一的。而在哈夫曼樹(shù)中，每個(gè)字符結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，它們不可能在根結(jié)點(diǎn)到其它字符結(jié)點(diǎn)的路徑上，所以一個(gè)字符的哈夫曼編碼不可能是另一個(gè)字符的哈夫曼編碼的前綴，從而保證了譯碼的非二義性。
下圖就是電文DCBBADD的哈夫曼樹(shù)：
4、哈夫曼樹(shù)的實(shí)現(xiàn)
由哈夫曼樹(shù)的構(gòu)造算法可知，用一個(gè)數(shù)組存放原來(lái)的n個(gè)葉子結(jié)點(diǎn)和構(gòu)造過(guò)程中臨時(shí)生成的結(jié)點(diǎn)，數(shù)組的大小為2n-1。所以，哈夫曼樹(shù)類(lèi)HuffmanTree中有兩個(gè)成員字段：data數(shù)組用于存放結(jié)點(diǎn)，leafNum表示哈夫曼樹(shù)葉子結(jié)點(diǎn)的數(shù)目。結(jié)點(diǎn)有四個(gè)域，一個(gè)域weight，用于存放該結(jié)點(diǎn)的權(quán)值；一個(gè)域lChild，用于存放該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)在數(shù)組中的序號(hào)；一個(gè)域rChild，用于存放該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)在數(shù)組中的序號(hào)；一個(gè)域parent，用于判定該結(jié)點(diǎn)是否已加入哈夫曼樹(shù)中。
哈夫曼樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)為：| 數(shù)據(jù) | weight | lChild | rChild | parent |
public class Node
{
char c; //存儲(chǔ)的數(shù)據(jù)，為一個(gè)字符
private double weight; //結(jié)點(diǎn)權(quán)值
private int lChild; //左孩子結(jié)點(diǎn)
private int rChild; //右孩子結(jié)點(diǎn)
private int parent; //父結(jié)點(diǎn)
//結(jié)點(diǎn)權(quán)值屬性
public double Weight
{
get
{
return weight;
}
set
{
weight = value;
}
}
//左孩子結(jié)點(diǎn)屬性
public int LChild
{
get
{
return lChild;
}
set
{
lChild = value;
}
}
//右孩子結(jié)點(diǎn)屬性
public int RChild
{
get
{
return rChild;
}
set
{
rChild = value;
}
}
//父結(jié)點(diǎn)屬性
public int Parent
{
get
{
return parent;
}
set
{
parent = value;
}
}
//構(gòu)造器
public Node()
{
weight = 0;
lChild = -1;
rChild = -1;
parent = -1;
}
//構(gòu)造器
public Node(double weitht)
{
this.weight = weitht;
lChild = -1;
rChild = -1;
parent = -1;
}
//構(gòu)造器
public Node(int w, int lc, int rc, int p)
{
weight = w;
lChild = lc;
rChild = rc;
parent = p;
}
}
public class HuffmanTree
{
private Node[] data; //結(jié)點(diǎn)數(shù)組
private int leafNum; //葉子結(jié)點(diǎn)數(shù)目
//索引器
public Node this[int index]
{
get
{
return data[index];
}
set
{
data[index] = value;
}
}
//葉子結(jié)點(diǎn)數(shù)目屬性
public int LeafNum
{
get
{
return leafNum;
}
set
{
leafNum = value;
}
}
//構(gòu)造器
public HuffmanTree(int n)
{
data = new Node[2 * n - 1];
leafNum = n;
}
//創(chuàng)建哈夫曼樹(shù)
public void Create(Node[] datain)
{
double minL, minR;
minL = minR = double.MaxValue;
int lchild, rchild;
lchild = rchild = -1;
int length = data.Length;
//初始化哈夫曼樹(shù)
for (int i = 0; i < length; i++)
data[i] = new Node();
for (int i = 0; i < datain.Length; i++)
data[i] = datain[i];
//處理n個(gè)葉子結(jié)點(diǎn)，建立哈夫曼樹(shù)
for (int i = leafNum; i < length; i++)
{
//在全部結(jié)點(diǎn)中找權(quán)值最小的兩個(gè)結(jié)點(diǎn)
for (int j = 0; j < i; j++)
{
if (data[j].Parent == -1)
{
if (data[j].Weight < minL)
{
minR = minL;
minL = data[j].Weight;
rchild = lchild;
lchild = j;
}
else if (data[j].Weight < minR)
{
minR = data[j].Weight;
rchild = j;
}
}
}
data[lchild].Parent = data[rchild].Parent = i;
data[i].Weight = minL + minR;
data[i].LChild = lchild;
data[i].RChild = rchild;
}
}
}
class Program
{
static void Main(string[] args)
{
HuffmanTree tree = new HuffmanTree(5);
Node[] nodes = new Node[] { new Node(1), new Node(2), new Node(2.5d), new Node(3), new Node(2.6d) };
tree.Create(nodes);
Console.ReadLine();
}
}
/////////////////////////////節(jié)選自網(wǎng)絡(luò)上的資料、
posted on 2011-10-02 17:04
Yu_ 閱讀(3002)
評(píng)論(1) 編輯 收藏 引用 所屬分類(lèi):
數(shù)據(jù)結(jié)構(gòu)