哈夫曼樹在分類問題中的應(yīng)用

宋　穎　趙大偉　劉思遠　畢明超

[摘要]分類是一種常用運算，其作用是將輸入數(shù)據(jù)按預(yù)定的標準劃分成不同的種類。雖然解決分類問題的方法很多，但利用哈夫曼樹可謂是求解給定問題的最佳分類方法。因此，首先闡述哈夫曼樹的原理，然后以根據(jù)檢測結(jié)果劃分產(chǎn)品質(zhì)量等級為例進一步論述哈夫曼樹的主要技術(shù)及實現(xiàn)，最后總結(jié)哈夫曼樹的優(yōu)勢。

[關(guān)鍵詞]哈夫曼樹 分類 判定樹 哈夫曼算法

中圖分類號：O24文獻標識碼：A文章編號：1671－7597（2009）0510054－02

一、引言

樹有廣泛的應(yīng)用，其中一類重要的應(yīng)用是描述分類過程。分類是一種常用運算，其作用是將輸入數(shù)據(jù)按預(yù)定的標準劃分成不同的種類。例如，將學生考試的百分制成績轉(zhuǎn)換為不及格、及格、中、良好、優(yōu)秀，那么如何由分數(shù)段的值確定其分級就是一個分類問題，學生成績分布情況見表（一）。

再如，某工廠對其產(chǎn)品質(zhì)量進行自動檢測，并根據(jù)檢測結(jié)果劃分產(chǎn)品質(zhì)量等級，如何由產(chǎn)品的檢測結(jié)果值m確定其質(zhì)量等級也是一個分類問題，等級標準見表（二）。

用于描述分類過程的二叉樹稱為判定樹。判定樹的每個非終端結(jié)點包含一個條件，因而對應(yīng)于一次比較或判斷；每個終端結(jié)點包含一個種類標記，對應(yīng)于一種分類結(jié)果。如圖1(a)、(b)所示為上述求解產(chǎn)品的質(zhì)量分類問題的兩棵判定樹，其中每顆樹上的每個非終端結(jié)點都對應(yīng)五個條件判斷，即對檢測m的五次比較。

那么究竟將這個分類過程表示成哪一棵判定樹，才能使其執(zhí)行時間最短呢？讓我們對上述判斷框做一具體的分析。假設(shè)需要分級的產(chǎn)品有N=100000件，并且這批產(chǎn)品的等級分布如表（二）中表格的第三行所示。對應(yīng)圖1-1(a)、(b)中的比較次數(shù)分別如表（三）所示。

相對而言，圖1(b)這棵判定樹對所有產(chǎn)品定級，總比較次數(shù)比圖1(a)將少做40000次比較，平均比較次數(shù)也下降為2.3。這說明，按不同判定樹進行分類的時間復(fù)雜性是不同的，有時可能相差很大，因此，怎樣能構(gòu)造出時間性能最高判定樹是一個值得研究的問題。

二、哈夫曼樹的原理與技術(shù)

為解決上述分類問題，首先必須找出一種一般化的方法以確定任一判定樹的平均比較次數(shù)。設(shè)T是一判定樹，其終端結(jié)點為N1，...，NK。每個終端結(jié)點Ni對應(yīng)的百分比為Wi，這里W1+W2+...+Wk=1。通常將Wi稱為Ni的權(quán)。再假定Ni的祖先數(shù)為Li。為區(qū)分出Ni對應(yīng)的分類結(jié)果需做Li次比較。在圖(b)所示的判定樹上,葉子B的祖先有三個，它們正好是為區(qū)分出等級B進行的三次比較。這樣，按T進行分類的平均比較次數(shù)為WPL(T)=(∑(Wi*N*Li))/N＝∑Wi*Li(i＝1..k)上述問題可重新表述為：給定一組值W1，...，

Wk，如何構(gòu)造一棵有K個葉子且分別以這些值為權(quán)的判定樹，使用權(quán)得其平均比較次數(shù)最小。滿足上述條件的判定樹稱為哈夫曼樹。

一般情況下，最優(yōu)二叉樹中，權(quán)越大的葉子離根越近。那么，如何構(gòu)造最優(yōu)二叉樹呢？哈夫曼（Haffman）依據(jù)這一特點于1952年提出了一種簡單而有效的方法，這種方法的基本思想是：

1．由給定的n個權(quán)值{W1，W2，…，Wn}構(gòu)造n棵只有一個葉結(jié)點的二叉樹，從而得到一個二叉樹的集合F＝{T1，T2，…，Tn}；

2．在F中選取根結(jié)點的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新的二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點權(quán)值之和；

3．在集合F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到集合F中；

4．重復(fù)2、3兩步，當F中只剩下一棵二叉樹時，這棵二叉樹便是所要建立的哈夫曼樹。

三、哈夫曼樹的實現(xiàn)

（一）哈夫曼樹在分類中的實現(xiàn)

以表（二）中第三行的五個百分比為給定值，按上述哈夫曼算法建立哈夫曼樹的過程如下。

1．先按給定的權(quán)值構(gòu)造5棵二叉樹如圖3-1（a）所示；

2．再取0.1，0.2另外構(gòu)造一棵新的二叉樹如圖3-1（b）所示；

3．再取0.2，0.2另外構(gòu)造一棵新的二叉樹如圖3-1（c）所示；

4．再取0.3，0.3另外構(gòu)造一棵新的二叉樹如圖3-1（d）所示；

5．再取0.4，0.6另外構(gòu)造一棵新的二叉樹如圖3-1（e）所示，即哈夫曼樹。

在得到的哈夫曼樹圖3-1(e)所示的各個非終端結(jié)點上設(shè)置適當?shù)臈l件，就得到圖1-1(b)所示的判定樹。因此，這一判定樹描述了求解給定問題的最佳分類方法。

（二）哈夫曼的算法

由上述哈夫曼樹的原理可知，最終求得的哈夫曼樹中共有2N-1個結(jié)點，其中N個葉結(jié)點是初始森林中的N個孤立結(jié)點，并且哈夫曼樹中沒有度數(shù)為1的分支結(jié)點。由于結(jié)點數(shù)已知且固定不變，可采用靜態(tài)鏈表作存儲結(jié)構(gòu)。設(shè)置一個大小為2K-1的數(shù)組，令數(shù)組的每個元素由四個域組成，它們分別用于存儲權(quán)值、雙親指針和左右孩子指針。在這種存儲結(jié)構(gòu)上的哈夫曼算法可描述如下：

1．將哈夫曼樹向量(T類型為hftree)中的2n-1結(jié)點初始化：即將各結(jié)點中的三個指針和權(quán)值均置為0。

2．讀入N個權(quán)值放入向量T的前N個分量中，它們是初始森林中的N個孤立的根結(jié)點上的權(quán)值。

3．對森林中的樹進行N-1次合并，共產(chǎn)生N-1個新結(jié)點，依次放入向量T的第i個分量中(N+1<=i<=M〉。每次合并的步驟是：

（1）在當前森林的所有結(jié)點T[j](1<=j<=i-1)中，選取具有最小權(quán)值和次小權(quán)值的兩個根結(jié)點，分別用x和y記住這兩個根結(jié)點在向量T中的下標。

（2）將根為T[X]和T[y]的兩棵樹合并，使其成為新結(jié)點T[i]為根的二叉樹。同時修改T[x]和T[y]的雙親域parent，使其指向新結(jié)點T[i]，這意味著它們在當前森林已不再是根。將T[x]和T[y]的權(quán)值相加后作為新結(jié)點T[i]的權(quán)值。

void huffman(int k,float W[k],hftree T)

/*求給定權(quán)值W的哈夫曼樹T*/

{ int i,j,x,y;

float m,n;

for (i=0;i<2*k-1;i++) /*置初值*/

{ T[i].parent=-1; T[i].lchild=-1; T[i].rchild=-1;

if (i

else T[i].wt=0

}

for (i=0;i

{ x:=0; y:=0:m=maxint: n:=maxint;

for (j=0;j

if ((T[j].wt

{ n=m; y=x; m=T[j].wt; x=j; }

else if ((T[j].wt

{n=T[j].wt; y=j };

T[x].parent=k+i; T[y].parent=k+i; /*合并成一棵新的二叉樹 */

T[k+i].wt=m+n;

T[k+i].lchild=x; T[k+i].rchild=y;

}

}

四、結(jié)束語

哈夫曼樹和哈夫曼算法的應(yīng)用十分廣泛，根據(jù)不同的應(yīng)用需求可以對哈夫曼樹做不同的解釋，即賦予不同的含義。本文詳加討論的問題只是其中的一種解釋。雖然解決分類問題的方法很多，但利用哈夫曼樹可謂是求解給定問題的最佳分類方法。

參考文獻：

[1]嚴尉敏、吳偉民，《數(shù)據(jù)結(jié)構(gòu)（C語言版）》[M].北京：清華大學出版社，2001.

[2]陳元春、張亮、王勇，《實用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)》[M].北京：中國鐵道出版社，2008.

[3]徐孝凱，《數(shù)據(jù)結(jié)構(gòu)實用教程》[M].北京：清華大學出版社，2000.

[4]包振宇、孫干，《數(shù)據(jù)結(jié)構(gòu)》[M].北京：中國鐵道出版社，2006.

作者簡介：

宋穎，副教授，技師，白城職業(yè)技術(shù)學院信息工程系主任。