Huffman编码实验报告

1二进制哈夫曼编码的原理及步骤（1）信源编码的计算设有N个码元组成的离散、无记忆符号集，其中每个符号由一个二进制码字表示，信源符号个数n、信源的概率分布P={p(si)},i=1,…..,n。且各符号xi的以li个码元编码，在变长字编码时每个符号的平均码长为；信源熵为：；唯一可译码的充要条件：；其中m为码符号个数，n为信源符号个数，Ki为各码字长度。构造哈夫曼数示例如下图所示。1.000000001.000000000.400.600.400.600.300.300.300.3050.150.090.600.090.600.030.030.040.050.030.030.040.05（2）二元霍夫曼编码规则（1）将信源符号依出现概率递减顺序排序。（2）给两个概率最小的信源符号各分配一个码位“0”和“1”，将两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含（n-1）个信源符号的新信源。称为信源的第一次缩减信源，用s1表示。（3）将缩减信源s1的符号仍按概率从大到小顺序排列，重复步骤(2)，得到只含（n-2）个符号的缩减信源s2。（4）重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1，然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。2功能介绍输入一段字符序列，通过本程序可得出该字符序列中各个字符出现的次数，以及每个字符出现的概率，并能计算出信源符号熵，每个字符的哈弗曼编码，和相应的平均码长，编码效率，码方差。3算法基本步骤描述得到信源序列得到信源序列输出得出信源序列输出得出信源序列个数得出信源序列的概率输出计算信源符号熵输出计算信源符号熵输出信源符号的哈弗曼编码输出信源符号的哈弗曼编码平均码长输出平均码长输出输出编码效率输出编码效率输出码方差输出码方差4C语言源代码#include<stdio.h>#include<string.h>#include<math.h>#defineMAX100//定义全局变量h存放信息熵doubleh=0;//定义结构体用于存放信源符号，数目及概率typedefstruct{//不同的字符 charSOURCECODE;//不同字符出现的次数 intNUM;//不同字符出现的概率 doublePROBABILITY;//哈夫曼编码符号 intCode[MAX]; intstart;//哈夫曼树的父结点 intparent;//哈夫曼树的左右子结点 intlchild; intrchild;//哈夫曼编码的长度 intlengthofhuffmancode;}Hcode;HcodeINFORMATION[MAX];//该函数用来求信源所包含的符号，以及不同符号出现的次数和概率intPofeachsource(charinformationsource[MAX],inta){ inti,j=1,m,flag=0; chartemp;//预先存入第一个字符，便于与后面的字符进行比较//统计不同的字符存入结构体数组中//利用flag标签来标记每个字符是否出现过，若出现过标记为1，否则置为零 INFORMATION[0].SOURCECODE=informationsource[0]; for(i=1;i<a;i++){ for(m=0;m<i;m++){ flag=0; if(informationsource[m]==informationsource[i]){ flag=1; break; } } if(flag==1) continue; else INFORMATION[j++].SOURCECODE=informationsource[i]; } INFORMATION[j].SOURCECODE='\0'; printf("信源符号数为:%d\n",j);//统计相同的字符出现的次数//每做一个字符出现次数的统计都将结构体数组里的NUM置为零 for(i=0;i<j;i++){ INFORMATION[i].NUM=0; for(m=0;m<a;m++) if(informationsource[m]==INFORMATION[i].SOURCECODE) INFORMATION[i].NUM++; }//统计每个字符出现的概率 for(i=0;i<j;i++) INFORMATION[i].PROBABILITY=(float)INFORMATION[i].NUM/a;//将每个不同字符出现的次数概率都显示出来 for(i=0;i<j;i++) printf("TheNUMandPROBABILITYofCode'%c'is%dand%.3f\n",INFORMATION[i].SOURCECODE,INFORMATION[i].NUM,INFORMATION[i].PROBABILITY); returnj;}//求信源符号的熵voidH(inta){ inti; for(i=0;i<a;i++){ h+=((-1)*(INFORMATION[i].PROBABILITY)*(log(INFORMATION[i].PROBABILITY)/log(2))); }}//哈夫曼编码函数voidHuffman(inta){ Hcodecd; inti,j,m=0,lm=0,p,c; doublemin,lmin;//顺序初始化每个信源父子结点为-1for(i=0;i<a;i++){INFORMATION[i].parent=-1;INFORMATION[i].lchild=-1;INFORMATION[i].lchild=-1;} //循环构造Huffman树for(i=0;i<a-1;i++){//min,lmin中存放两个无父结点且结点权值最小的两个结点min=lmin=MAX;//找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树for(j=0;j<a+i;j++){if((INFORMATION[j].PROBABILITY<min)&&(INFORMATION[j].parent==-1)){lmin=min;lm=m;min=INFORMATION[j].PROBABILITY;m=j;}elseif((INFORMATION[j].PROBABILITY<lmin)&&(INFORMATION[j].parent==-1)){lmin=INFORMATION[j].PROBABILITY;lm=j;}}//设置找到的两个子结点m、lm的父结点信息INFORMATION[m].parent=a+i;INFORMATION[lm].parent=a+i;INFORMATION[a+i].PROBABILITY=INFORMATION[m].PROBABILITY+INFORMATION[lm].PROBABILITY; INFORMATION[a+i].parent=-1;INFORMATION[a+i].lchild=m;INFORMATION[a+i].rchild=lm;} for(i=0;i<a;i++){cd.start=a-1;c=i;p=INFORMATION[c].parent;while(p!=-1)/*父结点存在*/{if(INFORMATION[p].lchild==c)cd.Code[cd.start]=1;elsecd.Code[cd.start]=0;cd.start--;/*求编码的低一位*/c=p;p=INFORMATION[c].parent;/*设置下一循环条件*/}//保存求出的每个叶结点的哈夫曼编码和编码的起始位for(j=cd.start+1;j<m;j++){INFORMATION[i].Code[j]=cd.Code[j];}INFORMATION[i].start=cd.start; }}voidmain(){//定义存放信源符号的数组 charinformationsource[MAX]; inti,j,m; doubleaverageofhuffmancode=0.0,Eita,cV=0.0; printf("pleaseinputthesourceofinformation:"); for(i=0;;i++){ scanf("%c",&informationsource[i]); if(informationsource[i]=='\n') break; } informationsource[i]='\0'; printf("信源序列为:");//显示已输入的一串信源符号 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:",INFORMATION[i].SOURCECODE);for(j=INFORMATION[i].start+1;j<m;j++)printf("%d",INFORMATION[i].Code[j]); INFORMATION[i].lengthofhuffmancode=m-INFORMATION[i].start-1;printf("\n");}//求哈夫曼编码的平均码长和编码效率 for(i=0;i<m;i++) averageofhuffmancode+=INFORMATION[i].PROBABILITY*INFORMATION[i].lengthofhuffmancode; printf("哈夫曼编码的平均码长为:%lf(码元/信源符号)\n",averageofhuffmancode); Eita=h/averageofhuffmancode; printf("哈夫曼编码的编码效率为:%lf\n",Eita);//求哈弗曼编码的码方差 for(i=0;i<m;i++) cV+=INFORMATION[i].PROBABILITY*INFORMATION[i].lengthofhuffmancode*INFORMATION[i].lengthofhuffmancode; cV-=averageofhuffmancode*averageofhuffmancode; printf("哈弗曼编码的码方差为：%lf\n",cV);}5运行结果截图:6实验分析（1）在哈弗曼编码的过程中，对缩减信源符号按概率有大到小的顺序重新排列，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。（2）哈弗曼编码效率相当高，对编码器的要求也简单得多。（3）哈弗曼它保证了信源概率大的符号对应于短码，概率小的符号对应于长码，每次缩减信源的最后两个码字总是最后一位码元不同，前面的各位码元都相同，每次缩减信源的最长两个码字有相同的码长。（4）哈弗曼的编法并不一定是唯一的。