摘要： 該文首先分析了赫夫曼算法，給出了一種赫夫曼算法的實(shí)現(xiàn)方法，然后研究了赫夫曼算法在壓縮編碼，判定樹，在外部文件排序中的最佳歸并樹等中的應(yīng)用。

關(guān)鍵詞： 赫夫曼樹；算法；編碼；判定樹；歸并樹

中圖分類號(hào)： TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）13-3062-04

赫夫曼樹是一類帶權(quán)路徑長(zhǎng)度最短的樹，稱為最優(yōu)樹，有著廣泛的應(yīng)用。聯(lián)系到不同的計(jì)算機(jī)算法，可以賦予帶權(quán)外部路徑長(zhǎng)度不同的含義。例如，在解某些判定問題時(shí)，利用Huffman樹可以得到最佳判定算法[1-2]；在進(jìn)行快速遠(yuǎn)距離通信時(shí)，利用Huffman樹，可以得到Huffman編碼，它是一種無損的壓縮編碼；在外部排序中，對(duì)多個(gè)不等長(zhǎng)的有序記錄的二路歸并時(shí)，利用Huffman樹可以得到最佳合并順序，即最佳歸并樹。該文主要討論赫夫曼算法的一種實(shí)現(xiàn)方法及其不同的應(yīng)用。

1 赫夫曼算法

3EBpC5P81R9fBZqqW4K01gn9QxzA4pqXFuRGe8wFI3I=3.2 判定樹

在解某些判定問題時(shí)，如果將不同情況出現(xiàn)的頻度作為權(quán)重的話，利用Huffman算法可以構(gòu)建最佳判定樹。在編制一個(gè)將百分制轉(zhuǎn)換成優(yōu)、良、中、及格、不及格五級(jí)分制的程序時(shí)，一般學(xué)生的成績(jī)呈正態(tài)分布，各級(jí)別的比例分別為：優(yōu)秀10%，良好30%，中等40%，及格15%，不及格占5%左右。利用上述Huffman算法構(gòu)建的判定樹如圖3所示。按最佳判定樹編寫程序，可提高比較的效率，顯著降低操作時(shí)間。

3.3 最佳歸并樹

4 結(jié)論

Huffman樹與Huffman編碼有著廣泛的應(yīng)用，例如對(duì)Huffman編碼進(jìn)行改進(jìn)可用于軟件測(cè)試數(shù)據(jù)進(jìn)化生成 [3]、SVM 多分類器構(gòu)造[4]、超光譜圖像分層無損壓縮[5]、基于稀疏分解的交通圖像壓縮中[6]等等。因此，正確理解Huffman算法的實(shí)質(zhì)，對(duì)有關(guān)的研究工作提供有益的啟示。

參考文獻(xiàn)：

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M]. 北京：清華大學(xué)出版社，2010：144-148.

[2] 許卓群，楊冬青，唐世渭，等.數(shù)據(jù)結(jié)構(gòu)與算法[M].北京：高等教育出版社，2006：126-128.

[3] 鞏敦衛(wèi)，張巖.一種新的多路徑覆蓋測(cè)試數(shù)據(jù)進(jìn)化生成方法[J].電子學(xué)報(bào)，2010（6）：1299-1304.

[4] 谷勝偉.基于赫夫曼樹的SVM 多分類器構(gòu)造方法[J].滁州學(xué)院學(xué)報(bào)，2009，11（3）：41-43.

[5] 張威，田峰.超光譜圖像分層無損壓縮方案[J].小型微型計(jì)算機(jī)系統(tǒng)，2011，32（12）：2499-2503.

[6] 王慶， 張葛祥.基于稀疏分解的交通圖像壓縮[J].公路交通科技，2010，27（6）：112-116.