信息论与编码课程设计报告课件.pdf

信息论与编码课程设计报告Huffman 编码与译码姓名:学院:班级:学号:指导老师:2010 年 12 月一、课程设计目的一、课程设计目的掌握通过计算机编程实现Huffman 编码二、基本原理二、基本原理Huffman 编码又称哈夫曼编码，是一种可变长编码方式，是由美国数学家David Huffman创立的，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。Huffman 算法的最根本的原则是：累计的(字符的统计数字*字符的编码长度)为最小，也就是权值(字符的统计数字*字符的编码长度)的和最小。Huffman 编码的步骤：1)把信源符号按概率大小顺序排列，并设法按逆次序分配码字的长度。2)在分配码字长度时，首先将出现概率最小的两个符号的概率相加合成一个概率。3)把这个合成概率看成是一个新组合符号地概率，重复上述做法直到最后只剩下两个符号概率为止。11)完成以上概率顺序排列后，再反过来逐步向前进行编码，每一次有二个分支各赋予一个二进制码，可以对概率大的赋为0，概率小的赋为 1。Huffman 编码分析：从以上编码步骤可以看出，Huffman 码是用概率匹配的方法进行信源匹配方法进行信源。它有两个明显的特点：一是 Huffman 码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分应用了短码；二是缩减信源的最后二个码字总是最后一位不同，从而保证了 Huffman编码是及时码。Huffman 变长码的效率是相当高的，它可以单个信源符号编码或用长度较小的信源序列编码，对编码的设计来说也将简单得多。本次实验将采用 C 语言对 Huffman 编码的实现进行编程，主要实现的功能是对字符串编码（实现压缩的功能），而后进行相反译码过程（即解压的功能）。其中将使用数据结构中的Huffman 树的知识，最后将基本功能进行扩展，从而实现对一个txt 文档的压缩和解压功能。本次实验中的编码过程的基本流程图如下所示：开始读取输入数据流统计各字符频率对各字符进行排序建立 Huffman 树对各字符进行编码结束三、方案实践与调试三、方案实践与调试本程序主要分为以下本程序主要分为以下 4 4 部分：部分：1 构造 Huffman 树给定 n 个实数 w1，w2，wn（n），求一个具有 n 个结点的二叉数，使其带权路径长度最小。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为 0 层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为 WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N 个权值 Wi(i=1,2,.n)构成一棵有 N 个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,.n)。可以证明Huffman 树的 WPL 是最小的。(1)根据与n 个权值 w1,w2wn对应的n 个结点构成具有n 棵二叉树的森林F=T1,T2Tn,其中第 i 棵二叉树 Ti(1 i n)都只有一个权值为 wi 的根结点，其左、右子树均为空(2)在森林 F 中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、右子树上根结点权值之和(3)从 F 中删除构成新树的那两棵，同时把新树加入F 中(4)重复第(2)和第(3)步，直到 F 中只含有一棵为止，此树便为Huffman树2 Huffman 编码算法根据最优二叉树构造 Huffman 编码，利用 Huffman 树很容易求出给定字符集及其概率(或频度)分布的最优前缀码。Huffman 编码正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉20至 90，其压缩效率取决于被压缩文件的特征。（1）用字符 si作为叶子，counti做为叶子 si的权，构造一棵 Huffman 树，并将树中左分支和右分支分别标记为0 和 1；（2）将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的编码。该编码即为最优前缀码（也称 Huffman 编码）。3 Huffman 译码算法依次读人文件的二进制码，从 Huffman 树的根结点(即 Tm-1)出发，若当前读人 0，则走向左孩子，否则走向右孩子。一旦到达某一叶子 T 时便译出相应的字符 H.ch。然后重新从根出发继续译码，直至文件结束。4 二进制转换算法将 Huffman 编码存储为二进制文件以及将生成的二进制文件转换为Huffman 编码以实现压缩的过程。程序中主要定义了两个结构体：程序中主要定义了两个结构体：1.定义赫夫曼树节点结构体typedef struct node int weight;struct node*LChild,*RChild,*Parent;/分别指向该节点的左孩子，右孩子，和双亲节点struct node*next;HFMNode,*HFMTree;2.定义赫夫曼编码的结构体typedef struct char ch;/存储对应的字符char codeN+1;/存储对应字符的编码int start;/存储编码的起始位置/指向建立的赫夫曼树的下一个节点CodeNode;详细设计详细设计1构造霍夫曼树主要代码如下：void CreatHFMTree(HFMTree*HT,int count)/创建赫夫曼树int i;HFMTree p,HT1,HT2;/HT1，HT2 分别存放权值最小和次小的节点的位置p=*HT=(HFMTree)malloc(sizeof(HFMNode);p-next=p-LChild=p-RChild=p-Parent=NULL;/初始化赫夫曼链表且有 2n-1 个节点for(i=1;inext=(HFMTree)malloc(sizeof(HFMNode);p=p-next;p-next=p-LChild=p-RChild=p-Parent=NULL;for(i=0,p=*HT;iweight=counti;p=p-next;for(i=n;iParent=HT2-Parent=p;p-LChild=HT1;p-RChild=HT2;p-weight=HT1-weight+HT2-weight;/将两个节点的权值相加存入一个节点p=p-next;/p 指向下一个没有存储权值的节点2霍夫曼编码算法主要代码如下：void TotalCoding(char s,CodeNode HC,char code)/利用赫夫曼编码表对整个字符串进行编码 int i,j;code0=0;/编码数组初始化 for(i=0;si;i+)for(j=0;jParent;root=root-Parent);/用 root 指向赫夫曼树的根结点for(i=0,p=root;codei;i+)/从根结点开始按编码顺序访问树if(codei=0)p=p-LChild;else p=p-RChild;if(p-LChild=NULL&p-RChild=NULL)/到根节点时将该节点对应的字符输出for(j=0,q=HT;q!=p;q=q-next,j+);sk+=strj;p=root;/回溯到根结点sk=0;/解码完毕，在字符串最后一个单元存入0编码界面解码界面四、总结体会四、总结体会在这次课程设计中，通过对程序的编写，调试和运行，使我更好的掌握了 Huffman 树等数据结构方面的基本知识和各类基本程序问题的解决方法，熟悉了各种调用的数据类型，在调试和运行过程中，加深我对程序运行的环境了解和熟悉的程度，同时也提高了我对程序调试分析的能力和对错误纠正的能力。这次信息论与编码的程序设计，对于我来说是一个挑战。我对数据结构的学习在程序的设计中也有所体现。课程设计是培养学生综合运用所学知识，发现问题、提出问题、分析问题和解决问题的过程，锻炼学生的逻辑思维能力和实践能力，是对学生实际工作能力的具体训练和考察过程。在整个课程程序中，我们充分应用和调用各个程序模块，从而部分实现了此次程序设计的所应该有的功能。就是我在课程设计是比较成功的方面，而在这个过程中，让我感觉收获最大的就是我们都能利用这次课程设计学到很多我们在课本上没有的知识，充分的发挥了我们的主动性，使我们学会了自主学习，和独立解决问题的能力。很多程序在结构上是独立的，但是本此设计的程序功能不是零散的，它有一个连接是的程序是一个整体，达到这种统一体十分重要，因为这个输出连接是贯穿始终的。这次的程序软件基本上运行成功，可以简单的输入进行压缩，并且运用简单的数字告诉程序的操作者下一步该如何进行，使得程序规模相对较小，即功能还不很全面，应用也不很普遍。原来数据结构可以涉及很多知识，而不是枯燥无聊的简单的代码部分而已，利用数据结构方面的知识，我们可以设计出更完善的软件。总而言之，这次数据结构课程设计让我们感触很深，使我们每个人都了解到学习不应该只局限于课本，因为课本上告诉我们的只是很有限的一部分，只是理论上的死知识，所涉及的范围也是狭窄的。我们若想在有限的范围内学习到无限的知识，就要我们自己懂得争取，懂得自学，懂得充分利用身边的任何资源。在我们的程序中有一部分查找许多该方面的资料，我竭力将所获得的信息变成自己的资源。我动手上机操作的同时，在了解和看懂的基础上对新学的知识进行改进和创新，但是在我们的程序软件中还有很多的不足，需要加以更新。通过这次课程设计，我们都意识到了自己动手实践的弱势，特别是在编程方面，于是我们知道了计算机的实践操作是很重要的，只有通过上机编程才能充分的了解自己的不足。通过这次的课程设计，我们深刻意识到自己在学习中的弱点，同时也找到了克服这些弱点的方法，这是在此活动中得到的一笔很大的财富。在以后的时间中，我们应该利用更多的时间去上机实验，多编写程序，相信不久后我们的编程能力都会有很大的提高，能设计出更多的更有创新的软件。同时也感谢老师给我们这次机会，发现自身存在的缺点与不足，从而在以后的大学生活中更好的提升和完善自我。参考书目参考书目:2严蔚敏,吴伟民.数据结构.清华大学出版社,2007.4附录源代码#include#include#include#include#define M 10000/定义字符串最大长度#define N 128义叶子节点个数typedef struct node义赫夫曼树节点结构体int weight;struct node*LChild,*RChild,*Parent;分别指向该节点的左孩子，右孩子，和双亲节点struct node*next;/指向建立的赫夫曼树的下一个节点HNode,*HTree;typedef struct义赫夫曼编码的结构体char ch;/存储对应的字符char codeN+1;/存储对应字符的编码int start;/存储编码的起始位置CodeNode;int n;储真正叶子节点个数void Open(char s)开存放字符或编码的文件，将其存入字符串数组中charname10;FILE*fp;int i=0,j;printf(请输入待压缩文件的文件名：);getchar();scanf(%s,name);/要打开的文件名/定/定/定/存/打if(fp=fopen(name,rt)=NULL)printf(打开失败！n);/若打开失败，则直接退出 exit(1);si+=fgetc(fp);while(si-1!=EOF)si+=fgetc(fp);si=0;/存取字符串结束fclose(fp);void Save(char s)存字符或编码到文件中char name10;FILE*fp;printf(请输入要保存的文件名：);gets(name);if(fp=fopen(name,wt)=NULL)printf(存储失败！);exit(1);fputs(s,fp);printf(n 保存成功，文件名为:%s。n,name);printf(n 按回车键继续.);getchar();fclose(fp);void SearchStr(char s,char str,int count)中字符的个数和每个字符出现的次数int i,j,k=0;for(i=0;iN;i+)/初始化每个字符出现的次数 counti=0;for(i=0;si;i+)for(j=0;jk;j+)str中查找是否有该字符if(strj=si)countj+;break;if(j=k)str中无该字符，将其存入最后一个单元strk=si;countk+;strk=0;/将字符串结尾置“0”n=k;/将实际的字符个数作为叶子节点个数存入n/保/查找字符串/在/在void SelectMin(HTree HT,int k,HTree*HT1,HTree*HT2)找赫夫曼链表中两个权值最小的节点int i,min;HTree p;min=32767;for(i=0,p=HT;inext)if(p-weightParent=0)min=p-weight;*HT1=p;min=32767;for(i=0,p=HT;inext)if(p-weightParent=0&p!=*HT1)第二个最小的节点不等于第一个节点 min=p-weight;*HT2=p;void CreatHFMTree(HTree*HT,int count)夫曼树int i;HTree p,HT1,HT2;/HT1，HT2 分别存放权值最小和次小的节点的位置p=*HT=(HTree)malloc(sizeof(HNode);p-next=p-LChild=p-RChild=p-Parent=NULL;for(i=1;inext=(HTree)malloc(sizeof(HNode);p=p-next;p-next=p-LChild=p-RChild=p-Parent=NULL;各个字符出现的次数作为权值for(i=0,p=*HT;iweight=counti;p=p-next;for(i=n;iParent=HT2-Parent=p;p-LChild=HT1;p-RChild=HT2;p-weight=HT1-weight+HT2-weight;/将两个节点的权值相加存入最后一个节点中 p=p-next;/p指向下一个没有存储权值的节点void HFMCode(HTree HT,CodeNode HC,char str)/查/令/创 建 赫/将/每/从每个叶子节点开始，利用赫夫曼树对每个字符进行编码，最终建立一个赫夫曼表int i;HTree q,p=HT;for(i=0;in;i+)/将字符存入赫夫曼编码结构体数组的字符单元中 HCi.ch=stri;HCi.coden-1=0;始化编码的最后一位for(i=0;iParent;q=q-Parent)断 q 所指向的节点，左孩子置0，右孩子置 1if(q=q-Parent-LChild)HCi.code-HCi.start=0;else HCi.code-HCi.start=1;p=p-next;断下一个叶子节点void TotalCoding(char s,CodeNode HC,char code)夫曼编码表对整个字符串进行编码int i,j;code0=0;码数组初始化for(i=0;si;i+)每个字符在赫夫曼编码表中对应的编码存入存放总编码的数组中for(j=0;jParent;root=root-Parent);root 指向赫夫曼树的根结点for(i=0,p=root;codei;i+)根结点开始按编码顺序访问树 if(codei=0)p=p-LChild;else p=p-RChild;if(p-LChild=NULL&p-RChild=NULL)/到根节点时将该节点对应的字符输出for(j=0,q=HT;q!=p;q=q-next,j+);sk+=strj;p=root;溯到根结点/初/判/判/利 用 赫/编/将/对 赫 夫/用/从/回 sk=0;/解码完毕，在字符串最后一个单元存入0void TransCode(char code,char str,char ss,HTree*HT,CodeNode HC)char str_in;printf(n 打开编码的文件.nn);Open(code);/打开编码文件DeCoding(code,*HT,str,ss);/将编码进行解码存入字符串数组ss中printf(n 得到的最终字符串为:n);puts(ss);printf(你要保存译码吗?输入 y 或 n:);scanf(%c,&str_in);if(str_in=y)Save(ss);/保存译码后的字符串void showtip1(char sM)char chr_in;printf(t 你选择了编码:n);couttt|-|endl;couttt|-编码-|endl;couttt|-|endl;couttt|a.手动输入couttt|couttt|b.从文件输入couttt|couttt|-|endl;coutchr_in;switch(chr_in)case a:printf(请输入并以#号结束:n);cin.get(s,M,#);break;case b:Open(s);printf(打开的文件内容为:n);break;default:printf(输入错误！n);void Coding(char s,char str,char code,int count,HTree*HT,CodeNode HC)char str_in;showtip1(s);printf(n 读入的字符串为:n);puts(s);|endl;|endl;|endl;|str_in;getchar();if(str_in=y)Save(code);getchar();存最终的赫夫曼编码/system(cls);int main()/主函数 char choice;dochar sM,ssM;/定义字符串数组，s存放将要编码的字符串，ss存解码后的字符串char strN;/存放输入的字符串中 n 个不同的字符int countN;/存放 n 个不同字符对应的在原字符串中出现的次数char codeM;/存放最终编码完成后的编码HTree HT;/定义一个赫夫曼树的链表CodeNode HCN;/定义一个赫夫曼编码表的数组，存放每个字符对应的赫夫曼编码couttt|-|endl;couttt|-赫夫曼编译系统-|endl;couttt|-|endl;couttt|1.编码couttt|2.解码couttt|3.说明couttt|0.退出couttt|-|endl;coutchoice;system(cls);switch(choice)case 1:Coding(s,str,code,count,&HT,HC);break;串进行编码/查/保|endl;|endl;|endl;|endl;/对 字 符 case 2:TransCode(code,str,ss,&HT,HC);break;/对 编 码进行解码 case 3:printf(该系统最大输入字符为 5000 个!n);printf(译码必须是赫夫曼编译出的密码n);case 0:break;default:printf(输入错误！请重新输入！n);while(choice!=0);return 0;