信息论与编码课程设计报告课件.pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《信息论与编码课程设计报告课件.pdf》由会员分享,可在线阅读,更多相关《信息论与编码课程设计报告课件.pdf(15页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、信息论与编码课程设计报告Huffman 编码与译码姓名:学院:班级:学号:指导老师:2010 年 12 月一、课程设计目的一、课程设计目的掌握通过计算机编程实现Huffman 编码二、基本原理二、基本原理Huffman 编码又称哈夫曼编码,是一种可变长编码方式,是由美国数学家David Huffman创立的,是二叉树的一种特殊转化形式。编码的原理是:将使用次数多的代码转换成长度较短的代码,而使用次数少的可以使用较长的编码,并且保持编码的唯一可解性。Huffman 算法的最根本的原则是:累计的(字符的统计数字*字符的编码长度)为最小,也就是权值(字符的统计数字*字符的编码长度)的和最小。Huff
2、man 编码的步骤:1)把信源符号按概率大小顺序排列,并设法按逆次序分配码字的长度。2)在分配码字长度时,首先将出现概率最小的两个符号的概率相加合成一个概率。3)把这个合成概率看成是一个新组合符号地概率,重复上述做法直到最后只剩下两个符号概率为止。11)完成以上概率顺序排列后,再反过来逐步向前进行编码,每一次有二个分支各赋予一个二进制码,可以对概率大的赋为0,概率小的赋为 1。Huffman 编码分析:从以上编码步骤可以看出,Huffman 码是用概率匹配的方法进行信源匹配方法进行信源。它有两个明显的特点:一是 Huffman 码的编码方法保证了概率大的符号对应于短码,概率小的符号对应于长码,
3、充分应用了短码;二是缩减信源的最后二个码字总是最后一位不同,从而保证了 Huffman编码是及时码。Huffman 变长码的效率是相当高的,它可以单个信源符号编码或用长度较小的信源序列编码,对编码的设计来说也将简单得多。本次实验将采用 C 语言对 Huffman 编码的实现进行编程,主要实现的功能是对字符串编码(实现压缩的功能),而后进行相反译码过程(即解压的功能)。其中将使用数据结构中的Huffman 树的知识,最后将基本功能进行扩展,从而实现对一个txt 文档的压缩和解压功能。本次实验中的编码过程的基本流程图如下所示:开始读取输入数据流统计各字符频率对各字符进行排序建立 Huffman 树
4、对各字符进行编码结束三、方案实践与调试三、方案实践与调试本程序主要分为以下本程序主要分为以下 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)。可以证明Huffma
5、n 树的 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 树很容易求出给定字符
6、集及其概率(或频度)分布的最优前缀码。Huffman 编码正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉20至 90,其压缩效率取决于被压缩文件的特征。(1)用字符 si作为叶子,counti做为叶子 si的权,构造一棵 Huffman 树,并将树中左分支和右分支分别标记为0 和 1;(2)将从根到叶子的路径上的标号依次相连,作为该叶子所表示字符的编码。该编码即为最优前缀码(也称 Huffman 编码)。3 Huffman 译码算法依次读人文件的二进制码,从 Huffman 树的根结点(即 Tm-1)出发,若当前读人 0,则走向左孩子,否则走向右孩子。一旦到达某一叶子
7、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;/存
8、储对应的字符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;ine
9、xt=(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
10、,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;/回溯到根结
11、点sk=0;/解码完毕,在字符串最后一个单元存入0编码界面解码界面四、总结体会四、总结体会在这次课程设计中,通过对程序的编写,调试和运行,使我更好的掌握了 Huffman 树等数据结构方面的基本知识和各类基本程序问题的解决方法,熟悉了各种调用的数据类型,在调试和运行过程中,加深我对程序运行的环境了解和熟悉的程度,同时也提高了我对程序调试分析的能力和对错误纠正的能力。这次信息论与编码的程序设计,对于我来说是一个挑战。我对数据结构的学习在程序的设计中也有所体现。课程设计是培养学生综合运用所学知识,发现问题、提出问题、分析问题和解决问题的过程,锻炼学生的逻辑思维能力和实践能力,是对学生实际工作能力的
12、具体训练和考察过程。在整个课程程序中,我们充分应用和调用各个程序模块,从而部分实现了此次程序设计的所应该有的功能。就是我在课程设计是比较成功的方面,而在这个过程中,让我感觉收获最大的就是我们都能利用这次课程设计学到很多我们在课本上没有的知识,充分的发挥了我们的主动性,使我们学会了自主学习,和独立解决问题的能力。很多程序在结构上是独立的,但是本此设计的程序功能不是零散的,它有一个连接是的程序是一个整体,达到这种统一体十分重要,因为这个输出连接是贯穿始终的。这次的程序软件基本上运行成功,可以简单的输入进行压缩,并且运用简单的数字告诉程序的操作者下一步该如何进行,使得程序规模相对较小,即功能还不很全
13、面,应用也不很普遍。原来数据结构可以涉及很多知识,而不是枯燥无聊的简单的代码部分而已,利用数据结构方面的知识,我们可以设计出更完善的软件。总而言之,这次数据结构课程设计让我们感触很深,使我们每个人都了解到学习不应该只局限于课本,因为课本上告诉我们的只是很有限的一部分,只是理论上的死知识,所涉及的范围也是狭窄的。我们若想在有限的范围内学习到无限的知识,就要我们自己懂得争取,懂得自学,懂得充分利用身边的任何资源。在我们的程序中有一部分查找许多该方面的资料,我竭力将所获得的信息变成自己的资源。我动手上机操作的同时,在了解和看懂的基础上对新学的知识进行改进和创新,但是在我们的程序软件中还有很多的不足,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息论 编码 课程设计 报告 课件
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内