信息论三种编码

1、精选优质文档-倾情为你奉上LZW编码LZW压缩算法的基本原理：提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大小。看起来和调色板图象的实现原理差不多，但是应该注意到的是，我们这里的编译表不是事先创建好的，而是根据原始文件数据动态创建的，解码时还要从已编码的数据中还原出原来的编译表.LZW编码的流程图：LZW编码的源代码：#include<string.h>#include<stdio.h>void copy1(char *prefix,char *s,int i,int j) in

2、t k; for(k=0;k<20;k+) prefixk=0; for(k=i;k<i+j;k+) prefixk-i=sk; void main()int i ,j,k,n,t,m;char s30,prefix30,dic2030="A","B","C",c20;k=3;m=0;j=1;i=0;printf(“Please input some words:n");gets(s);while(i<strlen(s) copy1(prefix,s,i,j); for(n=0;n<k;n+) if(

3、strcmp(prefix,dicn)=0) /比较两字符串 j+; m=n; if( (i+j)<=strlen(s) ) copy1(prefix,s,i,j);else strcpy(prefix,""); printf(“%dn",m); if(strlen(prefix)!=0)/求字符串长度 strcpy(dick,prefix);/把后面的字符复给到前面 printf("%sn",dick); k=k+1; i=i+j-1; j=1; getch();实验结果：Huffman编码Huffman编码原理简介： 

4、60;  霍夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。Huffman编码过程的几个步骤：l）将信号源的符号按照出现概率递减的顺序排列。2）将最下面的两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。3）重复进行步骤1和2直到概率相加的结果等于1为止。4）在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。5）记录下概率为1处到当前信号源符号之间的0，l序列，

5、从而得到每个符号的编码。Huffman编码源代码：#include <stdio.h>#include <math.h>#define sy_max 100#define sy_max2 30#define sy_max3 59#define DEEP 10 /*定义sycode1类*/typedef struct float weight; int flag;int father;int leftchilde;int rightchilde;sycode1; /*定义类sycode2类*/typedef struct int sy_arraysy_max2;int s

6、tart;sycode2;int main(void) sycode1 sy1sy_max3; sycode2 sy2sy_max2,cd; int i,j,x1,x2,n,c,p; float m1,m2,temp,hx=0,KL=0; printf("please input the signal's lengthn"); scanf("%d",&n); /*根据输入长度，初始化编码变量*/ for(i=0;i<=2*n-1;i+) sy1i.weight=0; sy1i.father=0; sy1i.flag=0; sy1i.

7、leftchilde=-1; sy1i.rightchilde=-1; printf("input the probability for every signal:n");/*根据输入长度，接收相应数目的概率数*/ for(i=0;i<n;i+) printf("input %dth probability:",i+1); scanf("%f",&temp); sy1i.weight=temp; hx=hx-temp*3.332*log10(temp); for(i=0;i<n-1;i+) m1=m2=sy_ma

8、x; x1=x2=0; for(j=0;j<n+i;j+) if(sy1j.weight<m1&&sy1j.flag=0) m2=m1; x2=x1; m1=sy1j.weight; x1=j; else if(sy1j.weight<m2&&sy1j.flag=0) m2=sy1j.weight; x2=j; sy1x1.father=n+i; sy1x2.father=n+i; /*将找出的两棵子树合并为一棵子树*/ sy1x1.flag=1; sy1x2.flag=1; sy1n+i.weight=sy1x1.weight+sy1x2.w

9、eight; sy1n+i.leftchilde=x1; sy1n+i.rightchilde=x2; for(i=0;i<n;i+) cd.start=n; c=i; p=sy1c.father; while(p!=0) if(sy1p.leftchilde=c) cd.sy_arraycd.start=1; else cd.sy_arraycd.start=0; cd.start=cd.start-1; c=p; p=sy1p.father; cd.start+; for(j=cd.start;j<=n;j+) sy2i.sy_arrayj=cd.sy_arrayj; sy2i

10、.start=cd.start; printf("nweightthuffmancoden"); for(i=0;i<n;i+) printf("%2.3f:t",sy1i.weight); for(j=sy2i.start;j<=n;j+) printf("%d",sy2i.sy_arrayj);/*计算平均码长以及信源熵*/ KL=KL+(n-sy2i.start+1)*sy1i.weight; printf("n"); printf("nH(X)=%ftKL=%fnR=%f",

11、hx,KL,hx/KL);getch();实验结果：Shannon编码Shannon编码源代码#include <stdio.h>#include <math.h>#include <stdlib.h>#define sy_CL 10 /*最大码长*/#define sy_PN 100 /*最大码数*/typedef float sy_type;typedef struct SHNODE sy_type pb;sy_type sy_sum;int kl;int codesy_CL;struct SHNODE *next;sy_class;sy_type sy

12、m_arrysy_PN; /*序列的概率*/int sy; /*定义全局变量sy代表码数也就是符号数*/void sy_pb_scan() int i;sy_type sum=0;printf("Think you for using this Shannon program!nPlease input lengthn");scanf("%d",&sy);printf("input%dsignal's probability:n",sy);printf(">>");for(i=0;i&l

13、t;sy;i+)scanf("%f",&sym_arryi);sum=sum+sym_arryi;if(sum>1.0001|sum<0.99) printf("sum=%f,sum must(<0.999<sum<1.0001)",sum);sy_pb_scan(); /*定义函数sy_pb_scan()，输入数据，并且检验输入概率和是否等于1*/void sy_sort() int i,j,pos;sy_type max;for(i=0;i<sy-1;i+)max=sym_arryi;pos=i;for(j

14、=i+1;j<sy;j+)if(sym_arryj>max)max=sym_arryj;pos=j;sym_arrypos=sym_arryi;sym_arryi=max; /*定义函数sy_sort()，对输入概率进行由小到大排序*/void valuelist(sy_class *L)sy_class *head,*p;int j=0;int i;sy_type temp,s;head=L; temp=0;p=head->next;while(j<sy)p->sy_sum=temp;temp=temp+p->pb;p->kl=-3.322*log1

15、0(p->pb)+1;s=p->sy_sum;for(i=0;i<p->kl;i+)p->codei=0;for(i=0;i<p->kl;i+)p->codei=2*s;if(2*s>=1)s=2*s-1;else if(2*s=0)break;else s=2*s;j+;p=p->next; /*算法函数*/void codedisp(sy_class *L) int i,j; sy_class *p; sy_type hx=0,KL=0; p=L->next; printf("numtgailvtsumt-lb(p

16、(ai)tlenthtcoden"); printf("n"); for(i=0;i<sy;i+)printf("a%dt%1.3ft%1.3ft%ft%dt",i,p->pb,p->sy_sum,-3.332*log10(p->pb),p->kl); j=0; for(j=0;j<p->kl;j+) printf("%d",p->codej); printf("n"); hx=hx-p->pb*3.332*log10(p->pb); /*计算信

17、源序列的熵*/ KL=KL+p->kl*p->pb; /*计算平均码字*/ p=p->next; printf("H(x)=%ftKL=%fnR=%fbit/code",hx,KL,hx/KL); /*计算编码效率*/sy_class *setnull() sy_class *head; head=(sy_class *)malloc(sizeof(sy_class); head->next=NULL; return(head);sy_class *my_creat(sy_type a,int n) sy_class *head,*p,*r; int i; head=setnull(); r=head