实验四 LZW编码方案程序设计

实验四LZW编码方案程序设计1、实验目的（1）进一步熟悉通用编码算法；（2）掌握C语言程序设计和调试过程中数值的进制转换、数值与字符串之间的转换等技术。2、实验要求（1）输入：本程序将从标准输入中读入待压缩的数据流；（2）输出：将压缩结果输出到标准输出上去。3、LZW算法描述1：procedureLZW2：字典初始化：将压缩文件中所有使用到的单字节字符放入字典中，为了压缩任何类型的文件，可以将字典的前256个位置（0x000到0x0FF）一次分配给0x00到0xFF的256个单字节字符。3：动态数据初始化：初始化新单词存放位置指针P。将它指向字典的第一个空位置。例如P=256（即0x100），读入被压缩文件的第一个字符cha，作为待处理单词W。单词的前缀Q为空，即Q=4095，尾字符就是cha，序号（码字）就是cha的序号。4：如果文件再没有字符了，输出当前单词的序号。编码结束。如果文件中还有字符，把当前单词W作为前缀，再从被压缩文件中读入一个字符CH，把CH作为尾字符，得到一个单词W1。5：如果字典中已有W1，则将W1看做当前单词W，返回第三步。如果字典中没有W1（发现一个新单词），先将原单词W的序号输出，再加新单词W1，增加到字典中，然后把刚刚读入的字符CH作为当前单词W，返回第三步。6:endprocedure*******************************************************************************实验流程图：*******************************************************************************4、参考代码/*********************************************************************Author:*Date:*Copyright:*Purpose：UseLZWalgorithmtocodethesourcesymbols***********************************************************#includestdio.h#includestdlib.h#includeconio.hstructword{unsignedintn;unsignedcharc;}w,wd[4096];//Dictionaryunsignedintp,n;unsignedcharh,m,l,f;/*Outputthecode*/voidout(intn){if(f==0){h=n/16;m=(n4)&0xf0;f=1;}else{m+=n/256;l=n&0xff;fputc(h,stdout);fputc(m,stdout);fputc(l,stdout);h=m=l=f=0;}}/*Maincopressprogram*/voidlzw(){intc,i;unsignedcharch;fprintf(stderr,\n\nbegincompress,pleasewait!\n);for(i=0;i256;i++){//Initializefirst256wordwd[i].n=4095;//indictionarywd[i].c=i;}p=256;w.n=4095;w.c=n=fgetc(stdin);h=m=l=f=0for(;;){c=fgect(stdin);if(c==-1){out(n);if(f)out(4095);fprintf(stderr,\n\ncompressionisover!\n);return;}ch=c;for(i=n+1;ip;i++){if(wd[i].n!=n)continue;if(wd[i].c==ch)break;}if(i!=p){w.n=n;w.c=ch;n=i;}else{out(n);if(p4095){wd[p].n=n;wd[p].c;p++;}w.n=4095;n=w.c=ch;}}}voidmain(void){lzw();}5改动后代码：#includestdio.h#includestring.h#includestdlib.h#includeiostreamusingnamespacestd;charwd[4096][20];//设定一个字典wdcharstr[20],w[20],w1[20],c[20];chartext[1000];//输入的文本textintN[1000];intnum;intM;intout(chars[])//得到一个短语是否在字典中，在时输出它的码字{inti;for(i=0;iM;i++)if(!strcmp(s,wd[i]))returni;//短语在字典中则返回ireturn-1;}voidadd(chars[])//将一个短语加入字典中{strcpy(wd[M++],s);将得到的短语加入词典}intmain(){inti,j,k;for(i=0;i256;i++)//将所有单个字符加入字典中，初始化字典{wd[i][0]=i;wd[i][1]='\0';}printf(请输入任意字符串，以回车键结束：\n\n);while(scanf(%s,text)!=EOF)//读入字符串{w[0]='\0';num=0;M=256;初始化词典for(i=0;;i++){if(text[i]=='\0')//字符串结尾处的处理{if(out(w)==-1)//如果短语不在词典中，加入词典，同时输出短语在词典中的序号add(w);N[num++]=out(w);break;//后继无词，中断}c[0]=text[i];c[1]='\0';//得到Cstrcpy(w1,w);strcat(w1,c);//W1=W+Ck=out(w1);if(k!=-1)//如果W1在字典中，W=W+C{strcpy(w,w1);continue;}else//如果W1不在字典中，W的编码加入编码码字中，将W+C加入字典中，W=C{N[num++]=out(w);add(w1);strcpy(w,c);}}printf(编码后的LZW码字:\n);for(i=0;inum;i++)//输出编码后的LZW码字printf(%d,N[i]);printf(\n\n);printf(加入字典中的短语:\n);for(i=256;iM;i++)//输出新加入字典中的短语printf(%s\n,wd[i]);//system(CLS);printf(请继续输入，停止输入请按Esc键\n\n);}return0;}实验结果输入数据：ababdabdcef查找asic码表得到，a—97b—98c—99d—100e—101f—102增加的新词有ab—256ba—257abd—258da—259abdc—260ce—261ef—262实验总结：通过lzw的实验了解lzw算法的具体工作原理，了解的lzw编码的具体编码方式和与其他编码的不同，利用字典的方式对每一个字符和短语进行编码，在对于较长字符，较多重复字符串的文本中有较高的编码效率