《基于哈弗曼的编码实现论文》由会员分享，可在线阅读，更多相关《基于哈弗曼的编码实现论文（14页珍藏版）》请在金锄头文库上搜索。
1、学 年 论 文题目： 基于哈弗曼的编码实现 学 生： 学 号： 院 （系）： 专 业： 指导教师： 年 月 日 2基于哈弗曼的编码实现摘要：Huffman编码是一种应用广泛的可变长编码方式，是二叉树的一种特殊转化形式。利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。哈弗曼树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。哈弗曼编码的原理是：将使用次数多的代码转换成长度较短的编码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。数据压缩
2、的过程称为编码，解压缩的过程称为译码。哈夫曼编码是一种根据字母的使用频率而设计的变长码，能提高信息的传输效率,至今仍有广泛的应用。关键词：Huffman编码，数据压缩，编码，译码，二进制码Based on the Huffmans codedABSTRACT:Huffman coding is a widely used way of variable length coding, is a kind of special transformation form of binary tree. Use Huffman tree seeks to communicate the binary c
3、oding as Huffman encoding. Harvard man in the tree from the root to each leaf has a path, the path branches agreed: 0 refers to the branch of the left subtree said, pointing to the right subtree of branch said 1 code, take each path of 0 or 1 on the sequence as and the corresponding character coding
4、, that is the Huffman encoding. Harvard, coding principle is: will use more code conversion grow shorter encoding, and use fewer can use longer encoding, and keep only solvability of coding. Process known as encoding data compression, decompression process known as decoding. Huffman encoding is a de
5、signed according to the use of letters frequency variable length code, can improve the efficiency of information transmission, there are still widely used. KEYWORDS:Huffman coding, data compression, coding, decoding, binary code 1哈弗曼原理通常我们把数据压缩的过程称为编码，解压缩的过程称为译码。本文根据Huffman编码原理，在详细设计中，根据权值和最小的根本原则，输
6、入要编码的字符集及其它的权值，再根据节点Node类，建立哈夫曼树，并进行编码，最后输出哈夫曼编码。在完成Huffman编码后，利用其构建的哈夫曼编码树来进行译码。与编码过程不同，译码过程中，将用户输入的二进制代码串依次与字符集中的每个字符的编码进行比较，译出一个字符后，循环比较下一个字符的编码，直到所有二进制码全部译出为止。哈夫曼编码方法的具体过程是：首先把信源的各个输出符号序列按概率递降的顺序排列起来，求其中概率最小的两个序列的概率之和，并把这个概率之和看做是一个符号序列的概率，再与其他序列依概率递降顺序排列(参与求概率之和的这两个序列不再出现在新的排列之中)。然后，对参与概率求和的两个符号
7、序列分别赋予二进制数字0和1。继续这样的操作，直到剩下一个以1为概率的符号序列。最后，按照与编码过程相反的顺序读出各个符号序列所对应的二进制数字组，就可分别得到各该符号序列的码字。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N个权Wi(i=1,2,.n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,.n)。可以证明哈夫曼树的WPL是最小的。2哈
8、弗曼编码步骤一、对给定的n个权值W1,W2,W3,.,Wi,.,Wn构成n棵二叉树的初始集。F=T1,T2,T3,.,Ti,.,Tn，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。）二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。四、重复二和三两步，直到集合F中只有一棵二叉树为止。简易的理解就是，假如有A,B,C,D,E五个字符，出现的频率（即权值）分别为5,4,3
9、,2,1,那么第一步先取两个最小权值作为左右子树构造一个新树，即取1，2构成新树，其结点为1+2=3，如图：虚线为新生成的结点，第二步再把新生成的权值为3的结点放到剩下的集合中，所以集合变成5,4,3,3，再根据第二步，取最小的两个权值构成新树，如图：再依次建立哈夫曼树，如下图：其中各个权值替换对应的字符即为下图：所以各字符对应的编码为：A-11,B-10,C-00,D-011,E-010霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合。3 哈弗曼编程运行4 总结通过系统性的学习让我了解了霍夫曼（哈弗曼）编码的历史、原理和编码的步骤还有它的实际应用和不足之处、也
10、使我对它有了重新的认识。通过对论文的不断更改我反思了很多，也学到了很多。在完成论文期间，我在编码，尤其是译码和解码的处理方式之处还是存在一些问题。另外，在处理输入方面也稍有难度，在输入字符序列的同时，应该统计出字符的种类以及各个字符的权值，本次论文中采用了结构体数组来存储这些内容。通过本次学习，我也认识到了自己还有很多不足，还有很多需要进一步学习的地方，在接下来的学习中我会花更多时间来认真加深知识的理解与运用。参考文献 1 耿国华编著.数据结构用C语言描述.高等教育出版社附录：源程序：#define _CRT_SECURE_NO_WARNINGS#include #include #inclu
11、de #include #include #define INIT_CAPCITY 100struct HTNode /结点信息char c;/数据项int parent;/双亲结点的位置int lchild;int rchild;int weight;/权值;struct ChNode /定义一个结构体，用来存放字符串的各个字符和权值信息char c;int weight;struct HCodechar codeINIT_CAPCITY;/存放当前结点的哈夫曼编码int m_start;/开始存放的位置;/创建哈夫曼树void CreateHT(HTNode ht,int n,ChNode
12、 s)int i,k,lnode,rnode;/lnode为最小权值结点的位置，rnode为次小权值结点的位置int min1,min2;/min1为最小值，min2为次小值for (i=0;i2*n-1;i+)/初始化hti.parent=-1;hti.lchild=-1;hti.rchild=-1;hti.weight=0;for (i=0;in;i+)hti.c=si.c;hti.weight=si.weight;printf(哈夫曼树初态为:n);printf(data weight parent lchild rchildn);for (i=0;i2*n-1;i+)printf(%-
13、6c %-6d %-6d %-6d %-6dn,hti.c,hti.weight,hti.parent,hti.lchild,hti.rchild);for (i=n;i2*n-1;i+)min1=min2=32767;lnode=rnode=0;for (k=0;k=i-1;k+)if (htk.parent=-1)if (htk.weightmin1)min2=min1;rnode=lnode;min1=htk.weight;lnode=k;else if (htk.weightmin2)min2=htk.weight;rnode=k;htlnode.parent=i;htrnode.pa
14、rent=i;hti.weight=htlnode.weight+htrnode.weight;hti.lchild=lnode;hti.rchild=rnode;printf(n哈夫曼树终态为:n);printf(data weight parent lchild rchildn);for (i=0;i2*n-1;i+)printf(%-6c %-6d %-6d %-6d %-6dn,hti.c,hti.weight,hti.parent,hti.lchild,hti.rchild);printf(n);/哈夫曼编码void CreateCode(HTNode ht,HCode hcd,int n)int i,f,c;HCode hc;for (i=0;i
