Huffman编码实验报告.doc

《Huffman编码实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1二进制哈夫曼编码的原理及步骤（1）信源编码的计算设有N个码元组成的离散、无记忆符号集，其中每个符号由一个二进制码字表示，信源符号个数n、信源的概率分布P={p(si)},i=1,…..,n。且各符号xi的以li个码元编码，在变长字编码时每个符号的平均码长为；信源熵为：；唯一可译码的充要条件：；其中m为码符号个数，n为信源符号个数，Ki为各码字长度。构造哈夫曼数示例如下图所示。1.0.400.600.300.300.150.150.090.600.030.030.040.05（2）二元霍夫曼编码规则（1）将信源符号依出现概率递减顺序排序。（2）给两个概率最小的信源符号各

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

3、熵，每个字符的哈弗曼编码，和相应的平均码长，编码效率，码方差。3算法基本步骤描述得到信源序列输出得出信源序列个数得出信源序列的概率输出计算信源符号熵输出信源符号的哈弗曼编码平均码长输出输出编码效率输出码方差4C语言源代码#include#include#include#defineMAX100//定义全局变量h存放信息熵doubleh=0;//定义结构体用于存放信源符号，数目及概率typedefstruct{//不同的字符charSOURCECODE;//不同字符出现的次数intNUM;//不同字符出现的概率doub

4、lePROBABILITY;//哈夫曼编码符号intCode[MAX];intstart;//哈夫曼树的父结点intparent;//哈夫曼树的左右子结点intlchild;intrchild;//哈夫曼编码的长度intlengthofhuffmancode;}Hcode;HcodeINFORMATION[MAX];//该函数用来求信源所包含的符号，以及不同符号出现的次数和概率intPofeachsource(charinformationsource[MAX],inta){inti,j=1,m,flag=0;chartemp;//预先存入第一个字符，便于与后面的字符进

5、行比较//统计不同的字符存入结构体数组中//利用flag标签来标记每个字符是否出现过，若出现过标记为1，否则置为零INFORMATION[0].SOURCECODE=informationsource[0];for(i=1;i

6、TION[j].SOURCECODE='';printf("信源符号数为:%d",j);//统计相同的字符出现的次数//每做一个字符出现次数的统计都将结构体数组里的NUM置为零for(i=0;i

7、ATION[i].NUM/a;//将每个不同字符出现的次数概率都显示出来for(i=0;i