离散数学之huffman编码

《离散数学之huffman编码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学实践内容实验报告姓名：学号：班级指导老师：哈夫曼编码一、摘要HUFFMAN编码又称哈夫曼编码，是一种可变长编码方式，是由美国数学家DavidHuffman创立的，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。Huffman算法的最根本的原则是：累计的(字符的统计数字*字符的编码长度)为最小，也就是权值(字符的统计数字*字符的编码长度)的和最小。哈夫曼编码在文件压缩中占有举足轻重的作用，如JPEG中就应用了哈夫曼编码。二、选题目的建立在离散数学的基础上，利用哈夫曼编码进

2、行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。综合设计的任务是：设计一个哈夫曼编码/译码系统，使学生掌握哈夫曼编码的特点、存储方法和基本原理，培养学生利用C++语言编写程序以及调试程序的能力，运用数据结构知识解决实际问题的能力，为后续计算机专业课程的学习打下坚实的基础。程序设计是为了锻炼我们的实际动手能力，在一定程度上，又增加了我们的各方面的知识，特别是一些联系实际的课程设计，它的完成需要自己平时积累的大量知识、并且需要勤于思考的能力和无限的激情。本次课设主要是学习程序设计的方法，进行程序设计的基本训练，巩固基础知识，通过思考，和大量的阅读，来构造一个完

3、整的程序。三、简单介绍和初步理解1.哈夫曼编码在介绍哈夫曼编码之前，我们要先了解哈夫曼树（最优二叉树）。假设有n个权值{w1,w2,……wn}，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度长度WPL最小的二叉树称做最优二叉树。步骤如下：1.根据给定的n个权值{W1,W2,……,Wn}构成n棵二叉树的集合F={T1,T2……,Tn}，其中每棵二叉树Ti中只有一个带权为Wi的根节点，其左右子树均为空。2.在F中选取两棵根节点的权值最小的的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根节点的权值之和。3.在F中删

4、除这两棵树，同时将新得到的二叉树加入F中。4.重复2和3，直到F只含一棵树为止。这棵树便是哈夫曼树。开始流程图：输入报文计算频度并令i=0,t=长度i<2*t-1找出根结点频度最小及次小树p1,p2合并成新树T[i]i++结束构建流程图设计一棵Huffman树，然后对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶子的路径上，各分支的赋值分别构成一个二进制串，该二进制串即为对应字符的前缀码，这些前缀码就是哈夫曼编码。一个任意长的哈夫曼序列可以被唯一地翻译为一个字符序列。2.哈夫曼译码哈夫曼编码是一种前缀码（前缀码：在一个编码系统中，任一个编码都不是其他任何编码的前缀

5、），因此，译码就很简单了。译码过程是：从根出发，按字符‘0’或‘1’确定找左孩子或右孩子，直至叶子结点，便可以求得字串相应的字符。四、深入理解和详细分析静态哈夫曼编码方法有一些缺点：一、对于过短的文件进行编码的意义不大，因为光以4BYTES的长度存储哈夫曼树的信息就需1024Bytes的存储空间；二、进行哈夫曼编码，存储编码信息时，若用与通讯网络，就会引起较大的延时；三、对较大的文件进行编码时，频繁的磁盘读写访问会降低数据编码的速度。因此，后来有人提出了一种动态的哈夫曼编码方法。动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得

6、到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。五．编程实现由于代码比较长，这儿就只看一下运行结果；六、一点自己的看法和总结通过本次离散数学的课程设计，我学习了很多在上课没懂的知识，并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识，真正学会一种算法了。当求解一个算法时,不是拿到问题就不加思索地做，而是首先要先对它有个大概的了解，接着再详

7、细地分析每一步怎么做，无论自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。这次的课程设计可以看作是一次理论与实践相结合的桥梁，通过这次的课程设计，我学习到了许多的知识，也认识到了自己目前的不足，那就是缺乏相应的知识与经验，所以在运用和操作方面体现了不足。但是，经过这段时间对相关书籍的阅读和查找，我顺利的完成了设计，我还明白了在编写程序的时候，应该尽量使界面简洁大方，布局统一。变量类型的定义，一定要够用就好，这样程序就可以尽可能的减少对系统资源的占用。在设计时也免不了存在着一些不足，所以在今后的学习中我会努力取得更大