哈夫曼算法及其应用研究

摘要： 该文首先分析了赫夫曼算法，给出了一种赫夫曼算法的实现方法，然后研究了赫夫曼算法在压缩编码，判定树，在外部文件排序中的最佳归并树等中的应用。

关键词： 赫夫曼树；算法；编码；判定树；归并树

中图分类号： TP301 文献标识码：A 文章编号：1009-3044（2013）13-3062-04

赫夫曼树是一类带权路径长度最短的树，称为最优树，有着广泛的应用。联系到不同的计算机算法，可以赋予带权外部路径长度不同的含义。例如，在解某些判定问题时，利用Huffman树可以得到最佳判定算法[1-2]；在进行快速远距离通信时，利用Huffman树，可以得到Huffman编码，它是一种无损的压缩编码；在外部排序中，对多个不等长的有序记录的二路归并时，利用Huffman树可以得到最佳合并顺序，即最佳归并树。该文主要讨论赫夫曼算法的一种实现方法及其不同的应用。

1 赫夫曼算法

3EBpC5P81R9fBZqqW4K01gn9QxzA4pqXFuRGe8wFI3I=3.2 判定树

在解某些判定问题时，如果将不同情况出现的频度作为权重的话，利用Huffman算法可以构建最佳判定树。在编制一个将百分制转换成优、良、中、及格、不及格五级分制的程序时，一般学生的成绩呈正态分布，各级别的比例分别为：优秀10%，良好30%，中等40%，及格15%，不及格占5%左右。利用上述Huffman算法构建的判定树如图3所示。按最佳判定树编写程序，可提高比较的效率，显著降低操作时间。

3.3 最佳归并树

4 结论

Huffman树与Huffman编码有着广泛的应用，例如对Huffman编码进行改进可用于软件测试数据进化生成 [3]、SVM 多分类器构造[4]、超光谱图像分层无损压缩[5]、基于稀疏分解的交通图像压缩中[6]等等。因此，正确理解Huffman算法的实质，对有关的研究工作提供有益的启示。

参考文献：

[1] 严蔚敏，吴伟民.数据结构（C语言版）[M]. 北京：清华大学出版社，2010：144-148.

[2] 许卓群，杨冬青，唐世渭，等.数据结构与算法[M].北京：高等教育出版社，2006：126-128.

[3] 巩敦卫，张岩.一种新的多路径覆盖测试数据进化生成方法[J].电子学报，2010（6）：1299-1304.

[4] 谷胜伟.基于赫夫曼树的SVM 多分类器构造方法[J].滁州学院学报，2009，11（3）：41-43.

[5] 张威，田峰.超光谱图像分层无损压缩方案[J].小型微型计算机系统，2011，32（12）：2499-2503.

[6] 王庆， 张葛祥.基于稀疏分解的交通图像压缩[J].公路交通科技，2010，27（6）：112-116.