哈夫曼编码信息论大作业模板

1、哈夫曼编码1 .前言：Haffman算法是个简单而高效的贪心算法，主要用来创建最优二叉树.可以在通讯时，对于出现频率较高的字符，用较少的比特数便可以进行通讯.从而节省通讯线路的资源消耗。该算法在各类数据结构，算法，组合数学，离散数学，图论等主题的书籍中都有所涉及。故本文不再赘述，本文致力于用Haffman算法实现压缩与解压缩，采用的语言为C语言，编译环境VC+6.0.下面给出1中实现的Haffman树的结构及创建算法，有两点说明：a)这里的Haffman树采用的是基于数组的带左右儿子结点及父结点下标作为存储结点的二叉树形式，这种空间上的消耗带来了算法实现上的便捷。b)由于对于最后生成的Haff

2、man树，其所有叶子结点均为从一个内部树扩充出去的，所以,当外部叶子结点数为m个时，内部结点数为m-1.整个Haffman树的需要的结点数为2m-1.2压缩过程的实现：压缩过程的流程是清晰而简单的：1创建Haffman树a2打开需压缩文件a褥需压缩文件中的每个ascii码对应的haffman编码按bit单位输出a4文件压缩结束。其中，步骤1和步骤3是压缩过程的关键。a) 步骤1:这里所要做工作是得到Haffman数中各叶子结点字符出现的频率并进行创建.统计字符出现的频率可以有很多方法：如每次创建前扫描被创建的文件，“实时”的生成各字符的出现频率；或者是创建前即做好统计.本文采用后一种的方案，统

3、计了十篇不同的文章中字符出现的频率。当前，也可以根据被压缩文件的特性有针对性的进行统计，如要压缩C语言的源文件，则可事先对多篇C语言源文件中出现的字符进行统计，这样，会创建出高度相对较“矮”的Haffman树，从而提高压缩效果。创建Haffman树的算法前文已有陈述，这里就不再重复了。b) 步骤3:将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出.这是本压缩程序中最关键的部分：这里涉及“转换”和“输出”两个关键步骤：“转换”部分大可不必去通过遍历Haffman树来找到每个字符对应的哈夫曼编码，可以将每个Haffman码值及其对应的ascii码存放于如下所示的结构体中：2

4、.算术编码(1)算术编码是把一个信源表示为实轴上0和1之间的一个区间，信源集合中的每一个元素都用来缩短这个区间。(2)设计思想：其算法的主要算法基本思想：首先就是构造一个结构体用于存储信源的相关信息(包括信源符号，信源概率，编码的上下限)；接着就是初始化信源的相关信息，如初始化编码间隔；利用算术编码的原理构造编码方法，最后实现编码。(3)调试分析：此算法主要就是算术编码方法的构造，利用算法中Initial_message()函数初始化以后，根据初始化间隔完成编码序列的编码。在调试的过程中经常遇到一些小问题，通过一步步的调试以及修改，问题一个的解决了。同时也遇到比较大的问题，就是编码方法过程的实

5、现，最大的体会就是必须深入理解次编码方法的原理。(4)流程图(5)测试结果:(6)源程序清单：#include#include#include#defineN4信源符号的个数#definen7/要编码的序列长度structARCcharmN;floatPN;floatLowN;floatHighN;floatlow;floathigh;code;Initial_message()初始化编码间隔floatF=0;inti=0,j;printf(请输入d个信源符号及其概率！n,N);for(i=0;iN;i+)scanf(%c%f,&code.mi,&code.Pi);getchar();for(

6、j=0;jN;j+)code.Lowj=F;F=F+code.Pj;code.Highj=F;printf(信源符号概率初始编码间隔n);for(j=0;jN;j+)printf(%c%f%f,%f)n,code.mj,code.Pj,code.Lowj,code.Highj);main()inti=0;intBcode10;charcn;char*p=NULL;char*q=NULL;floats,mid;Initial_message();printf(请输入长度为%d要编码白序列：”,n);scanf(%s,c);p=c;q=code.m;while(q!=NULL)/判定第一个需要编码

7、序列的第一符号所在的间隔if(*p=*q)code.low=code.Lowi;code.high=code.Highi;printf(%cn%f,%f)n,code.mi,code.low,code.high);gotoss;elseq+；i+；ss:p+；while(*p!=0)利用算术编码的方法，求出编码的十进制结果intk=0;floatt;floatpt=0;intk1;q=code.m;while(*q!=0)if(*p=*q)if(k=0)t=code.high-code.low;code.low=code.low+t*pt;code.high=code.low+t*code.P

8、k;printf(%cn%f,%f)n,code.mk,code.low,code.high);gotoxx;elsek1=k;while(k1)t=code.high-code.low;pt=pt+code.Pk1-1;k1-;code.low=code.low+t*pt;code.high=code.low+t*code.Pk;printf(%cn%f,%f)n,code.mk,code.low,code.high);gotoxx;elseq+；k+;xx:p+；mid=(code.high-code.low)/2+code.low;s=2*mid;for(i=0;i1)Bcodei=1;

9、s=s-1;elseBcodei=0;s=2*s;printf(%d,Bcodei);printf(n);3.Huffman编码对英文文本的压缩和解压缩(1)根据信源压缩编码一一Huffman编码的原理，制作对英文文本进行压缩和解压缩的软件。要求软件有简单的用户界面，软件能够对运行的状态生成报告，分别是：字符频率统计报告、编码报告、压缩程度信息报告、码表存储空间报告。(2)设计思想：首先构造一个结构体用于统计字符频率，然后把统计后的结果当作信源；接着用Haffman编码的方法对其编码，编码后对输入的英语文本进行编码的转换，即用Haffman编码的每一个字符的编码代替输入的英语文本每一字符，输入

10、的英语文本就变成了01代码流，最后利用这01代码流每八位压缩成相对应的字符。压缩流程:读取扫描文本文口一统巾字符频率一二!生成岬字一一呆存压绯文件I解压缩流程：读取扫描压缩文件二|一提半字符频率一二生成州树一一呆存文用/I(3)调试分析：本算法可以分成四个部分即统计字符概率，Huffman编码，压缩文件和解压文件四部分，也就是次算法中函数stati()，函数HCode()和函数compress()的构建，用于压缩后的字符出现了乱码，所以对解压文件这部分难以实现，这也是此算法失败的地方。经过不断的调试和修改还是只完成统计字符概率，Huffman编码和压缩文件这三部分。(4)流程图(5)测试结果:

11、i1l叫:虚面f言息论上机Huffman4BE的和解压轮Debug、.WH-.n编码的对英文文本压缩和解压缩幅输入用于保存字符文本的文件名，如l-txtfile.txt请输入英语文本；aaabbbeeeeeettttthhhhhhkkll；1,加nucfggFfgghhjhfgerefhhhthannhbhthhhenbbnfhjfhfhjI字符abe字符统计出现的次数5810723nucf9323125310103uiqrxJ概率0.04587155960.0733944954G.09174311930.0642201835G.2110091743er61834862399.02752293

12、580.018386239G.02752293580.00917431199r01834862390.04587155960.02752293580.0366972770.09174311930,09174311939.02752293583.06917431190.60917431190.01834862390.00917431190,0275229358信源符号mwH/fmmn编码权值Weight：1ldeight=1lileight=1Weiqht=1编码结果Code=1101000Cod1101001Code=TW101GCode=1101011IH(6)源程序清单：#include#

13、include#defineMaxValue1000/设定权值最大值#defineMaxBit10/设定的最大编码位数#defineMaxN1000/设定的最大结点个数#includeHuffman.hfloatComNum=0;用于计算压缩后的字符个数structstatistics/统计字符频率chara100;/出现的字符doublep100;字符出现的概率inttag100;/每一个字符出现次数intnum;/总计出现的字符种类个数floatn;/总计字符出现的次数TJ；charcc100;voidraplace(myHaffCode);stati()统计字符FILE*fp;FILE*

14、fp1;charch,filename10;inti=0,k;printf(请输入用于保存字符文本的文件名，如file.txtn);scanf(%s,filename);getchar();printf(请输入英语文本：)；gets(cc);fp=fopen(filename,w+);fprintf(fp,%s,cc);fclose(fp);TJ.num=1;TJ.n=0;if(fp1=fopen(filename,r)=NULL)printf(文件无法打开！力exit(0);ch=fgetc(fp1);TJ.ai=ch;while(ch!=EOF)统计字符出现的次数，并计算起概率。intj;

15、for(j=i;j=0;j-)if(TJ.aj=ch)TJ.tagj+=1;gotoxx;i+;TJ.ai=ch;TJ.tagi+=1;TJ.num+;xx:ch=fgetc(fp1);TJ.n+;fclose(fpl);for(k=0;k=i;k+)TJ.pk=TJ.tagk/TJ.n;printf(t字符统计n);printf(字符出现的次数概率n);for(k=0;k=i;k+)printf(%c%d%1.10fn,TJ.ak,TJ.tagk,TJ.pk);HCode()/haffman编码inti,j,n=TJ.num;HaffNode*myHaffTree=(HaffNode*)ma

16、lloc(sizeof(HaffNode)*(2*n+1);Code*myHaffCode=(Code*)malloc(sizeof(Code)*TJ.num);for(i=0;in;i+)排序-假字符出现的次数从小到大排intt=TJ.tagi;chart1=TJ.ai;for(j=i+1;jTJ.tagj)t=TJ.tagj;TJ.tagj=TJ.tagi;TJ.tagi=t;t1=TJ.aj;TJ.aj=TJ.ai;TJ.ai=t1;Haffman(TJ.tag,n,myHaffTree);/建立叶结点个数为n权值数组为J.tag的哈夫曼树myHaffTreeHaffmanCode(my

17、HaffTree,n,myHaffCode);/由n个结点的夫曼树myHaffTree构造哈夫曼编码myHaffCodeprintf(tHaffman编码n);printf(信源符号权值编码结果n);for(i=0;in;i+)printf(%cWeight=%dCode=,TJ.ai,myHaffCodei.weight);for(j=myHaffCodei.start;jn；j+)printf(%d,myHaffCodei.bitj);printf(n);raplace(myHaffCode);voidraplace(CodemyHaffCode口)把英语文本的字母包(括标点符号)用已经用

18、Haffman编码完成的编码结果代替成01代码并存于文件code.txt中charch;inti,n,j;FILE*fp1;if(fp1=fopen(code.txt,w+)=NULL)printf(文件无法打开！);exit(0);n=0;ch=ccn;while(ch!=0)for(j=0;jTJ.num;j+)if(ch=TJ.aj)for(i=myHaffCodej.start;iTJ.num;i+)fprintf(fp1,%d,myHaffCodej.biti);j=TJ.num;n+;ch=ccn;fclose(fp1);voidcompress。根据保存于code.txt的01代码每八位压缩一次FILE*fp1,*fp2;intch;charc;inti=0;intvalue;inta8=0;fp1=fopen(code.txt,r);fp2=fopen(yasuo.txt,w+);yasu.txt用于存储压缩后的结果while(!feof(fp1)fscanf(fp1,%1d,&ch);ai=ch;i+;if(i=8)value=a0*128+a1*64+a2*32+a3*16+a4*8+a5*4+a6*2+a7;c=value;fprintf(fp2,%c,c);ComNum+;i