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

宋　穎　趙大偉　劉思遠(yuǎn)　畢明超

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

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

中圖分類號(hào)：O24文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1671－7597（2009）0510054－02

一、引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)所示的各個(gè)非終端結(jié)點(diǎn)上設(shè)置適當(dāng)?shù)臈l件，就得到圖1-1(b)所示的判定樹。因此，這一判定樹描述了求解給定問題的最佳分類方法。

（二）哈夫曼的算法

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

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

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

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

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

（2）將根為T[X]和T[y]的兩棵樹合并，使其成為新結(jié)點(diǎn)T[i]為根的二叉樹。同時(shí)修改T[x]和T[y]的雙親域parent，使其指向新結(jié)點(diǎn)T[i]，這意味著它們?cè)诋?dāng)前森林已不再是根。將T[x]和T[y]的權(quán)值相加后作為新結(jié)點(diǎn)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)用需求可以對(duì)哈夫曼樹做不同的解釋，即賦予不同的含義。本文詳加討論的問題只是其中的一種解釋。雖然解決分類問題的方法很多，但利用哈夫曼樹可謂是求解給定問題的最佳分類方法。

參考文獻(xiàn)：

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

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

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

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

作者簡介：

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