信息论三种编码

《信息论》教师：李梅地球物理与信息技术学院07级电子信息工程2班赵凤阳LZW编码LZW压缩算法的基本原理：提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大小。看起来和调色板图象的实现原理差不多，但是应该注意到的是，我们这里的编译表不是事先创建好的，而是根据原始文件数据动态创建的，解码时还要从已编码的数据中还原出原来的编译表.LZW编码的流程图：LZW编码的源代码：#includestring.h#includestdio.hvoidcopy1(char*prefix,char*s,inti,intj){intk;for(k=0;k20;k++)《信息论》教师：李梅地球物理与信息技术学院07级电子信息工程2班赵凤阳prefix[k]=0;for(k=i;ki+j;k++)prefix[k-i]=s[k];}voidmain(){inti,j,k,n,t,m;chars[30],prefix[30],dic[20][30]={A,B,C},c[20];k=3;m=0;j=1;i=0;printf(“Pleaseinputsomewords:\n);gets(s);while(istrlen(s)){copy1(prefix,s,i,j);for(n=0;nk;n++){if(strcmp(prefix,dic[n])==0)//比较两字符串{j++;m=n;if((i+j)=strlen(s))copy1(prefix,s,i,j);elsestrcpy(prefix,);}}printf(“%d\n,m);if(strlen(prefix)!=0)//求字符串长度{strcpy(dic[k],prefix);//把后面的字符复给到前面printf(%s\n,dic[k]);}k=k+1;i=i+j-1;《信息论》教师：李梅地球物理与信息技术学院07级电子信息工程2班赵凤阳j=1;}getch();}实验结果：《信息论》教师：李梅地球物理与信息技术学院07级电子信息工程2班赵凤阳Huffman编码Huffman编码原理简介：霍夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。Huffman编码过程的几个步骤：l）将信号源的符号按照出现概率递减的顺序排列。2）将最下面的两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。3）重复进行步骤1和2直到概率相加的结果等于1为止。4）在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。5）记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符号的编码。Huffman编码源代码：#includestdio.h#includemath.h#definesy_max100#definesy_max230#definesy_max359#defineDEEP10/*定义sycode1类*/typedefstruct{floatweight;intflag;intfather;intleftchilde;intrightchilde;《信息论》教师：李梅地球物理与信息技术学院07级电子信息工程2班赵凤阳}sycode1;/*定义类sycode2类*/typedefstruct{intsy_array[sy_max2];intstart;}sycode2;intmain(void){sycode1sy1[sy_max3];sycode2sy2[sy_max2],cd;inti,j,x1,x2,n,c,p;floatm1,m2,temp,hx=0,KL=0;printf(pleaseinputthesignal'slength\n);scanf(%d,&n);/*根据输入长度，初始化编码变量*/for(i=0;i=2*n-1;i++){sy1[i].weight=0;sy1[i].father=0;sy1[i].flag=0;sy1[i].leftchilde=-1;sy1[i].rightchilde=-1;}printf(inputtheprobabilityforeverysignal:\n);/*根据输入长度，接收相应数目的概率数*/for(i=0;in;i++){printf(input%dthprobability:,i+1);scanf(%f,&temp);sy1[i].weight=temp;hx=hx-temp*3.332*log10(temp);}for(i=0;in-1;i++){m1=m2=sy_max;x1=x2=0;for(j=0;jn+i;j++)《信息论》教师：李梅地球物理与信息技术学院07级电子信息工程2班赵凤阳{if(sy1[j].weightm1&&sy1[j].flag==0){m2=m1;x2=x1;m1=sy1[j].weight;x1=j;}elseif(sy1[j].weightm2&&sy1[j].flag==0){m2=sy1[j].weight;x2=j;}}sy1[x1].father=n+i;sy1[x2].father=n+i;/*将找出的两棵子树合并为一棵子树*/sy1[x1].flag=1;sy1[x2].flag=1;sy1[n+i].weight=sy1[x1].weight+sy1[x2].weight;sy1[n+i].leftchilde=x1;sy1[n+i].rightchilde=x2;}for(i=0;in;i++){cd.start=n;c=i;p=sy1[c].father;while(p!=0)《信息论》教师：李梅地球物理与信息技术学院07级电子信息工程2班赵凤阳{if(sy1[p].leftchilde==c)cd.sy_array[cd.start]=1;elsecd.sy_array[cd.start]=0;cd.start=cd.start-1;c=p;p=sy1[p].father;}cd.start++;for(j=cd.start;j=n;j++){sy2[i].sy_array[j]=cd.sy_array[j];sy2[i].start=cd.start;}}printf(\nweight\thuffmancode\n);for(i=0;in;i++){printf(%2.3f:\t,sy1[i].weight);for(j=sy2[i].start;j=n;j++)printf(%d,sy2[i].sy_array[j]);/*计算平均码长以及信源熵*/KL=KL+(n-sy2[i].start+1)*sy1[i].weight;printf(\n);}printf(\nH(X)=%f\tKL=%f\nR=%f,hx,KL,hx/KL);getch();}实验结果：《信息论》教师：李梅地球物理与信息技术学院07级电子信息工程2班赵凤阳《信息论》教师：李梅地球物理与信息技术学院07级电子信息工程2班赵凤阳Shannon编码Shannon编码源代码#includestdio.h#includemath.h#includestdlib.h#definesy_CL10/*最大码长*/#definesy_PN100/*最大码数*/typedeffloatsy_type;typedefstructSHNODE{sy_typepb;sy_typesy_sum;intkl;intcode[sy_CL];structSHNODE*next;}sy_class;sy_typesym_arry[sy_PN];/*序列的概率*/intsy;/*定义全局变量sy代表码数也就是符号数*/voidsy_pb_scan(){inti;sy_typesum=0;printf(ThinkyouforusingthisShannonprogram!\nPleaseinputlength\n);scanf(%d,&sy);printf(input%dsignal'sprobability:\n,sy);printf();for(i=0;isy;i++){scanf(%f,&sym_arry[i]);sum=sum+sym_arry[i];}if(sum1.0001||sum0.99){printf(sum=%f,summust(0.999sum1.0001),sum);sy_pb_scan();《信息论》教师：李梅地球物理与信息技术学院07级电子信息工程2班赵凤阳}}/*定义函数sy_pb_scan()，输入数据，并且检验输入概率和是否等于1*/voidsy_sort(){inti,j,pos;sy_typemax;for(i=0;isy-1;i++){max=sym_arry[i];pos=i;for(j=i+1;jsy;j++)if(sym_arry[j]max){max=sym_arry[j];pos=j;}sym_arry[pos]=sym_arry[i];sym_arry[i]=max;}}/*定义函数sy_sort()，对输入概率进行由小到大排序*/voidvaluelist(sy_class*L){sy_class*head,*p;intj=0;inti;sy_typetemp,s;head=L;temp=0;p=head-next;while(jsy){p-sy_sum=temp;temp=temp+p-pb;p-kl=-3.322*log10(p-pb)+1;{s=p-sy_sum;for(i=0;ip-kl;i++)p-code[i]=0;for(i=0;ip-kl;i++){p-code[i]=2*s;《信息论》教师：李梅地球物理与信息技术学院07级电子信息工程2班赵凤阳if(2*s=1)s=2*s-1;elseif(2*s==0)break;elses=2*s;}}j++;p=p-next;}}/*算法函数*/voidcodedisp(sy_class*L){inti,j;sy_class*p;sy_typehx=0,KL=0;p=L-next;printf(num\tgailv\tsum\t-lb(p(ai))\tlenth\tcode\n);printf(\n);for(i=0;isy;i++){printf(a%d\t%1.3f\t%1.3f\t%f\t%d\t,i,p-pb,p-sy_sum,-3.332*log10(p-pb),p-kl);j=0;for(j=0;jp-kl;j++)printf(%d,p-code[j]);printf(\n);hx=hx-p-pb*3.332*log10(p-pb);/*计算信源序列的熵*/KL=KL+p-kl*p-pb;/*计算平均码字*/p=p-next;}printf(H(x)=%f\tKL=%f\nR=%fbit/code,hx,KL,hx/KL);《信息论》教师：李梅地球物理与信息技术学院07级电子信息工程2班赵凤阳/*计算编码效率*/}sy_class*setnull(){sy_class*head;head=(sy_class*)malloc(sizeof(sy_class));head-next=NULL;return(head);}sy_class*my_creat(sy_typea[],intn){sy_class*head,*p,*r;inti;head=setnull();r=head;for(i=0;in;i++){p=(sy_class*)malloc(sizeof(sy