Huffman编码实验分析报告

1、Huffman编码实验报告作者:日期:1二进制哈夫曼编码的原理及步骤信源编码的计算设有N个码元组成的离散、无记忆符号集，其中每个符号由一个二进制码字表示，信源符号个数n信源的概率分布P=p(sJ,i=1,.,n。且各符号xin的以li个码元编码，在变长字编码时每个符号的平均码长为Lp(xi)li;i1n信源熵为：H(X)p(xi)logp(xi);i1n唯一可译码的充要条件：mKi1;i1其中m为码符号个数，n为信源符号个数，Ki为各码字长度。构造哈夫曼数示例如下图所示。(1) 二元霍夫曼编码规则(1) 将信源符号依出现概率递减顺序排序。给两个概率最小的信源符号各分配一个码位“0”和“1”，将

2、两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n-1)个信源符号的新信源。称为信源的第一次缩减信源，用s1表示。(2) 将缩减信源s1的符号仍按概率从大到小顺序排列，重复步骤(2)，得到只含(n-2)个符号的缩减信源s2。(3) 重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1，然后从最后一级缩减信源开始，依编码路径向前返回,就得到各信源符号所对应的码字。2功能介绍输入一段字符序列，通过本程序可得出该字符序列中各个字符出现的次数，以及每个字符出现的概率，并能计算出信源符号熵，每个字符的哈弗曼编码，和相应的平均码长，编码效

3、率，码方差。3算法基本步骤描述4C语言源代码#include<stdio.h>#include<string.h>#include<math.h>#defineMAX100/定义全局变量h存放信息熵doubleh=0;/定义结构体用于存放信源符号，数目及概率typedefstruct/不同的字符charSOURCECODE;/不同字符出现的次数intNUM;/不同字符出现的概率doublePROBABILITY;/哈夫曼编码符号intCodeMAX;intstart;/哈夫曼树的父结点intparent;/哈夫曼树的左右子结点intlchild;intrch

4、ild;/哈夫曼编码的长度intlengthofhuffmancode;Hcode;HcodeINFORMATIONMAX;/该函数用来求信源所包含的符号，以及不同符号出现的次数和概率intPofeachsource(charinformationsourceMAX,inta)inti,j=1,m,flag=0;chartemp;/预先存入第一个字符，便于与后面的字符进行比较/统计不同的字符存入结构体数组中/利用flag标签来标记每个字符是否出现过，若出现过标记为1,否则置为零INFORMATION0.SOURCECODE=informationsource0;for(i=1;i<a;i

5、+)for(m=0;m<i;m+)flag=0;if(informationsourcem=informationsourcei)flag=1;break;if(flag=1)continue;elseINFORMATIONj+.SOURCECODE=informationsourcei;INFORMATIONj.SOURCECODE='0'printf("信源符号数为:%dn",j);/统计相同的字符出现的次数/每做一个字符出现次数的统计都将结构体数组里的NUh置为零for(i=0;i<j;i+)INFORMATIONi.NUM=0;for(m

6、=0;m<a;m+)if(informationsourcem=INFORMATIONi.SOURCECODE)INFORMATIONi.NUM+;/统计每个字符出现的概率for(i=0;i<j;i+)INFORMATIONi.PROBABILITY=(float)INFORMATIONi.NUM/a;/将每个不同字符出现的次数概率都显示出来for(i=0;i<j;i+)printf("TheNUMandPROBABILITYofCode'%c'is%dand%.3fn",INFORMATIONi.SOURCECODE,INFORMATIO

7、Ni.NUM,INFORMATIONi.PROBABILITY);returnj;/求信源符号的熵voidH(inta)inti;for(i=0;i<a;i+)h+=(-1)*(INFORMATIONi.PROBABILITY)*(log(INFORMATIONi.PROBABILITY)/log(2);/哈夫曼编码函数voidHuffman(inta)Hcodecd;inti,j,m=0,lm=0,p,c;doublemin,lmin;顺序初始化每个信源父子结点为-1for(i=0;i<a;i+)INFORMATIONi.parent=-1;INFORMATIONi.lchild

8、=-1;INFORMATIONi.lchild=-1;/循环构造Huffman树for(i=0;i<a-1;i+)/min,lmin中存放两个无父结点且结点权值最小的两个结点min=lmin=MAX;/找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树for(j=0;j<a+i;j+)if(INFORMATIONj.PROBABILITY<min)&&(INFORMATIONj.parent=-1)lmin=min;lm=m;min=INFORMATIONj.PROBABILITY;m=j;elseif(INFORMATIONj.PROBABIL

9、ITY<lmin)&&(INFORMATIONj.parent=-1)lmin=INFORMATIONj.PROBABILITY;lm=j;/设置找到的两个子结点m、lm的父结点信息INFORMATIONm.parent=a+i;INFORMATIONlm.parent=a+i;INFORMATIONa+i.PROBABILITY=INFORMATIONm.PROBABILITY+INFORMATIONlm.PROBABILITY;INFORMATIONa+i.parent=-1;INFORMATIONa+i.lchild=m;INFORMATIONa+i.rchild=

10、lm;for(i=0;i<a;i+)cd.start=a-1;c=i;p=INFORMATIONc.parent;while(p!=-1)/*父结点存在*/if(INFORMATIONp.lchild=c)cd.Codecd.start=1;elsecd.Codecd.start=0;cd.start-;/*求编码的低一位*/C=p;p=INFORMATIONc.parent;/*设置下一循环条件*/保存求出的每个叶结点的哈夫曼编码和编码的起始位for(j=cd.start+1;j<m;j+)INFORMATIONi.Codej=cd.Codej;INFORMATIONi.star

11、t=cd.start;voidmain()/定义存放信源符号的数组charinformationsourceMAX;inti,j,m;doubleaverageofhuffmancode=0.0,Eita,cV=0.0;printf("pleaseinputthesourceofinformation:");for(i=0;i+)scanf("%c",&informationsourcei);if(informationsourcei='n')break;informationsourcei='0'printf(&

12、quot;信源序列为:");/显示已输入的一串信源符号puts(informationsource);/返回不同信源符号的数目m=Pofeachsource(informationsource,i);/求信源的符号熵H(m);printf("信源的符号熵：H(X)=%.3f(比特/符号)n",h);Huffman(m);/输出已保存好的所有存在编码的哈夫曼编码for(i=0;i<m;i+)printf("%c'sHuffmancodeis:",INFORMATIONi.SOURCECODE);for(j=INFORMATIONi.

13、start+1;j<m;j+)printf("%d",INFORMATIONi.Codej);INFORMATIONi.lengthofhuffmancode=m-INFORMATIONi.start-1;printf("n");/求哈夫曼编码的平均码长和编码效率for(i=0;i<m;i+)averageofhuffmancode+=INFORMATIONi.PROBABILITY*INFORMATIONi.lengthofhuffmancode;printf("哈夫曼编码的平均码长为：lf(码元/信源符号)n",ave

14、rageofhuffmancode);Eita=h/averageofhuffmancode;printf("哈夫曼编码的编码效率为：lfn",Eita);/求哈弗曼编码的码方差for(i=0;i<m;i+)cV+=INFORMATIONi.PROBABILITY*INFORMATIONi.lengthofhuffmancode*INFORMATIONi.lengthofhuffmancode;cV-=averageofhuffmancode*averageofhuffmancode;printf("哈弗曼编码的码方差为：%lfn",cV);5运行

15、结果截图：$Huffilial!cudeJ.苔IIid*IrKuncode8011113Hli££e吐ncodeaiweioISHui-irr可nrdor1£r1H：IrlHoffnancodeQIS丄丄iiLU1FlAR13BillHiit-Imanrodelitr111Huffmancode110Htirfman1E00nHui-fmancodeTHwHuffnancuut?；BOOHurfn<tncodeis1P(1iHtiFtpiAnr-nnpissH<lffI'MIIuuue01101ThecinuFROBABILITVCodeprf

16、is1diiaHlyrCnAncodeiE1011MUM信孫的符号惰1H(X>-S.W«C比特”轩号>ft1a.odandanrtandNUMHUMCortepH#isCode1ui*io0.02STh疤ThoPROHAHILITVFROEAEILITVDieNUMandPROBABILITYufCuilepf*Is0.S83TheNUMandFROBflLilLUy1and.8.02UCoda9ofxgNUMNUMand)andand且nflTlieIheofFROBAEILITVFROmHILIIVCDdts：rfci'isCode*1*is0耽8M.M2NP

17、ROBflEILirVIhe：HUMando£Codopisand0.0&tNMand(.ore乂is1aniiM.MMhrnmcindFROBABILir'iofCodeeis1dind0B111irHMandFRORnFILirtCod©nisandNManriFRiiiBH卜；AA(.nriea1s：ainniTlieHUMaridFROBAEILITYof7andCode-'isT»wHUMPH0W1BILITVCodo：1o1isnnd0阳血Th?NUNandPItnmHILITYConf111isandDieHUMFRORAFT

18、LTTYCodei1isI0.028«iiufdHiftffiirire<eTbcandCodo-ioandPHOBnBILITVpicagoinputthoaaui*coo£informatien*thioioanoxanploaf亠Huffmarfctreo信源<71:thIsisHUMsHuffmailcodela：001丄呛夫具镰码甸黑均码苣为汨用昭宓码兀“言睛符号咗衣®§码的编码域率为=0"眄九咗弗昼輪码的彳绩潅知0-60L68OPir*i*s9anuki>vtormntinn#B"QXIJsertn.utDesktpCebugHuffman.exe6实验分析（1）在哈弗曼编码的过程中，对缩减信源符号按概率有大到小的顺序重新排列，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。（2）哈弗曼编码效率相当高，对编码器的要求也简单得多。（3）哈弗曼它保证了信源概率大的符号对应于短码，概率小的符号对应于长码，每次缩减信源的最后两个码字总是最后一位码元不同，前面的各位码元都相同，每次缩减信源的最长两个码字有相同的码长。（4）哈弗曼的编法并不一定是唯一的。7实验