哈夫曼樹在分類問題中的應用

宋　穎　趙大偉　劉思遠　畢明超

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

[關鍵詞]哈夫曼樹 分類 判定樹 哈夫曼算法

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

一、引言

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

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

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

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

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

二、哈夫曼樹的原理與技術

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

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

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

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

2．在F中選取根結點的權值最小和次小的兩棵二叉樹作為左、右子樹構造一棵新的二叉樹，這棵新的二叉樹根結點的權值為其左、右子樹根結點權值之和；

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

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

三、哈夫曼樹的實現

（一）哈夫曼樹在分類中的實現

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

1．先按給定的權值構造5棵二叉樹如圖3-1（a）所示；

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

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

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

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

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

（二）哈夫曼的算法

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

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

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

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

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

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

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

/*求給定權值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;

}

}

四、結束語

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

參考文獻：

[1]嚴尉敏、吳偉民，《數據結構（C語言版）》[M].北京：清華大學出版社，2001.

[2]陳元春、張亮、王勇，《實用數據結構基礎》[M].北京：中國鐵道出版社，2008.

[3]徐孝凱，《數據結構實用教程》[M].北京：清華大學出版社，2000.

[4]包振宇、孫干，《數據結構》[M].北京：中國鐵道出版社，2006.

作者簡介：

宋穎，副教授，技師，白城職業技術學院信息工程系主任。