哈夫曼树及其若干应用.pdf
- 文档编号:14654112
- 上传时间:2023-06-25
- 格式:PDF
- 页数:11
- 大小:549.11KB
哈夫曼树及其若干应用.pdf
《哈夫曼树及其若干应用.pdf》由会员分享,可在线阅读,更多相关《哈夫曼树及其若干应用.pdf(11页珍藏版)》请在冰点文库上搜索。
本科毕业论文本科毕业论文题目哈夫曼树及其若干应用学生姓名吴保利专业名称信息与计算科学指导教师李海侠2015年5月21日教学单位数学与信息科学学院学生学号201190024051编号SX2015XX051指导老师:
李海侠作者简介:
吴保利(1990-),男,陕西咸阳人,信息与计算科学专业2011级2班1哈夫曼树及其若干应用哈夫曼树及其若干应用吴保利(宝鸡文理学院数学与信息科学学院,陕西宝鸡721013)摘摘要:
要:
本文在哈夫曼树的构建及存储的基础上,着重介绍了哈夫曼树在通信和最佳判定方法中的应用,将哈夫曼树的思想与现实生活中的许多问题紧密的联系在一起,体现了哈夫曼树的重要意义.关键词:
关键词:
哈夫曼树;哈夫曼编码;最佳判定;人力资源哈夫曼(Huffman)树又称为最优树,是一类带权路径长度最短的二叉树,它是在1952年由DavidA.Huffman提出的,有着广泛的应用,其中最常见的是在哈夫曼编码(HuffmanCoding)中的应用,这种编码方式发表于一种构建极小多余编码的算法一文中,之后多被应用于计算机数据处理和通信中.随着信息时代的发展,人们开始不断地利用哈夫曼树的思想来解决生活中的许多问题.例如文献1-11中许多国内外的学者都对哈夫曼树作了深入的研究.现实生活中的最佳判定问题、人才评估和选拔问题、外部排序中最佳归并树的构建等问题中,都融入了哈夫曼树的思想,很大程度上提高了解决问题的效率.因此,在以后必然会有更多的领域涉及到哈夫曼树的思想,人们对哈夫曼树的探究也将更加深入.1哈夫曼树哈夫曼树1.1哈夫曼树的定义哈夫曼树的定义哈夫曼树也是一类特殊的二叉树,在介绍哈夫曼树的具体定义之前,先引出路径、路径长度和带权路径长度的定义.路径:
树中的一个结点到另外一个结点之间的分支便构成这两个结点之间的路径.在这条路径上的分支数便是这条路径的长度,而一棵树的路径长度则是从每一个结点到根结点的路径长度的总和.路径长度:
从树根第一层开始,若某一结点处于二叉树的第K层,因为从根结点到这个结点路径上的分支条数是1K,所以从根结点到其他各个结点的路径长度()PL也就等于该结点所在的层数K减去1.带权路径长度:
在一棵树中,所有的叶子结点的带权路径长度之和称为该树的带权路径长度.通常记作1nikkWPLl.其中i表示权值,kl表示路径长度.哈夫曼树:
若有n个权值123n,并且把这些权值按照一定的规则来构造一棵共有n个叶子结点的二叉树,且每个叶子结点都有与其相对应的权值i,经过计算得到带权路径长度WPL最小的一棵二叉树便是哈夫曼树或最优二叉树.1.2哈夫曼树的构造哈夫曼树的构造给出哈夫曼树的定义之后,应该如何构造哈夫曼树呢?
下面我们介绍一下哈夫曼最早给出的一个带有一般规律的算法,即哈夫曼算法.给定n个权值集合123n,,且0i,构成n棵二叉树的集合123,nFTTTT,而且每一棵二叉树iT有且仅有一个带权为i的根结点,其2左、右孩子都为空.重复执行以下步骤直到中只含有一棵树为止:
在集合F中分别选取两棵权值最小的二叉树,把这两棵二叉树分别作为左子树和右子树之和.在集合F中删除中的两棵权值最小的二叉树,且把新二叉树的权值加到集合中.最后得到的便就是哈夫曼树了.2哈夫曼树的应用哈夫曼树的应用哈夫曼树在通信、工程及软件开发等问题中都有着广泛的应用,而哈夫曼编码是哈夫曼树最为常见的应用.本文将着重介绍哈夫曼编码在通信中的应用,哈夫曼树在建立最佳判定算法、人力资源工作中以及最佳归并树中的应用.2.1哈夫曼编码哈夫曼编码2.1.1哈夫曼编码的简介哈夫曼编码的简介哈夫曼二叉树在通讯编码中具有极大的实际应用意义,比如构造一组最优前缀码,将文字转化为二进制字符串.二进制编码通常有两种:
一种是等长编码,另一种编码是不等长编码,等长编码的二进制串长度是由电文中不同的字符个数来决定的.如果需要传送的字符只有4种时,则只要有两位字符的串便可以进行分辨.但是,当传送的字符有26种时,则等长编码的长度至少为5.不等长编码中每个字符的编码长度可能是不相等的.不等长编码最大的优点即尽可能地缩短传送电文的字符串的总长度.而每个字符在电文中所出现的次数通常情况下都是不同的.如果将出现频数高的字符尽可能的缩短其编码长度,则总长也随之减少.不过在不等长编码的实用过程中,其中每一个字符的编码都不允许是另一个字符编码的前缀,我们将这种编码称为前缀编码.那么电文总长最短的二进制前缀码应该如何获取呢?
假如每个字符在电文中所出现的次数是i,该字符对应的编码长度为il,电文中一共有n种字符,则电文的总长度为1niiil.对应到二叉树上,如果置i为叶子结点的权,il为从根到叶子的路径长度.那么1niiil刚好是从根结点到叶子结点的路径长度,由此可见,如果将n种字符所出现的频率视为权值,可以得到电文总长度最短的二进制前缀码,设计一棵哈夫曼树时得到的二进制前缀码便称为哈夫曼编码.2.1.2哈夫曼树和哈夫曼编码的存储表示哈夫曼树和哈夫曼编码的存储表示一棵有n个叶子结点的哈夫曼树由于没有度为1的结点,所以在设计出的哈夫曼树中共有21n个结点,存储在长度为21n的一维数组中.应该如何选定结点结构?
由于在构成哈夫曼树之后,为了求编码,在求编码时,先根据权值构建出哈夫曼树,然后从叶子结点开始出发走一条从叶子结点到根结点的路径,而译码则需要从根结点开始出发走一条从根结点到叶子结点的路径.仅仅对结点来说,孩子节点与双亲结点的信息都需要体现出来,存储结构如下:
typedefstructunsignedintweight;unsignedintparent,lchild,rchild;HTNode,*HuffmanTree;3Typedefchar*HuffmanCode;2.1.3哈夫曼编码在通信中的应用哈夫曼编码在通信中的应用在通信中我们通常希望用最少的信息量来表达所要描述的问题,一般都将需传送的文字转换成由二进制的字符组成的字符串.而在传送过程中我们又希望所需要的字符串更短且能正确表达,所以我们一般选择用哈夫曼编码进行传送.例例1已知共有8种字符在某系统在通信系统中出现,其中每个字符的出现概率分别为:
0.05,0.29,0.06,0.09,0.13,0.24,0.03,0.11,试设计哈夫曼编码.解:
解:
其步骤可分为:
假设权值(5,29,6,9,13,24,3,11)W,8n,则15m,按照上述算法可以构造一棵二叉树如图所示.其存储结构HT的初始状态如表1所示.初始化为m个结点,对前n个结点赋权值.由构造最优二叉树的算法策略,建立前n个结点与其双亲结点的对应关系.其哈夫曼编码HC实现结果如图2所示.由建立的数据结构,从叶子结点向上遍历,并记录每个字符对应的编码串,将其存放在HT中.图图11建立哈夫曼树建立哈夫曼树3561311242994表表2HT2HT的最终状态的最终状态weightparentlchildrchild159002291400361000491100513120062413007390081111009810101014125911201348122714510134415116145615212151000131411111021031110400051106017111118001表表1HT1HT的初始状态的初始状态weightparentlchildrchild150002290003600049000513000624000730008110009-00010-00011-00012-00013-00014-00015-000图图22各字符的哈夫曼编码各字符的哈夫曼编码HC5通过上述步骤之后得到的8种字符的编码(图2),便使得每一种字符在传送的过程中能够高效率的完成,这就给发报人员及译码人员带来很大的方便.2.2哈夫曼树在建立最佳判定算法中的应用哈夫曼树在建立最佳判定算法中的应用处理判定问题时,经常会出现满足中间条件较多而满足两头条件较少的情况,就像我们在统计学生的成绩时,优秀生和不及格的学生人数都与中等学生的人数差距较大.如果我们在类似的判定算法中充分的利用哈夫曼树的思想,那么程序的执行速度将会被大大提高.其基本思想也是利用哈夫曼算法将各个等级的占有比例数作为权值,建立哈夫曼树,便可得到最佳判定顺序,提高判定效率.例例22在某学院职工合算奖金的系统中,根据学院奖金发放的有关规定,行政人员按其级别进行发放,其级别包含:
局级、处级、副处级、科级、副科级、一级科员、二级科员、三级科员;教师也按其级别进行发放,教师的级别有:
初级、中级和高级.而且每个等级内又可分为A、B、C三个级别.该学院目前行政人员的分布如表3所示,试建立合适的判定算法,分别确定出每个行政人员的职务和各个教师的级别.表表33某学院目前行政人员的分布表某学院目前行政人员的分布表级别局级处级副处级科级副科级一级科员二级科员三级科员比例数0.010.020.10.130.090.150.40.1解:
解:
按照普通的方法确定行政人员职务的算法如下:
if(grade=“jj”)elseif(grade=“cj”)elseif(grade=“fcj”)elseif(grade=“kj”)elseif(grade=“fkj”)elseif(grade=“1ky”)elseif(grade=“2ky”)elseif(grade=“3ky”)由上题中给出的分布规律可计算得平均每人要判断5.7次,在70%以上的人要判断4次以上才能得到最终结果.如果利用哈夫曼树确定判定算法的话,我们可以以各级别所占的比例数1、2、10、13、9、15、40、10为权,从而构造一棵有8个叶子结点的哈夫曼树,如图3所示.按照哈夫曼树结构确定判定顺序如下:
if(grade=“2ky”)elseif(grade=“1ky”)elseif(grade=“kj”)elseif(grade=“fcj”)elseif(grade=“3ky”)elseif(grade=“fkj”)elseif(grade=“cj”)elseif(grade=“jj”)按照上述算法平均每人只需判断2.75次,也只有22%的人需要判断4次以上.这与常规的顺序相比减少判定次数在50%以上,如果按照1000人计算,仅这一项减少判断次数将近3000次.同样,若每个级别的A、B、C三等的分布分别是10%、8%和5%,则常规的判定顺序为:
6if(grade=A)elseif(grade=B)elseif(grade=C)如果按照这类判定顺序,那么将有95%的人需要判定2次.若按照下列哈夫曼树的判定顺序:
if(grade=B)elseif(grade=A)elseif(grade=C)则大约有85%以上的人在判定时只需要1次.通过上述两种方法的比对,我们能够清楚的看出,在类似的判定问题中,如果能够充分的利用好哈夫曼树的思想,将会在很大程度上提高问题的解决效率.2.3哈夫曼树在人力资源工作中的应用哈夫曼树在人力资源工作中的应用在日常处理人力资源相关的工作中,尤其是在进行人才的选拔时,经常会出现这样的需求:
从众多的候选者之中尽快的选拔中最能符合需求的人才;快速的从少数候选者之中选拔出综合素质较高的人才;快速的从众多的候选者之中尽可能挑选出综合素质较高的人才.在解决上述这些看似相互矛盾的问题时多数情况下是依靠管理者的经验作出裁决,而很少会采用定量的方法解决.但是在某些情况下如果能够利用哈夫曼树的思想解决此类问题,也是一种非常有用的手段.在解决这类问题时我们先假设:
所需要的外部资源在有需求时都能及时足额提供;每个选拔环节的次序都没有严格的限定,而且对于每一个候选者所需要的工作总量在同一个工作环节中都大致相等;只要无重复的完成所有工作步jjfkj3kyfcjkj1ky2ky图图33哈夫曼树哈夫曼树7骤就能得到所需要的选拔结果;有一定的历史数据或者工作经验或者理论依据能够得以利用(确定权数);工作总量跟工作成效整体呈现正相关;对于有些将要被淘汰的对象不再需要进行下一步的工作.在上述条件下,我们可以将人才选拔工作的相关要求大致归结为两条:
所需工作总量达到最少;所需工作成效达到最好.这两条明显是相互矛盾的,因此只能做到在满足其他条件的情况下尽可能的侧重其另一个方面,从而求得最优的解,或者可以降低两个方面要求的的最优程度从而求得满意的解.例例36若某次人才选拔工作中共需要经历5个工作环节,且该选拔工作满足上述的假定条件,根据选拔要求给出每个环节淘汰的候选者的比例数如表4所示.表表44每个环节淘汰候选者的比例数每个环节淘汰候选者的比例数环节ABCDE比例数0.050.150.400.300.10假设有10000名候选者作为本次选拔工的选拔对象,他们在经历A、B、C、D、E五个环节的选拔后,最终留下3052(100000.950.850.600.700.90)人.求出较为合适的淘汰环节次序.解:
解:
我们先按照传统的依次经历模式进行计算,在整个选拔过程中所需要的工作总量(以人次为工作总量的计量单位,下同)为:
100001000010.05()1000010.0510.151000010.0510.1510.40100001+()()+()()()+(0.0510.1510.4010.30100009500807548453391.5)()()()=35811.5(人次)我们用同样的方法也可以计算出在上述的假定条件下所需的工作总量最少、最多和平均次数为:
所需要的工作总量最少可达到:
26983(人次)所需要的工作总量最多可达到:
40404.75(人次)在平均情况下,即所需要的工作总量与工作环节的先后次序无关的情况下,此时要求每个环节在淘汰时比例应该相等,我们设其淘汰比例都为:
1(10.05)(10.15)(10.40)(10.30)(10.10)0.213,在这种平均情况下所需要的工作总量为:
32072(人次).将上述几种情况作以分析可知:
传统的工作模式跟最优的工作模式之间伴随着工作环节的增加,其所需要的工作总量的差别也会越来越大,在最极端的情况下:
后面环节中人员的淘汰比率高于前面环节中的淘汰比率(此时工作量最大);后面环节中人员的淘汰比率低于前面环节中的淘汰比率(此时工作量最小).由哈夫曼树的思想,我们可以将人才选拔工作中需要满足的三种条件视为哈夫曼树的单分支序列树进行构造.具体方法为:
将所需要的经历环节数表示为树的高度,将具体所经历的某个环节用具体层次上的分支结点作为代表,在树的结点处不需要再标明具体的权值.按照这类方法构造的特殊类型的哈夫曼树,同一层上的结点数都只有1个,即蜕化为度是1的左斜树,不过依然满足最优的选拔方案(工作总量最小或者工作成效最好).这类特殊类型的哈夫曼树的构造过程可分为如下步骤:
确定出工作环节以及每一环节中的淘汰比率(由历史数据或者理论依据或者工作经验进行确定).确定具体的工作要求(工作成效最好或者总工作量最小),并且按照具体8要求确定出是对工作环节按权(淘汰率)进行升序还是降序排列.如果要求工作成效最好时就采用升序,如果要求总工作量最小时则采用用降序.把工作环节名称根据排列顺序自上而下地填进对应的度为1的蜕化后的左倾斜树的结点中.沿用前面的数据我们可以将满足选拔人才的三个要求按照上述方法构造一个特殊工作环节序列分别是:
要求工作总量最小的情况下为:
CDBEA要求工作成效最好的情况下为:
AEBDC在两者兼顾的情况下:
CDAEB或者CDBAE等(根据工作总量约束确定).由上例可以看出,在安排淘汰环节时,若顺序不同则总体判定次数就可能不同,选择合适的算法可以减少许多任务量.但在具体的实践中,还需要考虑问题的可行性,综合各种因素来决定各环节的顺序.2.4哈夫曼树在最佳归并树中的应用哈夫曼树在最佳归并树中的应用外部排序由两部分构成.第一阶段先产生初始归并段.由可用内存量的大小,可以把外存上含有n个记录的文件分成m个长度分别为(1,2,m)ili的段,将生成的这些段依次读入内存,再利用内排序的方法对其进行排序,之后将排序后得到的有序段再一次写入外存.第二阶段进行归并.对第一阶段产生的初始归并段由小到大逐趟进行归并,直到产生整个有序文件.然而,在整个排序过程中,归并效率是影响整个排序效率的关键.那么要使得归并效率最佳,则应使初始归并段的长度il互不相等,m个初始归并段归并过程应该是带权路径长度之和最小的归并树所描述的归并过程.也就是求m个结点的多叉哈夫曼树的过程.例例4设由置换选择得到9个初始归并段,其长度(即记录数)依次是:
9,30,12,18,3,17,2,6,24.求出3路平衡归并的最佳归并树.解:
解:
作3路平衡归并,其归并树如图4所示.若每个记录占一个物理块,那么两趟归并所需对外存进行的读/写次数为:
4842224621731812309)(如果将初始归并段的长度看成是归并树中叶子结点的权,则此三叉树的带权路径长度的两倍刚好为484.很显然,归并的方案直接影响所得到的归并树和树的带权路径长度.因此,如果能将长度不等的个初始归并段,以其段长作为权值构造一棵哈夫曼树作为归并树,这样在进行外部归并时便会使得对外存进行的读/写次数达到最少.对题中9个初始归并段可以构造一棵如图5所示的归并树,如果按照此树进行归并,对外存的读/写次数仅为:
(30192122172182242233363)2446明显比前边的归并方案要简单得多,这棵归并树便是3路平衡归并的最佳归并树.22图图4343-路平衡归并的归并路平衡归并的归并931131269由上例我们可以很清楚的看到,利用哈夫曼树构造的最佳归并树使得在进行归并操作时大大减少了读/写次数,从而提高了外部排序的效率.总结总结:
在信息技术飞速发展的今天,信息技术已经变得越来越重要,我们时时刻刻都在跟数据交流,而在信息处理中怎样使效率最高已经成为信息时代最核心的问题.哈夫曼树是提高效率的一种有效方法,运用好哈夫曼树的思想能解决现实中的很多问题,像本文中所介绍的哈夫曼编码,其在通信中的应用尤为重要,使得每个字符都能够简单、准确、快速的得到传递.哈夫曼树在人力资源工作中和在最佳归并树中的应用也是对其思想的进一步升华,大大提高了问题的解决效率.目前,哈夫曼树已深入更多、更广的领域,给人们带来许多便利.因此,对哈夫曼树的研究以后也将更加深入.致谢:
本文在写作过程中得到李海侠老师的指导.参考文献参考文献:
1徐莹.赫夫曼树遍历算法的优化J.安徽电子信息职业技术学院学报,2009,25(5):
7235-7237.2孙尧,徐欣,陈知千.赫夫曼算法效率的优化J.东华大学计算机科学与技术学院学报,2010,9(7):
60-62.3徐凤生,钱爱增,李海军等.赫夫曼编码的求解算法J.德州学院计算机系学报,2007,23
(2):
48-50.4陈桂英,王亚鹏.哈夫曼树及其应用J.河南理工大学万方科技学院学报,2014,12
(1):
256-257.5黄伟焕.赫夫曼算法在分类优化应用中的缺陷及修正J.温州职业技术学院学报,2002,4
(2):
31-32.6冯运义,雷蕾.赫夫曼算法在人力资源工作中的应用研究J.全国贸易经济类核心期刊,2006,462:
238-239.7冯玉山.利用赫夫曼树建立最佳判定算法J.北京工业职业技术学院学报,2002,2
(1):
30-31.8严蔚敏,吴伟民.数据结构(C语言描述)M.北京:
清华大学出版社,2013.9刘奇超.赫夫曼编码及其应用J.郑州市电子信息工程学校学报,2008,8:
97-98.10张小红.赫夫曼编译码系统的设计与实现J.电子科技期刊,2011,24
(2):
90-91.11张荣梅.哈夫曼算法及其应用研究J.河北经贸大学信息技术学院学报,13(9):
3062-3064.图图5353-路平衡归并的最佳归并树路平衡归并的最佳归并树6224181712930310HuffmantreeandsomeapplicationsWUBao-li(InstituteofMathematicsandInformationScience,BaojiUniversityofArtsandSciences,Baoji721013,Shaanxi,China)Abstract:
BasedontheconsructionandstrangeofHuffmantree,thispaperdealswiththeapplicationsofHuffmantreeincommunicationsandthebestjudgement.Theidealof13Huffmantreeisclosedlylinkedwithalotofproblemsinreal-lifeandtheimportantsignificanceofHuffmantreeisembedded.Keywords:
Huffmantree;Huffmancoding;Thebestdecision;Thehumanresources
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈夫曼树 及其 若干 应用