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