赫夫曼樹遍歷算法的優化

摘要:對數據結構中赫夫曼樹和赫夫曼遍歷的算法問題進行探討，針對傳統使用的遍歷算法存在循環次數較多、算法時間復雜度較大問題，通過修改參數和循環體結構對原有算法進行改進，從而減少循環次數，降低算法時間復雜度，同時也提出了動態編碼算法等的優點和可行性。

關鍵詞:赫夫曼樹; 赫夫曼編碼; 算法時間復雜度; 靜態編碼算法; 參數;循環體

中圖分類號:TP312文獻標識碼:A文章編號:1009-3044(2009)25-7235-03

Optimization of Huffman Tree Traversal Arithmetic

XU Ying

(Anhui Vocational college of Electronics and Information Technology， Bengbu 233000， China)

Abstract: Investigating into data structure about Huffman tree and Huffman traversal arithmetic， It is discovered that there are many problems such as much more cycle and much higher time complexity in traditional traversal algorithm， the thesis submits a improved algorithm to reduce the cycles and time complexity through altering parameter and structure of loop body， and further promote the advantage and feasibility of dynamic encoder.

Key words: Huffman tree; Huffman encoding; time complexity; static encoder; loop body

赫夫曼(Huffman)樹，又稱最優樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度(若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數)。樹的帶權路徑長度記為WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N個權值Wi(i=1，2，...n)構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li(i=1，2，...n)?？梢宰C明赫夫曼樹的WPL是最小的。

1 赫夫曼編碼概述

赫夫曼在上世紀五十年代初就提出這種編碼時，根據字符出現的概率來構造平均長度最短的編碼。它是一種變長的編碼。在編碼中，若各碼字長度嚴格按照碼字所對應符號出現概率的大小的逆序排列，則編碼的平均長度是最小的。(注:碼字即為符號經赫夫曼編碼后得到的編碼，其長度是因符號出現的概率而不同，所以說赫夫曼編碼是變長的編碼。)。赫夫曼樹是現實生活中處理某些事務常用到的一種數據結構。對赫夫曼樹各終結點，進行二進制編碼，被稱為赫夫曼編碼，例如快速遠距離通信中所用到的電報，就是將報文中的每個字符出現的頻率高低構造出一棵赫夫曼樹，按每個字符(終結點)的位置進行赫夫曼編碼，經編碼后的報文總長減少，并用接受報文的一方也可以將電文正常編譯回原文。就可根據赫夫曼樹進行編碼。經赫夫曼編碼得到的對應的碼值。只要使用同一棵赫夫曼樹，就可把編碼還原成原來那組字符。顯然赫夫曼編碼是前綴編碼，即任一個字符的編碼都不是另一個字符的編碼的前綴，否則，編碼就不能進行翻譯。其編碼和譯碼的原理在清華大學出版社出版的嚴蔚敏和吳偉民編著的C語言版《數據結構》中已有詳細闡述，

1.1 赫夫曼編碼算法

在該書中，作者也用C語言對無棧非遞歸遍歷赫夫曼樹求赫夫曼編碼的算法進行了描述，筆者認為在該算法中，當指針P指向一個終結點時，必須使循環體中的語句循環執行三次才能完成對該終結點的訪問。因此對該算法增加一個語句，使得只要循環二次執行循環體就可完成對該終結點的訪問，具體算法如下[1]:

//無棧非遞歸遍歷赫夫曼樹，求赫夫曼編碼

HC=(Huffmancode)malloc((n+1)*sizeof(char*));

p=m;cdlen=0;

for(i=1;i<=m;++i) HT[i].weight=0;//遍歷赫夫曼樹時用作結點狀態標志

while(p){

if(HT[p].weight==0){

HT[p].weight=1;

if(HT[p].lchild!=0){p= HT[p].rchild=0;cd[cdlen++]=\"0\";}

else if(HT[p].rchild==0){//向左

HC[p]=(char*)malloc((cdlen+1)*sizeof(char));

cd[cdlen]=\"\\0\"; strcpy(HC[p]，cd); HT[p].weight=2;

}}

else if(HT[p].weight==1){

HT[p].weight=2;

If(HT[p].rchild=!0) {p= HT[p].rchild; cd[cdlen++]=\"1\";}

}

else{ HT[p].weight=0; p=HT[p].parent; --cdlen;}

}//while

在這種算法中，設置了一個HT[i].weight數組，用于存放遍歷赫夫曼樹時用作結點，狀態標志，它的含義是:

2.2 改進后的赫夫曼算法

修改后的算法自頂向下非遞歸的遍歷赫夫曼樹:(1)如果該點未被訪問過(HT[i].weight=0)，則遍歷其左子樹，并將臨時開辟的用來計算赫夫曼編碼的數組cd中添加一個數字“0”，如果左子樹為空，向右一步訪問其右子樹，如果右子樹也為空，則說明該結點為終結點，將cd中添加一個結束標識“10”，將該結點赫夫曼編碼放置在數組HT[i]中的訪問標識設置為2，表示該結點已經訪問結束。(2)第二種情況，如果該結點的左子樹已訪問完需要訪問其右子樹(在這種情況中出現的結點的右子樹都是非空的，即非終結點或成為分支結點，因為終結點已在情況1中討論完畢)將其標識值由1改為2，并將赫夫曼編碼中添加數字“1”。(3)第三種情況，如果訪問標識值為2，即該結點及其子樹已訪問結束，則退回到父結點，編碼長度減1。第三種情況是對前兩種情況的善后處理以便能訪問其他分支上的結點[2]。

再次考查該算法，讀者會發現，在遍歷結點i左子樹的時候，如果其左子樹非空，總要再次進入一個大的循環，于是筆者對此局部做了調整，并且根據調整后的結構特點，筆者為數組HT[i].weight的賦予另一種含義，即:

//無棧非遞歸遍歷赫夫曼樹，求赫夫曼編碼的改進算法

HC=(Huffmancode)malloc((n+1)*sizeof(char*));

p=m;cdlen=0;

for(i=1;i<=m;++i) HT[i].weight=0;//遍歷赫夫曼樹時用作結點狀態標志

while(p){

if(HT[p].weight==0){

while(p= HT[p].lchild=!0) {p= HT[p].rchild=0;cd[cdlen++]=\"0\";}

HT[p].weight=1;

}

If(HT[p].rchile==0){

HC[p]=(char*)malloc((cdlen+1)*sizeof(char));

cd[cdlen]=\"\\0\";strcpy(HC[p]，cd); HT[p].weight=2;

}

else if(HT[p].weight==1){

If(HT[p].rchild=!0) { p= HT[p].rchild; cd[cdlen++]=\"1\";}

}

else{ HT[p].weight=0;

p=HT[p].parent;

--cdlen;

HT[p].weight++;}

}//while

在這種算法中對待每個結點，也同樣分為三種情況:1)當HT[i].weight=0，即該結點為根的左子樹中還有結點未被訪問時，則遍歷其左子樹，每遍歷一層，赫夫曼編碼添加一個數字“0”，當此時的結點，再無左子樹時，訪問狀態值設置為1，表示此時結點左子樹已訪問完畢，向右一步，如果其無右子樹，則此節點訪問完畢，保存其赫夫曼編碼[3-4]。2)當HT[i].weight=1，該結點左子樹已訪問完畢，則向右一步訪問其右子樹編碼添加一個數字“1”。3)當HT[i].weight=2，該結點右子樹上所有結點已訪問完畢，應跳回其父結點，編碼減少一位，并且對它父結點的訪問狀態值加上1，如果是從其左子樹跳出，則狀態值由0變為1(表示其左子樹已被訪問完畢)，若從其右子樹跳回，則狀態值由1變為2(表示其右子樹已訪問完畢)，繼續循環[5]。

算法中，方框中的語句也可以不寫，這是由赫夫曼樹的結構特點所決定的，赫夫曼結構的特點是，如果某個結點i存在左子樹，那么它必定也有右子樹，反之亦然，即左右子樹必定同時存在或同時不存在，因此在第一種情況的討論中，方框上方的語句說明某結點已無左子樹，那么不用判斷即可得知該結點也無右子樹，因此可以順序執行方框下方語句，而無需方框中判斷語句。同樣第二種情況中，第一句判斷HT[i].weight=1表示某結點P有左子樹且樹已訪問結束，而并非指P無左子樹，因此也可以不經判斷繼續執行方框之后的語句[6]。

3 總結

本文中討論的遍歷編碼方法是靜態的赫夫曼編碼，它對需要編碼的數據進行兩遍掃描:第一遍統計原數據中各字符出現的頻率，利用得到的頻率值創建赫夫曼樹，并必須把樹的信息保存起來，即把字符0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，(用4Bytes的長度存儲頻率值，頻率值的表示范圍為0～2^32-1，這已足夠表示大文件中字符出現的頻率了)以便解壓時創建同樣的赫夫曼樹進行解壓;第二遍則根據第一遍掃描得到的赫夫曼樹進行編碼，并把編碼后得到的碼字存儲起來。 靜態赫夫曼編碼方法有一些缺點:1)對于過短的文件進行編碼的意義不大，因為光以4BYTES的長度存儲赫夫曼樹的信息就需1024Bytes的存儲空間;2)進行赫夫曼編碼，存儲編碼信息時，若用與通訊網絡，就會引起較大的延時;3)對較大的文件進行編碼時，頻繁的磁盤讀寫訪問會降低數據編碼的速度[7]。

因此，后來有人提出了一種動態的赫夫曼編碼方法。動態赫夫曼編碼使用一棵動態變化的赫夫曼樹，對第t+1個字符的編碼是根據原始數據中前t個字符得到的赫夫曼樹來進行的，編碼和解碼使用相同的初始赫夫曼樹，每處理完一個字符，編碼和解碼使用相同的方法修改赫夫曼樹，所以沒有必要為解碼而保存赫夫曼樹的信息。編碼和解碼一個字符所需的時間與該字符的編碼長度成正比，所以動態赫夫曼編碼可實時進行。動態赫夫曼編碼比靜態赫夫曼編碼復雜的多，有興趣的讀者可參考有關數據結構與算法的書籍[8]。

參考文獻:

[1] 嚴蔚敏，吳偉民. 數據結構(C語言版)[M]. 北京:清華大學出版社，1997.144-146.

[2] 汪杰 等.數據結構經典算法實現與習題解答[M].北京:人民郵電出版社，2004，168-171.

[3] 劉奇超. 赫夫曼編碼及其應用[J].科技信息(學術版)，2008(8):54-57.

[4] 徐鳳生，錢愛增，李海軍，李天志.赫夫曼編碼的求解算法[J].德州學院學報，2007，23(2):48-51.

[5] 唐駿，徐明亮，馬鴻飛.一種赫夫曼碼生成算法研究[J].電子元器件應用，2007，9(1):22-25.

[6] 趙瑾，蘇淑華.算數編碼與赫夫曼編碼的比較[J].福建電腦，2005(7):20-22.

[7] 王群芳.哈夫曼編碼的另一種實現[J].安徽教育學院學報，2006，24(6):36-39.

[8] 黃錦祝.用C語言實現三叉哈夫曼樹[J].福建電腦，2004(3):36-39.