信息论课程设计报告(唯一可译码,lzw编码,算数编码)

1.判定唯一可译码2.LZw编码3.算数编码一判定唯一可译码1．任务说明输入：任意的一个码(即已知码字个数及每个具体的码字)输出：判决结果（是/不是）输入文件:in1.txt，含至少2组码，每组的结尾为”$”符输出文件:out1.txt，对每组码的判断结果说明：为了简化设计，可以假定码字为0，1串2．问题分析、实现原理、流程图参考算法伪代码：Forall,ijWWCdoifiW是jW的前缀then将相应的后缀作为一个尾随后缀放入集合0F中EndifEndforLoopForalliWCdoForalljnWFdoifiW是jW的前缀then将相应的后缀作为一个尾随后缀放入集合1nF中ElseifjW是iW的前缀then将相应的后缀作为一个尾随后缀放入集合1nF中EndifEndforEndforiiFFIf,iiWFWCthenReturnfalseElseifF中未出现新的元素thenReturntrueEndif//能走到这里，说明F中有新的元素出现，需继续Endloop3．实现源码#includeiostream#includestringusingnamespacestd;structstrings{char*string;structstrings*next;};structstringsFstr,*Fh,*FP;//输出当前集合voidoutputstr(strings*str){do{coutstr-stringendl;str=str-next;}while(str);coutendl;}inlineintMIN(inta,intb){returnab?b:a;}inlineintMAX(inta,intb){returnab?a:b;}#definelength_a(strlen(CP))#definelength_b(strlen(tempPtr))//判断一个码是否在一个码集合中，在则返回0，不在返回1intcomparing(strings*st_string,char*code){while(st_string-next){st_string=st_string-next;if(!strcmp(st_string-string,code))return0;}return1;}//判断两个码字是否一个是另一个的前缀，如果是则生成后缀码voidhouzhui(char*CP,char*tempPtr){if(!strcmp(CP,tempPtr)){cout集合C和集合F中有相同码字:endlCPendl不是唯一可译码码组!endl;exit(1);}if(!strncmp(CP,tempPtr,MIN(length_a,length_b))){structstrings*cp_temp;cp_temp=new(structstrings);cp_temp-next=NULL;cp_temp-string=newchar[abs(length_a-length_b)+1];char*longstr;longstr=(length_alength_b?CP:tempPtr);//将长度长的码赋给longstr//取出后缀for(intk=MIN(length_a,length_b);kMAX(length_a,length_b);k++)cp_temp-string[k-MIN(length_a,length_b)]=longstr[k];cp_temp-string[abs(length_a-length_b)]=NULL;//判断新生成的后缀码是否已在集合F里，不在则加入F集合if(comparing(Fh,cp_temp-string)){FP-next=cp_temp;FP=FP-next;}}}voidmain(){//功能提示和程序初始化准备cout\t\t唯一可译码的判断!\nendl;structstringsCstr,*Ch,*CP,*tempPtr;Ch=&Cstr;CP=Ch;Fh=&Fstr;FP=Fh;charc[]=C:;Ch-string=newchar[strlen(c)];strcpy(Ch-string,c);Ch-next=NULL;charf[]=F:;Fh-string=newchar[strlen(f)];strcpy(Fh-string,f);Fh-next=NULL;//输入待检测码的个数intCnum;cout输入待检测码的个数:;cinCnum;cout输入待检测码endl;for(inti=0;iCnum;i++){couti+1：;chartempstr[10];cintempstr;CP-next=new(structstrings);CP=CP-next;CP-string=newchar[strlen(tempstr)];strcpy(CP-string,tempstr);CP-next=NULL;}outputstr(Ch);CP=Ch;while(CP-next-next){CP=CP-next;tempPtr=CP;do{tempPtr=tempPtr-next;houzhui(CP-string,tempPtr-string);}while(tempPtr-next);}outputstr(Fh);structstrings*Fbegin,*Fend;Fend=Fh;while(1){if(Fend==FP){cout是唯一可译码码组!endl;exit(1);}Fbegin=Fend;Fend=FP;CP=Ch;while(CP-next){CP=CP-next;tempPtr=Fbegin;for(;;){tempPtr=tempPtr-next;houzhui(CP-string,tempPtr-string);if(tempPtr==Fend)break;}}outputstr(Fh);//输出F集合中全部元素}}4.运行结果：输入、输出及结果分析5．设计体会通过对判定唯一可译码算法的实现，我进一步了解判定唯一可译码缩的基本原理及过，体会到了其重要性,同时也锻炼了我独立分析问题以及解决问题的能力,这次课程设计让我深刻认识到了自己编程能力的不足，在以后的学习中要加强自己的编程能力。二LZw编码1.任务说明输入：由集合{a,b,c,d}内字符构成的输入串，输入序列长度L=100处理：先编码，再对编码结果译码输出：编码结果，译码结果输入文件:in4.txt，含至少两组输入，每组包含满足要求的串输出文件:out4.txt，对每组输入的编码和译码结果2.问题分析、实现原理、流程图实现原理：LZW就是通过建立一个字符串表,用较短的代码来表示较长的字符串来实现压缩.字符串和编码的对应关系是在压缩过程中动态生成的,并且隐含在压缩数据中,解压的时候根据表来进行恢复,算是一种无损压缩.在本次实验中我们就进行了LZW编码以及译码简单算法的编写。LZW编码又称字串表编码，是无损压缩技术改进后的压缩方法。它采用了一种先进的串表压缩，将每个第一次出现的串放在一个串表当中，用一个数字来表示串，压缩文件只进行数字的存贮，则不存贮串，从而使图像文件的压缩效率得到了较大的提高。LZW编码算法的原理是首先建立一个词典，即跟缀表。对于字符串流，我们要进行分析，从词典中寻找最长匹配串，即字符串P在词典中，而字符串P+后一个字符C不在词典中。此时，输出P对应的码字，将P+C放入词典中。编码参考算法：（以下为基于4叉树字典的伪代码，同学们可另外自行设计，参见教材P335）1.字典初始化：建一个初始的4叉树。该树的每个节点包含了字典序号信息。若字典序号非0，表示该节点对应的字典已建立。每个节点的儿子按顺序依次对应于输入字符a,b,c,d.根节点有4个儿子节点A、B、C、D，分别对应初始字典中的a,b,c,d，其对应的序号分别为1，2，3，4；而A、B、C、D节点均设4个儿子，其对应的序号设为0，对应的字典串分别为aa,ab,ac,ad;ba,bb,bc,bd;ca,cb,cc,cd;da,db,dc,dd建议：字典采用4叉树结构3.实现源码#includeiostream#includestring#includeiomanipusingnamespacestd;stringdic[30];intn;intfind(strings){inttemp=-1;for(inti=0;i30;i++){if(dic[i]==s)temp=i+1;}returntemp;}voidinit(){dic[0]=a;dic[1]=b;dic[2]=c;dic[3]=d;for(inti=4;i30;i++){dic[i]=;}}voidcode(stringstr){init();chartemp[2];temp[0]=str[0];temp[1]='\0';stringw=temp;inti=1;intj=3;cout\n编码为：;for(;;){chart[2];t[0]=str[i];t[1]='\0';stringk=t;if(k==){coutfind(w);break;}if(find(w+k)-1){w=w+k;i++;}else{coutfind(w);stringwk=w+k;dic[j++]=wk;w=k;i++;}}coutendl;for(i=0;ij;i++){coutsetw(45)i+1setw(12)dic[i]endl;}coutendl;}voiddecode(intc[]){init();intpw,cw;cw=c[0];intj=2;cout\n译码为：;coutdic[cw-1];for(inti=0;in-1;i++){pw=cw;cw=c[i+1];if(cw=j+1){coutdic[cw-1];chart[2];t[0]=dic[cw-1][0];t[1]='\0';stringk=t;j++;dic[j]=dic[pw-1]+k;}else{chart[2];t[0]=dic[pw-1][0];t[1]='\0';stringk=t;j++;dic[j]=dic[pw-1]+k;coutdic[cw-1];}}coutendl;for(inti=0;ij+1;i++){coutsetw(45)i+1setw(12)dic[i]endl;}coutendl;}voidmain(){stringstr;while(1){cout\n\n\ta.编码\tb.译码\n\n;cout请选择：;charcha;cincha;if(cha=='a'){cout\n输入要编码的字符串(由a,b,c,d组成)：;cinstr;code(str);}else{intc[30];cout\n消息序列长度是：;cinn;cout\n消息码字依次是：;for(inti=0;in;i++){cinc[i];}decode(c);}}}4.运行结果：输入、输出及结果分析5．设计体会在实验设计过程中，遇到的主要问题是对文件操作和字典的生成比较难,对于这个算法的编写我觉得设计难度比较大，因为长时间不用,对语言也有些生疏.。所以设计起来比较吃力。通过对LZW算法的实现，我进一步了解LZW算法进行数据压缩的基本原理及过程，体会到了其重要性，同时也锻炼了我独立分析问题以及解决问题的能力,这次课程设计让我深刻认识到了自己编程能力的不足，在以后的学习中要加强自己的编程能力。三算数编码1.任务说明要求：输入字符集为{a,b},且p