2009 NO.28|中國科教創(chuàng)新導刊理論前沿China Education Innovation HeraldHuffman算法的分析與應用牛雷婷1.2(1.聊城教育學院(聊城大學東昌學院)電子科學系山東聊城252000; 2.山東科技大學信息科學與工程學院山東青 島.266510)摘要:在目前的信息科學領域,數(shù)據(jù)壓鳊技術占有重要地住，而Huffman算法在數(shù)據(jù)壓縮場合的應用甚為廣泛。除此之外，Huffman算法在數(shù)據(jù)庫系統(tǒng)及網(wǎng)絡通信等領域發(fā)揮著越來越重要的作用，究其原因,主要是由于通過Huffman算法可實現(xiàn)存儲結構、編碼方式及最小權值的選擇,從而獲得明顯的壓蝙效果。關鍵詞:Huffman算法數(shù)據(jù)壓鳊 分析應用中圖分類號:G642文獻標識碼: A文章編號:1673-9795(2009)10(a)-0087-01信息科學領域中數(shù)據(jù)壓縮技術發(fā)揮著種無損壓縮,可對壓縮后的數(shù)據(jù)進行安全重要作用，通過數(shù)據(jù)壓縮，可使文件所占存.恢復,它不僅可縮小文件的存儲空間,還可儲空間變小，更重要的是,它可使模塊間的四以提高模塊間的數(shù)據(jù)交換速度,因而有著數(shù)據(jù)交換速度大大提高。數(shù)據(jù)壓縮的主要特別廣泛的應用范圍.針對不同的應用場任務是采用不等長的二進制碼去縮短文件⑦合,赫夫曼樹中葉子結點的權值對應不同中出現(xiàn)頻率高的字符,從而減少不必要的的意義,如利用Huffman算法可實現(xiàn)最佳的空間浪費,而Huffman算法是利用二叉樹去自白判定過程,此時權值是作為字符或符號出構造前綴編碼,它按照權值大小去選擇兩現(xiàn)的頻率存在的,而在面對排序問題時,權個最小結點組成子樹，重復組樹從而最終圖3值又被視為序列長度值。除此之外，建成一棵新的帶權路徑長度最小的二叉Huffman算法還可應用于數(shù)據(jù)傳送、視頻信樹。因此在目前的數(shù)據(jù)壓縮領域,Huffman號壓縮等領域。算法的應用越來越廣泛，除此之外，例2:用Huffman算法對文件內容進行Huffman算法在信息檢索系統(tǒng)、數(shù)據(jù)庫系壓縮.統(tǒng)、網(wǎng)絡通信等場合也有著廣泛的應用。壓縮過程可分以下三步:(1)計算文件中數(shù)據(jù)的出現(xiàn)頻率,以此構造赫夫曼樹,并1 Huffman算法簡介對數(shù)據(jù)進行編碼;(2)在上步的基礎上,將數(shù)1.1 Huffman算法的定義據(jù)譯為赫夫曼編碼;(3)不同數(shù)據(jù)對照不同所謂Huffman算法,是由赫夫曼(D.A.要求進行數(shù)據(jù)壓縮,最終完成對所有文件Huffman)在1952針對構造帶權路徑長度內容的壓縮。WPL最小的二叉樹而給出的帶有一般規(guī)律圖4以"verygood"8個字符為例，按照上述的算法.即設有n個權值{ W1, W2, ..Wn},步驟，可將字符個數(shù)最終壓縮到3個字符，構造一棵有n個葉子葉子的二又樹,每個葉2 存在的問題及改進措施而重復的字符個數(shù)越多,壓縮比例就會越子結點帶有權值Wi,且?guī)嗦窂介L度WPL 2.1 存在的問題方。在上述Huffman算法描述的第(2)步中,1.2 Huffman算法的算法描述選取權值最小的兩個結點作為左右子樹組4結語(1)根據(jù)給定的n個權值{W1, W2,..成新的二叉樹,形成新的結點,此時若出現(xiàn)學習數(shù)據(jù)結構的目標之一便是能將Wn}構成n棵二叉樹的集合F={T1,T2,-,多個權值相同的結點,按上述算法描述則Huffman算法 靈活運用,這看似簡單，但真Tn},其中每棵二叉樹Ti中只有一個帶權為不能解決此問題,因為若單純按照規(guī)定去正實現(xiàn)需要結合數(shù)據(jù)結構中的其他算法，Wi的根結點,其左右子樹均空。構遣新二叉樹,則由于根結點權值相同的應 首先掌握Huffman算法的基本原理，了解(2)在F中選取兩棵根結點的權值最小多棵子樹 ，深度卻不同,選擇不同子樹所得Huffman算 法的應用領域，從而為能最終靈的樹作為左右子樹構造一新的二叉樹,置的新二叉 樹的深度也是不相同的。因而,同活運用該算法打好 基礎。新二叉樹的根結點權值為其左、右子樹上樣一組待編碼元素可能構建出多棵深度和.根結點的權值之和。結構都不相同的赫夫曼樹。參考文獻(3)在F中刪除這兩棵樹，同時將得到的2.2 改進措施[1]嚴蔚敏,吳偉民.數(shù)據(jù)結構(C語言版)M].新二叉樹加入到F中。由以上描述可知,在選取權值最小的清華大學出版社,2008.(4)重復(2).(3)至F只含一棵樹為止,這兩個結點構造新二叉樹過程中,一旦遇到[2] 韓俊英，韓虎.Hufman算法的分析與改棵樹便是赫夫曼樹。多個結點權值相同的情況,選擇結點不同，進[J]. 蘭州鐵道學院學報，2003(6).例1:給定一組權值{8,7,4,1}構造赫夫最終構造的赫夫曼樹也不同，如此將 [3] 王文莉. Huffman算法的實現(xiàn)[J].鄭州鐵曼樹。Huffman算法應用到不同場合時,便無法取路職業(yè)技術學院學報, 2005(6).分析:按上述Huffman算法構造赫夫曼得 預期效果.由此可將Huffman算法完善改[4] 楊利華,李娟,彭永康.哈夫曼算法的改樹圖示如圖1-4. .進如下:進與應用[J].電腦知識與技術,2005第(1).(3). (4)步保持不變,第(2)步改(11).⑧⑦④?為:在F中選取兩棵根結點的權值最小的樹作為左右子樹構造- .新的二叉樹，當存在.圖1多棵子樹根結點的權值相同的情況時,選取深度小的子樹用于構造新的新二叉樹的根結點權值為其左中國煤化工TYHCNMHG.3 Huffman算法的應用圖2Huffman算法是數(shù)據(jù)壓縮場合中的一中國科教創(chuàng)新導刊China Education Innovation Herald87