信息论课程设计报告

1、判定唯一可译码LZw编码算数编码一判定唯一可译码1.任务说明输入：任意的一个码（即已知码字个数及每个具体的码字）输出：判决结果（是/不是）输入文件:in1.txt，含至少2组码，每组的结尾为"$"符输出文件：out1.txt,对每组码的判断结果说明：为了简化设计，可以假定码字为0,1串问题分析、实现原理、流程图参考算法伪代码：ForallW（,WjCdoifWi是W|的前缀then将相应的后缀作为一个尾随后缀放入集合F0中EndifEndforLoopForallWiCdoForallWFndoifWi是W的前缀then将相应的后缀作为一个尾随后缀放入集合Fn中中Elsei

2、fWj是Wi的前缀then将相应的后缀作为一个尾随后缀放入集合Fn中EndifEndforEndforF，UiFiIf-.W-F,W(三CthenReturnfalseElseifF中未出现新的元素thenReturntrueEndif能走到这里，说明F中有新的元素出现，需继续Endloop实现源码#include<iostream>#include<string>usingnamespacestd;structstringschar*string;structstrings*next;structstringsFstr,*Fh,*FP;输出当前集合voidoutput

3、str(strings*str)docout<<str->string<<endl;str=str->next;while(str);cout<<endl;inlineintMIN(inta,intb)returna>b?b:a;inlineintMAX(inta,intb)returna>b?a:b;#definelength_a(strlen(CP)#definelength_b(strlen(tempPtr)判断一个码&在一个码集合中，在则返回0,不在返回1intcomparing(strings*st_string,c

4、har*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中有相同码字："<<endl<<CP<<endl<<"不是唯一可译码码组!&quo

5、t;<<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=newcharabs(length_a-length_b)+1;char*longstr;longstr=(length_a>length_b?CP:tempPtr);府长度长的码赋给longstr取出后缀-for(intk=MIN(length_a,length_b);

6、k<MAX(length_a,length_b);k+)cp_temp->stringk-MIN(length_a,length_b)=longstrk;cp_temp->stringabs(length_a-length_b)=NULL;听断新生成的后缀码是否已在集合F里，不在则加入F集合if(comparing(Fh,cp_temp->string)(FP->next=cp_temp;FP=FP->next;voidmain()(功能提示和程序初始化准备cout<<"tt唯一可译码的判断！n"<<endl;st

7、ructstringsCstr,*Ch,*CP,*tempPtr;Ch=&Cstr;CP=Ch;Fh=&Fstr;FP=Fh;charc="C:"Ch->string=newcharstrlen(c);strcpy(Ch->string,c);Ch->next=NULL;charf="F:"Fh->string=newcharstrlen(f);strcpy(Fh->string,f);Fh->next=NULL;输入待检测码的个数intCnum;cout<<"输入待检测码的个数:

8、"cin>>Cnum;cout<<"输入待检测码"<<endl;for(inti=0;i<Cnum;i+)cout<<i+1<<":"chartempstr10;cin>>tempstr;CP->next=new(structstrings);CP=CP->next;CP->string=newcharstrlen(tempstr);strcpy(CP->string,tempstr);CP->next=NULL;outputstr(Ch

9、);CP=Ch;while(CP->next->next)CP=CP->next;tempPtr=CP;dotempPtr=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=C

10、h;while(CP->next)(CP=CP->next;tempPtr=Fbegin;for(;)(tempPtr=tempPtr->next;houzhui(CP->string,tempPtr->string);if(tempPtr=Fend)break;outputstr(Fh);输出F集合中全部元素运行结果：输入、输出及结果分析C:WIMD0WSsystem3Zcmd,tKe唯一可译码的判断?符枝拱码的十挣检洞词11011601F:101101集合饵口集舍F中有相同仍字，1位是雌一可译码码组，Prgsa，y虹ytocuntin眼一-一设计体会通过对判定

11、唯一可译码算法的实现，我进一步了解判定唯一可译码缩的基本原理及过，体会到了其重要性，同时也锻炼了我独立分析问题以及解决问题的能力这次课程设计让我深刻认识到了自己编程能力的不足，在以后的学习中要加强自己的编程能力。二LZw编码任务说明输入：由集合a,b,c,d内字符构成的输入串，输入序列长度L<=100处理：先编码，再对编码结果译码输出：编码结果，译码结果输入文件:in4.txt,含至少两组输入，每组包含满足要求的串1. 输出文件:out4.txt,对每组输入的编码和译码结果问题分析、实现原理、流程图实现原理：LZW就是通过建立一个字符申表，用较短的代码来表示较长的字符申来实现压缩.字符申

12、和编码的对应关系是在压缩过程中动态生成的，并且隐含在压缩数据中，解压的时候根据表来进行恢复，算是一种无损压缩.在本次实验中我们就进行了LZW编码以及译码简单算法的编写。LZW编码乂称字申表编码，是无损压缩技术改进后的压缩方法。它采用了一种先进的申表压缩，将每个第一次出现的申放在一个申表当中，用一个数字来表示申，压缩文件只进行数字的存贮，则不存贮申，从而使图像文件的压缩效率得到了较大的提高。LZW编码算法的原理是首先建立一个词典，即跟缀表。对于字符申流，我们要进行分析，从词典中寻找最长匹配申，即字符申P在词典中，而字符申P+后一个字符C不在词典中。此时，输出P对应的码字，将P+C放入词典中。编码

13、参考算法：（以下为基于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,对应的字典串分另U为aa,ab,ac,ad;ba,bb,bc,bd;ca,cb,cc,cd;da,db,dc,dd建议：字典采用4叉树结构实现源码#include<iostream&g

14、t;#include<string>#include<iomanip>usingnamespacestd;stringdic30;intn;intfind(strings)(inttemp=-1;for(inti=0;i<30;i+)(if(dici=s)temp=i+1;returntemp;voidinit()(dic0="a"dic1="b"dic2="c"dic3="d"for(inti=4;i<30;i+)(dici=""voidcode(strin

15、gstr)(init();chartemp2;temp0=str0;temp1='0'stringw=temp;inti=1;intj=3;cout<<"n编码为:"for(;)(chart2;t0=stri;t1='0'stringk=t;if(k="")(cout<<""<<find(w);break;if(find(w+k)>-1)(w=w+k;i+；else(cout«""«find(w);stringwk=w+k

16、;dicj+=wk;w=k;i+；cout«endl;for(i=0;i<j;i+)cout«setw(45)«i+1«setw(12)«dici<<endl;cout«endl;voiddecode(intc)init();intpw,cw;cw=c0;intj=2;cout«"n译码为：cout«diccw-1;for(inti=0;i<n-1;i+)pw=cw;cw=ci+1;if(cw<=j+1)(cout«diccw-1;chart2;t0=diccw-1

17、0;t1='0'stringk=t;j+；dicj=dicpw-1+k;elsechart2;t0=dicpw-10;t1='0'stringk=t;j+；dicj=dicpw-1+k;cout<<diccw-1;cout<<endl;for(inti=0;i<j+1;i+)cout<<setw(45)<<i+1<<setw(12)<<dici<<endl;cout<<endl;voidmain()stringstr;while(1)cout<<&q

18、uot;nnta.编码tb.译码nn"cout<<”请选择："charcha;cin>>cha;if(cha='a')cout<<"n输入要编码的字符申(由a,b,c,d组成):"cin>>str;code(str);elseintc30;cout<<"n消息序列长度是："cin>>n;cout<<"n消息码字依次是："for(inti=0;i<n;i+)cin>>ci;decode(c);运行结果

19、：输入、输出及结果分析时尊论谖程该H报皆kw#H5l£wDebugliw.eMej编码4译码请选择：-输入要编码的字符串由E4jd组成=aaabbbcccddd编码为*142638-11012345678910集不马b译码请选择，b消息序列长度是：B捎息码宇依次是W142638-110石马为*aaabbbcccfthcabbccaabbcab12345678910&编码b.译码请选序搜狗拼音半二设计体会在实验设计过程中，遇到的主要问题是对文件操作和字典的生成比较难，对丁这个算法的编写我觉得设计难度比较大，因为长时间不用，对语言也有些生疏.0所以设计起来比较吃力。通过对LZW算

20、法的实现，我进一步了解LZW算法进行数据压缩的基本原理及过程，体会到了其重要性，同时也锻炼了我独立分析问题以及解决问题的能力，这次课程设计让我深刻认识到了自己编程能力的不足，在以后的学习中要加强自己的编程能力。1. 三算数编码任务说明要求：输入字符集为a,b,且p(a)=1/4,p(2)=3/4.对长度L<=20的序列进行算术编码，并进行反向译码输入文件:in3.txt,含至少两组输入，每组为满足要求的申输出文件:out3.txt,对每组输入的编码和译码结果2. 参考算法：略问题分析、实现原理、流程图算术编码是把一个信源表示为实轴上0和1之间的一个区间，信源集合中的每一个元素都用来缩短这

21、个区间。算法流程输入信源符号个数，信源概率分布，还有需要编码的符号序列，根据概率可以算出初始编码间隔，High当前编码的上限，Low当前编码的下限，high中间变量，用来计算下一个编码符号的当前间隔的上限，low中间变量，用来计算下一个编码符号的当前间隔的下限，d当前间隔之间的距离。(1) 扫描需编码的符号序列，确定编码空间第1个编码符号的当前间隔为其初始的编码间隔，第i个编码符号的当前间隔为第i-1个编码后的Low,High),第i+1个编码符号的当前间隔算法如下：high=Low+d*第i+1个初始编码符号对应的上限，low=Low+d*第i+1个编码符号对应的下限，然后High=high

22、,Low=low,d=d*第i个编码符号的概率。实现源码#include<iostream>usingnamespacestd;#include"math.h"charS100,A10;floatP10,f10,gFs;/编码程序voidbianma(inta,inth)inti,j;floatfr;floatps=1;floatFs=0;floatSp100,b100,F100;以待编码的个数和字符个数为循环周期将待编码的字符所对应的概率存入到Fs中for(i=0;i<h;i+)for(j=0;j<a;j+)if(Si=Aj)Spi=Pj;fr=f

23、j；/将划分好的0,1)区间的对应点赋值给frFs=Fs+ps*fr;从选择的子区间中继续进行下一轮的分割。不断的进行这个过程直到所有符号编码完毕。ps*=Spi;/求Pscout<<"Fs="<<Fs<<endl;显示最终的算术编码gFs=Fs;floatl=log(float)1/ps)/log(float)2);/计算算术编码的码字长度lif(l>(int)l)l=(int)l+1;elsel=int(l);/将Fs转换成二进制的形式intd20;intm=0;while(l>m)Fs=2*Fs;if(Fs>1)F

24、s=Fs-1;dm=1;elseif(Fs<1)dm=0;elsedm=1;break;m+;intz=m;/解决有关算术编码的进位问题，给二进制数加if(m>=l)|(while(1)(dm-1=(dm-1+1)%2;最后位加if(dm-1=1)break;elsem-;cout<<"s="for(inte=0;e<z+1;e+)cout<<de;cout<<endl;解码程序voidjiema(inta,inth)(inti,j;floatFt,Pt;floatFs=0,Ps=1;for(i=0;i<h;i+)/以编码个数和符号个数为循环周期对其进行解码(for(intj=a-1