课程设计(论文)哈夫曼编码及其应用
16页1、图论论文论文题目 学生姓名 专业班级 学 号 邮 箱 2015年 12月 20日目 录摘要1第一章 哈夫曼树21.1 哈夫曼树的基本概念2第二章 哈夫曼算法构造32.1 哈夫曼树的构造算法32.2 举例说明其构造过程3第三章 哈夫曼树的应用53.1 用于通信编码5第四章 运行结果6第五章 总结7参考文献:7附录8哈夫曼编码及其应用摘要在现代社会,通信的发展,使得现代社会更加丰富多彩,我们可以随时随地在任何 地方了解到世界各地的信息,而这又必须依赖信息的传递。在信息化高度发达的当今社会,我们必须对信息的传递有着较高的要求,我们希望信息在传递的过程中,能够保持节省性和保密性和无损性,而著名的霍夫曼编码就能够达到这样的要求。因此研究霍夫曼编码对信息的压缩和解压就时相当有必要的,我们用C+对霍夫曼编码给出简单的算法以实现对文件的压缩和解压。哈夫曼树是由哈夫曼于1951年所创立并改进的,他本人也根据哈夫曼树提出了相应的编码.由于哈夫曼树是具有最小加权路径长度的二叉树,故哈夫曼编码能产生较短的码文.基于这个优势,在信息化高度发达的当今社会,对信息的传递也有着较高要求的我们,希望信息在传递过程中,能
2、够保持节省性和保密性,哈夫曼编码则很好的满足了这方面的要求,因而对其的研究是相当有必要的.关键字:哈夫曼树,二叉树,信息压缩编码第一章 哈夫曼树1.1 哈夫曼树的基本概念首先要了解关于树的一些概念。定义1.1 在一棵树中,从一个结点往下可以达到的孩子或子孙结点之间的通路,称为路径.定义1.2 若将树中结点都赋给一个具有某种含义的数值,则这个数值称为该结点的权.定义1.3 由根结点到所有叶结点的路径长度之和称为二叉树的路径长度.定义1.4 从根结点到叶结点的路径长度与相应结点权值之积的和叫做二叉树的带权路径长度.定义1.5 最优二叉树,也称哈夫曼树,实质是对一组带有确定权值的叶结点,构造的具有最小带权路径长度的二叉树.如果二叉树中的叶结点都具有一定的权值,则可将这一概念推广,设二叉树有个带权值的叶结点,那么,二叉树的带权路径长度应记为:,其中为第个叶结点的权值;为第个叶结点的路径长度.如下图: 图在图中,即为根结点,而则为叶结点,若的权值分别为则二叉树路径长度为2,二叉树的带权路径长度为7,即.例 下面我们结合实例来说明哈夫曼树.如图1.2.2 按照的计算方法,经过计算比较后,我们发现,
3、图的值最小,它即为哈夫曼树.由此可见,由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路径长度.那么如何找到带权路径长度最小的二叉树呢?根据哈夫曼树的定义,一棵二叉树要使其值最小,必须使权值越大的叶结点越靠近根结点,而权值越小的叶结点越远离根结点,这样计算树的带权路径长度时,自然树会具有最小的带权路径长度,这是生成算法的一种基本思想.第二章 哈夫曼算法构造哈夫曼树,实质是对一组带有确定权值的叶结点,构造的具有最小带权路径长度的二叉树.尽管哈夫曼树可以通过比较后得出,可是在运算过程中往往会出现一些问题,使其实现起来并不容易,因而我们可以应用编程来有效地解决这个问题.2.1 哈夫曼树的构造算法为了构造权值为的哈夫曼树,哈夫曼提出了一种构造算法,现将其陈述如下:步骤1 根据题目给定的个权值构造有下列棵二叉树的集合 ,其中每棵二叉树中只有一个带权为的根结点,其 左右树均为空;步骤2 在中选取两棵根结点的权值最小的树作为左、右子树构造一棵新的二 叉树,且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之 和;步骤3 在中删除这两棵树,同时将新得到的二叉树加入中;步骤4 重复步
4、骤2和步骤3,直到只含有一棵树为止,这棵树便是哈夫曼树.2.2 举例说明其构造过程假设叶结点权值集合为的哈夫曼树的构造第一步 我们根据给定的4个权值来构造4棵二叉树的集合.第二步 在找出权值中最小的两个作为新二叉树的左右子树,且置新的二叉树根结点权值是其左右结点权值之和.第三步 将次小的树与新生成的树再作为左右子树生成权值为6的新树;第四步 再次将权值为4的树在同上一个权值为6的树再次生成新树即可.从以上过程可以计算出这棵二叉树的带权路径长度为19.第三章 哈夫曼树的应用3.1 用于通信编码在电报通讯中,电文是以二进制的序列传送的.在发送端需要将电文中的字符序列转换成二进制的序列,而在接收端又需要把接收的序列转换成对应的字符序列.例如给出一段电文: 电文中只使用了这四种字符,各字符出现的频度分别是,若进行等长编码,需要两位二进制位,可依次编码为 则所发电文是: 采用不等长编码要避免译码的二义性.例如,字符的编码是字符的编码的前缀部分.这样对于代码串,既是的代码,也是和的代码,因此,这样的编码不能保证译码的唯一性.所以,若对某一字符集进行不等长编码,可用该字符集中的每个字符作为叶子结点生
《课程设计(论文)哈夫曼编码及其应用》由会员ni****g分享,可在线阅读,更多相关《课程设计(论文)哈夫曼编码及其应用》请在金锄头文库上搜索。
安全生产责任制
公司人力资源创策略规划
huagongyuanli课程设计报告
两只小猪帮小兔盖房子看图写话
摄影入门的所有基础知识
东北工业基地的困境及出路
贫困生助学金申请书表
2023年河南省安阳市林州市横水镇东赵村社区工作人员考试模拟试题及答案
东北大学22春《应用统计》补考试题库答案参考31
试谈办公室公务活动礼仪工作规范
《 对韵歌》 教学设计
中考数学知识点总结
北师大版五年级数学《比较图形的面积》教学反思
物业管理全套应急预案(齐全)
胶砂试模检定规程
物业管理师《物业管理实务》考试内容及考试题附答案第32期
门窗安装项目环境影响评价评价报告
2022年安培中心安全生产责任制
买菜评课稿
生产誓师动员大会发言稿范本(2篇)
2023-05-13 9页
2023-04-16 6页
2023-03-24 24页
2023-12-06 19页
2022-11-20 10页
2023-07-20 28页
2023-09-02 19页
2023-08-09 8页
2022-08-26 9页
2022-10-19 9页