信源编码--------霍夫曼编码.doc

实验二 信源编码-霍夫曼编码1. 掌握信息熵的定义、性质和计算；2. 掌握平均码字长度和编码效率的计算；3 掌握霍夫曼编码的原理；4 熟练掌握二进制霍夫曼码的编码步骤；5 正确使用C语言实现霍夫曼编码。二、实验内容1. 熟练画出霍夫曼编码图，正确求出字符串的二进制霍夫曼编码；2. 用C语言正确编程，实现霍夫曼编码、解码，并在Visual C+环境中验证。三、 实验原理1. 霍夫曼编码的基本原理按照概率大小顺序排列信源符号，并设法按逆顺序分配码字字长，使编码的码字为可辨识的。2. 平均码长：L=p(si)*li （单位为：码符号/信源符号）其中，p(si)为信源si在q个信源中出现的概率，li为信源si的二进制霍夫曼编码。3. 信息熵：H(S)=- p(si) *log2 p(si) （单位为：比特/信源符号）其中，p(si)为信源si在q个信源中出现的概率。4. 编码效率：= H(S)/ L其中，H(S)为信息熵，L为平均码长。四、 实验步骤：1. 将q个信源符号按概率分布的大小，以递减次序排列起来，设 2. 用“0”和“1”码符号分别代表概率最小的两个信源符号，并将这两个概率最小的符号合并成一个符号，合并的符号概率为两个符号概率之和，从而得到只包含q-1个符号的新信源，称为缩减信源。 3. 把缩减信源的符号仍旧按概率大小以递减次序排列，再将其概率最小的两个信源符号分别用“0”和“1”表示，并将其合并成一个符号，概率为两符号概率之和，这样又形成了 q 2 个符号的缩减信源。4. 依此继续下去，直至信源只剩下两个符号为止。将这最后两个信源符号分别用“0”和“1”表示。5. 然后从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即对应的码字。/* 霍夫曼编码 */2010-3-31：注释/程序共有8处需要补充#include#include#include#define n 100#define m 2*n-1/ 码结点的存储结构typedef structchar ch;char bits9;int len;CodeNode;typedef CodeNode HuffmanCoden+1;/ 树结点的存储结构typedef structint weight;int lchild,rchild,parent;HTNode;typedef HTNode HuffmanTreem+1;int num;/ 挑选权值最小的两个结点void select(HuffmanTree HT, int k, int &s1, int &s2) int i,j;int minl=32767;for(i=1;i=k;i+)if(HTi.weightminl&HTi.parent=0) j=i; minl=HTi.weight;s1=j;minl=32767;for(i=1;i=k;i+)if(HTi.weightminl&HTi.parent=0&i!=s1) j=i; minl=HTi.weight;s2=j;/ 统计输入字符串st中出现的字符种类和各个字符在该字符串中出现的次数，/ 出现的字符存放在str数组中，各个字符在该字符串中出现的次数存放在/ cnt数组中，返回字符串st中字符种类数。int jsq(char *s, int cnt, char str) char*p;int i,j,k=0;int temp257;for(i=0;i257;i+) tempi=0;for(p=s;*p!=0;p+)temp*p+;/程序补充处1：统计字符串中指针p所指向的字符出现的次数，次数保存在数/组元素temp*p中for(i=0,j=0;i=256;i+) if(tempi!=0) j+;strj=i;cntj=tempi;/程序补充处2：将字符串中各字符按其在ASCII码表中位置依次存放在数组元/素strj中，并将其在该字符串中出现的次数存放在数组元素cntj中 num=j;return j;/ 建立霍夫曼树void chuffmanTree(HuffmanTree &HT, HuffmanCode &HC, int cnt, char str)int i,s1,s2;for(i=1;i=2*num-1;i+) HTi.lchild=0; HTi.rchild=0; HTi.parent=0; HTi.weight=0;for(i=1;i=num;i+)HTi.weight=cnti;/程序补充处3：将霍夫曼树中各叶子节点的权值HTi.weight设置为该字符在/字符串中出现的次数cnti for(i=num+1;i=2*num-1;i+) select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTi.weight;/程序补充处4：将调用select函数得到的两个权值最小的结点s1和s2合并，产生/一个新结点i，（1）设置结点s1的父结点为结点i；（2）设置结点s2的父结点/为结点i；（3）设置结点i的左子结点为结点s1；（4）设置结点i的右子结点为/结点s2；（5）结点i的权值为结点s1和s2权值之和for(i=1;i=num;i+) HCi.ch=stri;/ 给霍夫曼树的每个叶子结点分配二进制码void HuffmanEncoding(HuffmanTree HT, HuffmanCode HC) int c,p,i;char cdn;int start;cdnum=0;for(i=1;i0) start-; cdstart=(HTp.lchild=c)?0:1; c=p; strcpy(HCi.bits,&cdstart); HCi.len=strlen(HCi.bits);/程序补充处5：求取每个叶子节点的霍夫曼二进制编码的码长HCi.len / 译码void decode(HuffmanCode HC,char receive, char s) char str268;char cd9;int i,j,k=0,p=0,cjs;while(receivep!=0) cjs=0; for(i=0;inum&cjs=0&receivep!=0;i+) cdi= ; cdi+1=0; cdi=receivep+; for(j=1;j=num;j+)/程序补充处8：补充下述if语句的条件：要求利用strcmp函数对HCj.bits/和cd进行比较，当二者相等时执行后述大括号中语句/strcmp函数：当进行比较的两个字符串相当时，函数返回值为0 if(!strcmp(HCj.bits,cd) strk=HCj.ch; k+; cjs=1; break; strk=0;strcpy(s,str);/ 输出字符串的二进制编码void coding(HuffmanCode HC, char str,char get) int i,j=0;char k=0;while(strj!=0) for(i=1;i=num;i+) if(HCi.ch=strj) strcat(get,HCi.bits); break; j+;strcat(get,&k);/程序补充处6：用函数strcat将get数组的末尾处加上字符串结束标志0/ 计算编码效率double code_ratio(char st,int cn,HuffmanCode HC)double up=0.0,down=0.0,temp=0.0;int i=1,len=strlen(st);for(i;i=num;i+)/程序补充处7：计算单个字符在字符串中出现的概率temp temp=cni/len; up-=temp*(log(temp)/log(2); down+=temp*HCi.len;return (up/down)*100;/主函数void main()char str257; / str用于在统计输入序列中的字符时用，存放是什么字符，1到256char st10000,s10000; / st用来接受输入的字符串，s用来接受解压的字符串int cn257; / cn用于接受统计后的每个字符的频率，1到256HuffmanTree HT;HuffmanCode HC;printf(输入要编码的字符串：);scanf(%s,&st);/ 统计输入字符串st中出现的字符种类和各个字符在该字符串中出现的次数，/ 出现的字符存放在str数组中，各个字符在该字符串中出现的次数存放在/ cn数组中，num为字符串st中字符种类数。num=jsq(st,cn,str); / 在str数组中最后一个字符的后面加上一个字符串结束标志0 strnum+1=0;chuffmanTree(HT,HC,cn,str); / 建立霍夫曼树HuffmanEncoding(HT,HC); / 根据霍夫曼树建立霍夫曼编码printf(共有%d种符号n,num);for(int i=1;i=num;i+)printf(字符%c次数为%d,编码为%sn,HCi.ch,cni,HCi.bits);char get10000;get0=0;coding(HC,st,get);printf(上述字符串的霍夫曼码为%sn,get);printf(编码效率为%f%n,code_ratio(st,cn,HC);printf(输入二进制码开始译码：);char receive10000;scanf(%s,&receive);