Huffman算法的分析與應用

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