还剩13页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
福建农林大学计算机与信息学院数据结构课程设计设计哈夫曼编译码器姓名韦邦权专业2013级计算机科学与技术学号13224624班级13052316完成日期
2013.
12.28哈夫曼编译码器
一、需求分析在当今信息爆炸时代,如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视,哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术哈夫曼编码是一种编码方式,以哈夫曼树—即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩哈夫曼编码使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码这张编码表的特殊之处在于,它是根据每一个源字符出现的估算概率而建立起来的(出现概率高的字符使用较短的编码,反之出现概率低的则使用较长的编码,这便使编码之后的字符串的平均期望长度降低,从而达到无损压缩数据的目的)哈夫曼编码的应用很广泛,利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码树中从根到每个叶子都有一条路径,对路径上的各分支约定指向左子树的分支表示“0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码,这就是哈夫曼编码哈夫曼译码输入字符串可以把它编译成二进制代码,输入二进制代码时可以编译成字符串
二、设计要求对输入的一串电文字符实现哈夫曼编码,再对哈夫曼编码生成的代码串进行译码,输出电文字符串通常我们把数据压缩的过程称为编码,解压缩的过程称为解码电报通信是传递文字的二进制码形式的字符串但在信息传递时,总希望总长度能尽可能短,即采用最短码假设每种字符在电文中出现的次数为Wi,编码长度为Li,电文中有n种字符,则电文编码总长度为∑WiLi若将此对应到二叉树上,Wi为叶结点的权,Li为根结点到叶结点的路径长度那么,∑WiLi恰好为二叉树上带权路径长度因此,设计电文总长最短的二进制前缀编码,就是以n种字符出现的频率作权,构造一棵哈夫曼树,此构造过程称为哈夫曼编码设计实现的功能1哈夫曼树的建立;2哈夫曼编码的生成;3编码文件的译码
三、概要设计哈夫曼编\译码器的主要功能是先建立哈夫曼树,然后利用建好的哈夫曼树生成哈夫曼编码后进行译码在数据通信中,经常需要将传送的文...。