本站原创摘 要 ： 该文首先分析了赫夫曼算法,给出了一种赫夫曼算法的实现方法,然后研究了赫夫曼算法在压缩编码,判定树,在外部文件排序中的最佳归并树等中的应用.
关 键 词 ： 赫夫曼树；算法；编码；判定树；归并树
中图分类号： TP301 文献标识码：A 文章编号：1009-3044（2013）13-3062-04
赫夫曼树是一类带权路径长度最短的树,称为最优树,有着广泛的应用.联系到不同的计算机算法,可以赋予带权外部路径长度不同的含义.例如,在解某些判定问题时,利用Huffman树可以得到最佳判定算法[1-2]；在进行快速远距离通信时,利用Huffman树,可以得到Huffman编码,它是一种无损的压缩编码；在外部排序中,对多个不等长的有序记录的二路归并时,利用Huffman树可以得到最佳合并顺序,即最佳归并树.该文主要讨论赫夫曼算法的一种实现方法及其不同的应用.
1.赫夫曼算法
3.2 判定树
在解某些判定问题时,如果将不同情况出现的频度作为权重的话,利用Huffman算法可以构建最佳判定树.在编制一个将百分制转换成优、良、中、及格、不及格五级分制的程序时,一般学生的成绩呈正态分布,各级别的比例分别为：优秀10%,良好30%,中等40%,及格15%,不及格占5%左右.利用上述Huffman算法构建的判定树如图3所示.按最佳判定树编写程序,可提高比较的效率,显著降低操作时间.
3.3 最佳归并树
4.结论
Huffman树与Huffman编码有着广泛的应用,例如对Huffman编码进行改进可用于软件测试数据进化生成 [3]、SVM 多分类器构造[4]、超光谱图像分层无损压缩[5]、基于稀疏分解的交通图像压缩中[6]等等.因此,正确理解Huffman算法的实质,对有关的研究工作提供有益的启示.