鄭文艷

摘 要： 字符編碼與信息壓縮是計算機應(yīng)用的重要研究課題，許多學(xué)者對此作了很多非常有價值的研究。文章簡單分析了二叉哈夫曼樹的構(gòu)造及編碼，通過比較三種構(gòu)造三叉哈夫曼樹的算法，提出了構(gòu)造任意K叉哈夫曼樹及K進制的最優(yōu)前綴編碼的算法，并給出C語言源程序，使哈夫曼編碼的應(yīng)用范圍變得更為廣闊。

關(guān)鍵詞： 哈夫曼樹； 三叉哈夫曼樹； K叉哈夫曼樹； 哈夫曼編碼

中圖分類號：TP312 文獻標志碼：A 文章編號：1006-8228（2013）09-41-02

1 二叉哈夫曼樹[1-2]的構(gòu)造算法

對于給定的數(shù)據(jù)序列，要生成帶權(quán)路徑長度最小的二叉樹，應(yīng)讓權(quán)值越大的葉結(jié)點越靠近樹根，權(quán)值越小的葉結(jié)點越遠離樹根。哈夫曼最早給出了一個具有一般規(guī)律的算法，稱之為哈夫曼算法。

⑴ 根據(jù)給定的n個權(quán)值{W1，W2，W3，…，Wi，…，Wn}構(gòu)成n棵二叉樹的初始集合F={T1，T2，T3…，Ti，…，Tn}，其中每棵二叉樹Ti中只有一個權(quán)值為Wi的根結(jié)點，它的左右子樹均為空。

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

⑶ 在F中刪除這兩棵樹，同時將新得到的二叉樹加入到集合F中。

⑷ 重復(fù)⑵和⑶，直到集合F中只含有一棵樹為止。這棵樹便是哈夫曼樹。

2 三叉哈夫曼樹構(gòu)造的擴展算法

與哈夫曼算法類似，可以每次取三個根結(jié)點權(quán)值最小的樹作子樹，構(gòu)造一棵新的三叉樹，算法思路如下。

⑴ 根據(jù)給定的n個權(quán)值{W1，W2，W3，…，Wi，…，Wn}構(gòu)成n棵三叉樹的初始集合F={T1，T2，T3，…，Ti…，Tn}，其中每棵三叉樹Ti中只有一個權(quán)值為Wi的根結(jié)點，它的左、中、右子樹均為空。

⑵ 在F中選取三棵根結(jié)點的權(quán)值最小的樹作為左、中、右子樹構(gòu)造一棵新的三叉樹，且新得到的三叉樹的根結(jié)點的權(quán)值為其左、中、右子樹的根結(jié)點的權(quán)值之和。

⑶ 在F中刪除這三棵樹，同時將新得到的三叉樹加入到集合F中。

⑷ 重復(fù)⑵和⑶，直到集合F中只含有一棵樹為止[3]。

此算法由二叉哈夫曼算法擴展而來，因而將它稱為三叉哈夫曼樹構(gòu)造的擴展算法。

3 k叉哈夫曼樹的構(gòu)造

設(shè)有n個信源符號，在傳輸過程中的概率分別是W1，W2，W3，…，Wn，將概率設(shè)為權(quán)值。k0=（n-1）mod（k-1），當k0=0時，（n-1）/（k-1）為整數(shù)，哈夫曼樹中只有度為0和k的結(jié)點；當k0≠0，即（n-1）/（k-1）不為整數(shù)時，需添加k-1-k0個權(quán)值為0的結(jié)點。算法思路如下。

⑴ 作n棵樹的集合F={T1，T2，T3，…，Ti，…，Tn}，每棵樹Ti只有一個權(quán)值為Wi的根結(jié)點，且均無子女。

⑵ 計算k0=（n-1）mod（k-1）；若k0≠0，則添加k-1-k0個權(quán)值為0的結(jié)點，并作為k-1-k0棵樹添加到F中，否則不用添加。

⑶ 在F中選k棵根結(jié)點權(quán)值最小的樹作子樹，構(gòu)造一棵新的k叉樹，其根結(jié)點的權(quán)值為所有子樹根結(jié)點的權(quán)值之和，并在F中刪除這k棵樹，且將新得到的k叉樹加入F中。

⑷ 重復(fù)⑶，直到F中只剩下一棵樹為止。則該樹即為k叉哈夫曼樹。

4 用C語言[4-6]實現(xiàn)

4.1 存儲結(jié)構(gòu)

由樹的孩子兄弟表示法及線索二叉樹存儲結(jié)構(gòu)中標志域的啟發(fā)，采用如下存儲結(jié)構(gòu)：

struct hlnode

{ float weight；

struct hlnode *llink；

struct hlnode *rlink；

int tag；

}

其結(jié)點的結(jié)構(gòu)如圖1所示。

[llink＼&weight＼&tag＼&rlink＼&]

圖1 結(jié)點結(jié)構(gòu)圖

llink：指針，指向該結(jié)點的第一個孩子結(jié)點；

weight：記錄該結(jié)點的權(quán)值；

tag：其取值為0，1，2，…，k-1；任一父結(jié)點，其第一個孩子結(jié)點到最后一個孩子結(jié)點的tag值按照k-1，k-2，…，2，1，0排列，這樣每個結(jié)點的tag值還表示其最后一位編碼的碼值；

rlink：指針。

⑴ 當tag=0時，指向該結(jié)點的父結(jié)點，且該結(jié)點為其父結(jié)點的最后一個孩子即第k個孩子；

⑵ 當tag=n（n=k-1，k-2，…，2，1）時，指向該結(jié)點的下一個兄弟，且該結(jié)點為其父結(jié)點的第k-n個孩子。

可利用這種存儲結(jié)構(gòu)中所有葉子結(jié)點空的llink域?qū)⑷~子結(jié)點按權(quán)值的升序連接成一個葉子的單鏈表leaf。這樣在求編碼時，沿著鏈表leaf的llink域可以迅速找到信源符號所在的葉子結(jié)點，然后再對葉子結(jié)點求編碼。

4.2 算法描述[7-8]

K叉哈夫曼樹的構(gòu)造算法如下：

⑴ 建立一個帶頭結(jié)點的空鏈表L；

⑵ 讀入n個信源符號的權(quán)值，并升序存入鏈表L中；

⑶ 計算k0=（n-1）mod（k-1）；若k0≠0，則在鏈表L的表頭結(jié)點后插入k-1-k0個權(quán)值為0的結(jié)點；

⑷ 取鏈表L中的前k個結(jié)點作子樹，產(chǎn)生一個新的結(jié)點作其父結(jié)點，父結(jié)點的權(quán)值為這k棵子樹根結(jié)點的權(quán)值之和；

⑸ 將子樹中的葉子結(jié)點鏈入鏈表leaf中，并從鏈表L中刪除這k棵子樹；

⑹ 將新產(chǎn)生的父結(jié)點按升序插入鏈表L中；

⑺ 重復(fù)⑷、⑸、⑹，直到鏈表L中除表頭結(jié)點外只剩下一個結(jié)點為止，則該結(jié)點即為k叉哈夫曼樹的樹根結(jié)點；

⑻ 用指針r指向鏈表leaf的第一個結(jié)點；

⑼ 將當前指針r所指結(jié)點的tag值存入數(shù)組cd[]中，整型變量sp為當前結(jié)點的碼值在數(shù)組中的位置；

（10） 通過rlink域找到當前結(jié)點的父結(jié)點，將其tag值存入數(shù)組cd[]中；

（11） 重復(fù)（10），直到到達根結(jié)點（即父結(jié)點為空的結(jié)點）為止，此時，sp為指針r所指結(jié)點的最后一位碼值在數(shù)組中的位置，按位置的逆序?qū)?shù)組中存放的碼值全部輸出，即為指針r所指結(jié)點的哈夫曼編碼。

（12） 將指針r后移，重復(fù)⑼、（10）、（11），直到所有葉子結(jié)點的編碼皆已求出（即指針r為空）為止。

5 結(jié)束語

數(shù)據(jù)編碼技術(shù)在計算機通信和信息壓縮中一直占據(jù)著重要地位，依照哈夫曼樹得到字符編碼的算法作為通用的數(shù)據(jù)壓縮方法，是大多數(shù)通用壓縮程序的基礎(chǔ)，并且往往作為壓縮過程中的一個步驟。本文通過分析二叉哈夫曼樹及三種三叉哈夫曼樹的構(gòu)造算法，提出了k叉哈夫曼樹的構(gòu)造算法，并得到k進制最優(yōu)前綴編碼。所求得的各葉子結(jié)點的代碼長度雖不等，但最長不會超過分支點個數(shù)x（葉子結(jié)點的路徑長度的最大值），而且k越大，平均編碼長度會越短，對數(shù)據(jù)通信、信息壓縮等領(lǐng)域有較大的促進作用，而且k可以是任何大于2的正整數(shù)，應(yīng)用范圍更為廣闊。

參考文獻：

[1] 劉愛民.離散數(shù)學(xué)[M].北京郵電大學(xué)出版社，2004.

[2] 方景龍，王毅剛.應(yīng)用離散數(shù)學(xué)[M].人民郵電出版社，2005.

[3] 嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].清華大學(xué)出版社，2005.

[4] 任正云.哈夫曼樹及其在信息編碼中的應(yīng)用[J].沙洋師范高等?？茖W(xué)校學(xué)報，2007.5：31-32

[5] 黃錦祝.用C語言實現(xiàn)三叉哈夫曼樹[J].福建電腦，2004.3：64-65

[6] 呂文志，戎麗霞.一種新的三叉哈夫曼樹生成算法[J].福建電腦，2006.7：91-92

[7] 朱祥正.基于k叉樹的最優(yōu)樹[J].計算機應(yīng)用研究，1998.1：39-41

[8] 王玲.樹的父母—子女環(huán)存貯結(jié)構(gòu)[J].四川師范大學(xué)學(xué)報，2000.6：20-21