实验二唯一可译码判决准则

湖南大学信息科学与工程学院实验报告实验名称唯一可译码判决准则课程名称信息论与编码1、实验目的（1）进一步熟悉唯一可译码判决准则；（2）掌握C语言字符串处理程序的设计和调试技术。2、实验要求（1）已知：信源符号个数q、码字集合C。（2）输入：任意的一个码。码字个数和每个具体的码字在运行时从键盘输入。（3）输出：判决（是唯一可译码/不是唯一可译码）。3、算法的流程输入码字集合X0for所有Wi，Wj∈X0if码字Wi是码字Wj的前缀，即将相应的后缀作为一个尾随后缀放入新集合X1endifendforfor所有Wi∈X0for所有Wj∈Xn－1ifWi是Wj的前缀，即将相应的后缀作为一个尾随后缀放入新集合Xn中elseifWj是Wi的前缀，即将相应的后缀作为一个尾随后缀放入新集合Xn中endifendforendfor构造尾随后缀集合X←Xiif有码字Wi∈X0，Wi∈X，则非唯一可译码4、算法的程序#includeiostream.h#includestdlib.h#includestring.hstructstrings{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集合中全部元素}}运行结果5、实验总结唯一可译码定义为：码的任意N次扩展码都是非奇异码。通过Kraft不等式得到了存在唯一可译码的充要条件。给定了信源以及码符号集后，从所有唯一可译码中寻找出平均码长最小的码（最佳码），即是信源编码的主要目的。在找最佳码之前，对码字进行唯一可译码的判决还是很有必要的。