1、V毕 业 论 文（设 计）题目（中文）哈夫曼树的应用及算法实现 （英文）On Applications and Implementation of the Huffman trees 专业 信息与计算科学 VI摘要随着信息科技的不断发展、移动终端的推陈出新，信息数据的传递无处不在。而在设备容量以及信息传输速率的限制之下，数据的压缩及安全成为了时下的一大课题。David A. Huffman于1952年提出了哈夫曼编码，如今该编码已被广泛用于在文本，图像和视频压缩之中。作为一种可变长度编码技术，哈夫曼编码的优点是流程简易和有效压缩比，它在处理数据压缩的各种应用中已显然是最领先的方法之一。除此之外
2、，哈夫曼树作为一种数据结构，在其他领域也有着极大的用武之地。本文首先对哈夫曼树的概念、结构与性质作一个简要陈述，使我们更好地理解其主要原理及运作模式。随后简述哈夫曼树在数据压缩、数据安全、信息的分类判定等问题中的用处，将其在各领域中的发展与改进作一个归纳，以达到对哈夫曼树更进一步的了解。其次，将基本的哈夫曼算法通过C+代码作一个简单的实现，深入发掘这种数据结构的特点。最后，总结哈夫曼树的优越之处及不足之处，展望其未来的发展方向。关键词：哈夫曼树；哈夫曼编码；数据压缩；算法VIIAbstractWith the development of information technology, mor
3、e and more devices are invented. Data transmission can be seen anywhere. However, Because of the restriction of device capacity and the transmission rate, Compression and data security has become a major issue. The Huffman coding has been widely used in text, image and video compression, Since it wa
4、s proposed by Huffman in 1952. As a variable-length coding technique, it has been proved to be one of the most advanced methods being used in applications dealing with data compression. In addition, as a data structure, the Huffman tree also has a great usefulness in other areas. Firstly, we make a
5、brief statement of the concept of the Huffman tree, its structure and properties, with its main principle and mode of operation. Then, in order to achieve a better understanding of the Huffman tree, in the applications of the Huffman tree, such as data compression, data security and information clas
6、sification are summarized. After that, we make a simple implementation of the basic Huffman algorithm with C+. Finally, we summarize the advantages and shortcomings of the Huffman tree, and analyze its future development.Keywords: Huffman tree; Huffman coding; data compression; algorithm目 录上海师范大学本科毕
7、业论文（设计）诚信声明I上海师范大学本科毕业论文（设计）选题登记表II上海师范大学本科毕业论文（设计）指导记录表中文摘要及关键词 英文摘要及关键词 第一章 绪论 11.1 本课题的研究意义11.2 国内外发展简况 11.3 本文主要内容 2第二章 哈夫曼树 32.1 树32.2 哈夫曼树3第三章 哈夫曼树的应用 53.1 数据压缩 53.2 分类判定问题 83.3 其他应用10第四章 哈夫曼编码改进算法及其基本实现124.1 改进的哈夫曼编码算法124.2 哈夫曼编码程序基本实现144.3 结果演示 15第五章 总结16参考文献 18附录 201第一章 绪论1.1 本课题的研究意义本课题主要针
8、对哈夫曼树的特点，围绕其在各领域的应用作一个简略的汇总，并对基本算法进行实现。当今世界是个信息大爆炸的时代，随着 3G、4G 信号的逐渐完善，通讯科技的飞速发展，人们随时随地都能通过网络进行信息的交互。微信、微博、邮箱等程序的出现，几乎改变了现代人的相处模式，因而消息的传输无时无刻不在进行着，随之而来的许多问题成了现代算法研究的课题之一。信息的大小直接影响、限制着传输效率和各个终端的储存容量，信息容量的压缩、加密等成了刻不容缓的话题。而哈夫曼编作为一种无损变长编码，恰好能有效地进行数据压缩，提高通信的效率。除此之外，哈夫曼树还在各个领域中有着相当广泛的应用，例如分类及确定多重判定程序问题中的应
9、用；实现树的图形化表示；文件加密等。而传统的哈夫曼算法虽然优点多多，但储存空间、运行效率等还是有着较大的改进空间。随着科技时代的进步，各类应用的要求不断提升，哈夫曼算法明显存在着一定劣势，因而对传统的哈夫曼算法作进一步研究和改进对于实际应用和理论都有着重要意义。1.2 国内外发展简况随着信息技术的逐年提升，传输数据的容量自然也呈几何倍数上升。在如此大环境下，哈夫曼编码占用的储存空间过大、编码解码效率不高等缺点逐一暴露。因而众学者在提升算法性能、改进算法效率方面始终进行着研究。哈夫曼算法在不同的改进之中，也不断地呈现出更为多样化的变革。计算机技术在日新月异的时代中不断发展，数据结构早已不再局限于
10、单一的计算、排序、数值等问题中。二叉树作为基本的数据结构之一，在越来越多的实际应用问题中大展拳脚。作为二叉树结构的一种特殊应用，哈夫曼树是哈2夫曼早在上世纪 50 年代就提出的数据结构，它在数据压缩方面有着极大的用武之地。因哈夫曼树的带权路径最短、权值大的结点离根结点较近，也被称作最优二叉树。这种特性使得哈夫曼编码能够将电报文字的长度进行相当程度的压缩。随着时代的发展，通过对哈夫曼树的改进，其压缩性能也逐渐提高。到了今时今日，仍旧有许多人在对其压缩数据的性能这一课题孜孜不倦地研究着。例如Sharma M.发表于 2010 年的Compression using Huffman coding 2
11、2、卢冰，刘兴海在 2013 年发表在期刊中的论文利用改进的哈夫曼编码实现文件的压缩与解压 2等。与此同时，其他领域也常常在哈夫曼树的改进之下不断发展。由何红洲，周明天于 2013 年发表的一种基于哈夫曼判定的蛋白质分类方法 12可见，虽然研究对象与哈夫曼树并不相关，却可利用它的结构特点，在一定程度上改善其他算法的效率，从而达到事半功倍的效果。 A novel steganography method for image based on Huffman Encoding 16、 Incomplete cryptography method using invariant Huffman co
12、de length to digital rights management 17等文章也代表了近年来哈夫曼树在加密、隐藏信息方面的趋势。显而易见，对哈夫曼树的应用研究与改进将会在未来不断持续。1.3 本文主要内容本文主要内容为哈夫曼树的各类应用及算法实现。本文第二章主要将对树和哈夫曼树的概念、性质等作总结，并介绍哈夫曼树的基本构造。而在第三章中，我们主要介绍哈夫曼树在各个领域中的不同应用。首先是哈夫曼树在数据压缩中的用法及针对其存储空间过大等缺点的简单改进。在分类判定问题中，由于判定次数过多而导致的算法效率低下，亦可由哈夫曼算法解决。而对于哈夫曼编码在加密、隐蔽信息、图形化表示等算法中的用处
13、，我们也将作详尽概述。随后的第四章中，我们介绍了一种自适应的哈夫曼编码算法，可针对其运3行效率作有效改进。最后，我们通过 C+完成了哈夫曼算法的基本实现，详细写出算法的实现过程，并将代码放入附录中以作参考。第二章 哈夫曼树2.1 树2.1.1 树的定义树是 n 个结点的有限集合。树有 n 个结点，每个结点的子树数量称为结点的度，度为 0 的结点称为叶子结点。结点子树的根结点称为该结点的孩子结点，而该结点则被称为双亲结点。结点的层即是由根作为第一层，根的孩子是第二层，依次类推，若有结点在第 n 层，其子树的根就在 n+1 层。树的最大层次数称为深度。若树中各结点从左至右不能互换次序，则称为有序树
14、，同时，若可以互换顺序则称为无序树。N 个树的集合称为森林。二叉树是树形结构的一种特例，这种结构的树，每个结点最多两棵子树，分别称为左子树和右子树，其顺序无法任意更换，是有序树。2.1.2 树的性质对于任意的一棵非空树，有以下特点：每棵树有且只有一个根结点，称为Root。当 n1 时，其余的结点可划分为有限个互不相交的集合，每个集合的本身又是一棵树，称为根的子树。对任意一棵二叉树，若其叶子结点数为 n0，度为 2 的结点数为 n2，那么n2+1=n0。设 i 为叶子结点，i 的左子树结点为 2*i,若 2*in，那么 i 没有左子树；i 的右子树结点为 2*i+1，若 2*i+1n，那么 i
15、没有右子树。 142.2 哈夫曼树2.2.1 哈夫曼树的概念路径：在任意一棵树中，从一个结点往下走，可以达到的孩子结点之间形成的通路。路径长度：通路中经过的分支的数量。结点的权值：对树中不同的结点给出一个有相对含义的数值。带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为 WPL。假如有 n 个权值，分别作为 n 个结点,并以此构造一棵含有 n 个最终叶子结点的二叉树，使得每个带有权值的叶子结点 WPL 最小，那么这棵树就被人们称作最优二叉树。为了解决这个问题，人们提出了许多方法。其中，哈夫曼于1952
16、年提出的一种算法能够顺利解决这类问题，因而该算法被称为哈夫曼算法。而衍生出的二叉树结构，也被叫作哈夫曼树、最优二叉树。 12.2.2 哈夫曼树构造哈夫曼树的简单构造如下所示 8：1.假设 n 个带有权值N1,N2,Nn(其中 N1N2Nn)的结点分别为一棵左子树、右子树为空的树，树的集合为 TT1，T2，Tn。如图 1 所示。2.从集合 T 中选取权值最小的两棵树 T1、T2，将 T1 作为新树 T的左子树，将 T2 作为新树 T的右子树，T的根结点权值为 N1=N1+N2。如图 2 所示。3. 将 T1、T2 从 T 中删除，并将集合 T 变为T ，T3，Tn，对应权值为N1,N3，Nn。如图 3 所示。4.重复 2 和 3 步，使得 T 中只含一棵树 T，构造完成。如图 4 所示。5图 1 图 2图 3 图 4第三章 哈夫曼树的应用3.1 数据压缩随着安卓、ios 等系统在移动终端的普及，手机、电视机顶盒、平板电脑等对信息存储的需求也不断攀升。但储存空间总是有限的，开源不成，便需要在节流上做文章，由此数据压缩也显得格外重要。压缩根据是否能够完全恢复数据而分为有损压缩和无损压缩。有损压缩通常用于视频、音乐、图片等。而对于不能缺失的信息，例如文本文件，则需要通过无损压缩来实现。哈夫曼编码、Shannon-Fano 编码、Run-length 编码等是
