愛華網(wǎng)關(guān)鍵詞： 哈夫曼樹； 三叉哈夫曼樹； K叉哈夫曼樹；哈夫曼編碼
中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1006-8228（2013）09-41-02
1 二叉哈夫曼樹[1-2]的構(gòu)造算法
對(duì)于給定的數(shù)據(jù)序列，要生成帶權(quán)路徑長度最小的二叉樹，應(yīng)讓權(quán)值越大的葉結(jié)點(diǎn)越靠近樹根，權(quán)值越小的葉結(jié)點(diǎn)越遠(yuǎn)離樹根。哈夫曼最早給出了一個(gè)具有一般規(guī)律的算法，稱之為哈夫曼算法。
?、鸥鶕?jù)給定的n個(gè)權(quán)值{W1，W2，W3，…，Wi，…，Wn}構(gòu)成n棵二叉樹的初始集合F={T1，T2，T3…，Ti，…，Tn}，其中每棵二叉樹Ti中只有一個(gè)權(quán)值為Wi的根結(jié)點(diǎn)，它的左右子樹均為空。
?、圃贔中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹的根結(jié)點(diǎn)的權(quán)值之和。
?、?在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入到集合F中。
⑷重復(fù)⑵和⑶，直到集合F中只含有一棵樹為止。這棵樹便是哈夫曼樹。
2 三叉哈夫曼樹構(gòu)造的擴(kuò)展算法
與哈夫曼算法類似，可以每次取三個(gè)根結(jié)點(diǎn)權(quán)值最小的樹作子樹，構(gòu)造一棵新的三叉樹，算法思路如下。
⑴根據(jù)給定的n個(gè)權(quán)值{W1，W2，W3，…，Wi，…，Wn}構(gòu)成n棵三叉樹的初始集合F={T1，T2，T3，…，Ti…，Tn}，其中每棵三叉樹Ti中只有一個(gè)權(quán)值為Wi的根結(jié)點(diǎn)，它的左、中、右子樹均為空。
?、圃贔中選取三棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左、中、右子樹構(gòu)造一棵新的三叉樹，且新得到的三叉樹的根結(jié)點(diǎn)的權(quán)值為其左、中、右子樹的根結(jié)點(diǎn)的權(quán)值之和。
?、?在F中刪除這三棵樹，同時(shí)將新得到的三叉樹加入到集合F中。
?、?重復(fù)⑵和⑶，直到集合F中只含有一棵樹為止[3]。
此算法由二叉哈夫曼算法擴(kuò)展而來，因而將它稱為三叉哈夫曼樹構(gòu)造的擴(kuò)展算法。
3 k叉哈夫曼樹的構(gòu)造
設(shè)有n個(gè)信源符號(hào)，在傳輸過程中的概率分別是W1，W2，W3，…，Wn，將概率設(shè)為權(quán)值。k0=（n-1）mod（k-1），當(dāng)k0=0時(shí)，（n-1）/（k-1）為整數(shù)，哈夫曼樹中只有度為0和k的結(jié)點(diǎn)；當(dāng)k0≠0，即（n-1）/（k-1）不為整數(shù)時(shí)，需添加k-1-k0個(gè)權(quán)值為0的結(jié)點(diǎn)。算法思路如下。
?、抛鱪棵樹的集合F={T1，T2，T3，…，Ti，…，Tn}，每棵樹Ti只有一個(gè)權(quán)值為Wi的根結(jié)點(diǎn)，且均無子女。
⑵計(jì)算k0=（n-1）mod（k-1）；若k0≠0，則添加k-1-k0個(gè)權(quán)值為0的結(jié)點(diǎn)，并作為k-1-k0棵樹添加到F中，否則不用添加。
?、窃贔中選k棵根結(jié)點(diǎn)權(quán)值最小的樹作子樹，構(gòu)造一棵新的k叉樹，其根結(jié)點(diǎn)的權(quán)值為所有子樹根結(jié)點(diǎn)的權(quán)值之和，并在F中刪除這k棵樹，且將新得到的k叉樹加入F中。
?、戎貜?fù)⑶，直到F中只剩下一棵樹為止。則該樹即為k叉哈夫曼樹。
4 用C語言[4-6]實(shí)現(xiàn)
4.1 存儲(chǔ)結(jié)構(gòu)
由樹的孩子兄弟表示法及線索二叉樹存儲(chǔ)結(jié)構(gòu)中標(biāo)志域的啟發(fā)，采用如下存儲(chǔ)結(jié)構(gòu)：
struct hlnode
{ float weight；
struct hlnode *llink；
struct hlnode *rlink；
int tag；
}
其結(jié)點(diǎn)的結(jié)構(gòu)如圖1所示。
[llink＼&weight＼&tag＼&rlink＼&]
圖1 結(jié)點(diǎn)結(jié)構(gòu)圖
llink：指針，指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)；
weight：記錄該結(jié)點(diǎn)的權(quán)值；
tag：其取值為0，1，2，…，k-1；任一父結(jié)點(diǎn)，其第一個(gè)孩子結(jié)點(diǎn)到最后一個(gè)孩子結(jié)點(diǎn)的tag值按照k-1，k-2，…，2，1，0排列，這樣每個(gè)結(jié)點(diǎn)的tag值還表示其最后一位編碼的碼值；
rlink：指針。
?、女?dāng)tag=0時(shí)，指向該結(jié)點(diǎn)的父結(jié)點(diǎn)，且該結(jié)點(diǎn)為其父結(jié)點(diǎn)的最后一個(gè)孩子即第k個(gè)孩子；
?、飘?dāng)tag=n（n=k-1，k-2，…，2，1）時(shí)，指向該結(jié)點(diǎn)的下一個(gè)兄弟，且該結(jié)點(diǎn)為其父結(jié)點(diǎn)的第k-n個(gè)孩子。
可利用這種存儲(chǔ)結(jié)構(gòu)中所有葉子結(jié)點(diǎn)空的llink域?qū)⑷~子結(jié)點(diǎn)按權(quán)值的升序連接成一個(gè)葉子的單鏈表leaf。這樣在求編碼時(shí)，沿著鏈表leaf的llink域可以迅速找到信源符號(hào)所在的葉子結(jié)點(diǎn)，然后再對(duì)葉子結(jié)點(diǎn)求編碼。
4.2 算法描述[7-8]
K叉哈夫曼樹的構(gòu)造算法如下：
?、?建立一個(gè)帶頭結(jié)點(diǎn)的空鏈表L；
?、?讀入n個(gè)信源符號(hào)的權(quán)值，并升序存入鏈表L中；
⑶計(jì)算k0=（n-1）mod（k-1）；若k0≠0，則在鏈表L的表頭結(jié)點(diǎn)后插入k-1-k0個(gè)權(quán)值為0的結(jié)點(diǎn)；
?、热℃湵鞮中的前k個(gè)結(jié)點(diǎn)作子樹，產(chǎn)生一個(gè)新的結(jié)點(diǎn)作其父結(jié)點(diǎn)，父結(jié)點(diǎn)的權(quán)值為這k棵子樹根結(jié)點(diǎn)的權(quán)值之和；
⑸將子樹中的葉子結(jié)點(diǎn)鏈入鏈表leaf中，并從鏈表L中刪除這k棵子樹；
?、?將新產(chǎn)生的父結(jié)點(diǎn)按升序插入鏈表L中；
?、酥貜?fù)⑷、⑸、⑹，直到鏈表L中除表頭結(jié)點(diǎn)外只剩下一個(gè)結(jié)點(diǎn)為止，則該結(jié)點(diǎn)即為k叉哈夫曼樹的樹根結(jié)點(diǎn)；
?、?用指針r指向鏈表leaf的第一個(gè)結(jié)點(diǎn)；
?、蛯?dāng)前指針r所指結(jié)點(diǎn)的tag值存入數(shù)組cd[]中，整型變量sp為當(dāng)前結(jié)點(diǎn)的碼值在數(shù)組中的位置；
（10）通過rlink域找到當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)，將其tag值存入數(shù)組cd[]中；
?。?1）重復(fù)（10），直到到達(dá)根結(jié)點(diǎn)（即父結(jié)點(diǎn)為空的結(jié)點(diǎn)）為止，此時(shí)，sp為指針r所指結(jié)點(diǎn)的最后一位碼值在數(shù)組中的位置，按位置的逆序?qū)?shù)組中存放的碼值全部輸出，即為指針r所指結(jié)點(diǎn)的哈夫曼編碼。
（12）將指針r后移，重復(fù)⑼、（10）、（11），直到所有葉子結(jié)點(diǎn)的編碼皆已求出（即指針r為空）為止。
5 結(jié)束語
數(shù)據(jù)編碼技術(shù)在計(jì)算機(jī)通信和信息壓縮中一直占據(jù)著重要地位，依照哈夫曼樹得到字符編碼的算法作為通用的數(shù)據(jù)壓縮方法，是大多數(shù)通用壓縮程序的基礎(chǔ)，并且往往作為壓縮過程中的一個(gè)步驟。本文通過分析二叉哈夫曼樹及三種三叉哈夫曼樹的構(gòu)造算法，提出了k叉哈夫曼樹的構(gòu)造算法，并得到k進(jìn)制最優(yōu)前綴編碼。所求得的各葉子結(jié)點(diǎn)的代碼長度雖不等，但最長不會(huì)超過分支點(diǎn)個(gè)數(shù)x（葉子結(jié)點(diǎn)的路徑長度的最大值），而且k越大，平均編碼長度會(huì)越短，對(duì)數(shù)據(jù)通信、信息壓縮等領(lǐng)域有較大的促進(jìn)作用，而且k可以是任何大于2的正整數(shù)，應(yīng)用范圍更為廣闊。
參考文獻(xiàn)：
[1]劉愛民.離散數(shù)學(xué)[M].北京郵電大學(xué)出版社，2004.
[2]方景龍，王毅剛.應(yīng)用離散數(shù)學(xué)[M].人民郵電出版社，2005.
[3]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].清華大學(xué)出版社，2005.
[4]任正云.哈夫曼樹及其在信息編碼中的應(yīng)用[J].沙洋師范高等專科學(xué)校學(xué)報(bào)，2007.5：31-32
[5]黃錦祝.用C語言實(shí)現(xiàn)三叉哈夫曼樹[J].福建電腦，2004.3：64-65
[6]呂文志，戎麗霞.一種新的三叉哈夫曼樹生成算法[J].福建電腦，2006.7：91-92
[7]朱祥正.基于k叉樹的最優(yōu)樹[J].計(jì)算機(jī)應(yīng)用研究，1998.1：39-41
[8] 王玲.樹的父母—子女環(huán)存貯結(jié)構(gòu)[J].四川師范大學(xué)學(xué)報(bào)，2000.6：20-21
