LZW编码实现实验报告.pdfVIP

LZW编码的C/C++编码实现实验报告 　LZW就是通过建立一个字符串表,用较短的代码来表示较长的字符串来实现压缩. 字符串和编码的对应 关系是在压缩过程中动态生成的,并且隐含在压缩数据中,解压的时候根据表来进行恢复,算是一种无损压 缩.在本次实验中我们就进行了LZW编码以及译码简单算法的编写。 LZW编码又称字串表编码，是无损压缩技术改进后的压缩方法。它采用了一种先进的串表压缩，将每个 第一次出现的串放在一个串表当中，用一个数字来表示串，压缩文件只进行数字的存贮，则不存贮串， 从而使图像文件的压缩效率得到了较大的提高。 LZW编码算法的原理是首先建立一个词典，即跟缀表。对于字符串流，我们要进行分析，从词典中寻找 最长匹配串，即字符串P在词典中，而字符串P+后一个字符C不在词典中。此时，输出P对应的码字，将 P+C放入词典中。经过老师的举例，我初步知道了对于一个字符串进行编码的过程。编码的部分算法如 下： 首先根据需要得建立一个初始化词典。这里字根分别为A B C。具体的初始化算法如下： void init()//词典初始化 { dic[0]=A; dic[1]=B; dic[2]=C;//字根为A,B,C for(int i=3;i30;i++)//其余为空 { dic[i]=; } } 对于编码算法的建立，则需先建立一个查找函数，用于查找返回序号： int find(string s) { int temp=-1; for(int i=0;i30;i++) { if(dic[i] s) temp=i+1; } return temp; } 接下来就可以编写编码算法了。 void code(string str) { init();//初始化 char temp[2]; temp[0]=str[0];//取第一个字符 temp[1]=\0; string w=temp; int i=1; int j=3;// 目前字典存储的最后一个位置 cout\n 编码为：; for(;;) { char t[2]; t[0]=str[i];//取下一字符 t[1]=\0; string k=t; if(k ) //为空，字符串结束 { cout find(w); break;//退出for循环,编码结束 } if(find(w+k)-1) { w=w+k; i++; } else { cout find(w); string wk=w+k; dic[j++]=wk; w=k; i++; } } coutendl; for(i=0;ij;i++) { coutsetw(45)i+1setw(12)dic[i]endl; } coutendl; } 译码是编码的逆过程。在译码中根缀表仍为A,B,C。且定义如下变量 StringP :前一步码字流 pW : StringP的第一个字符 StringC :当前的码字流 cW : StringC的第一个字符 结合老师给的前两步译码过程，得到译码算法如下： void decode(int c[]) { init(); int pw,cw; cw=c[0]; int j=2; cout\n 译码为：; coutdic[cw-1]; for(int i=0;in-1;i++) { pw=cw; cw=c[i+1]; if(cw=j+1) { coutdic[cw-1]; char t[2]; t[0]=dic[cw-1][0]; t[1]=\0; string k=t; j++; dic[j]=dic[pw-1]+k; } else { char t[2]; t[0]=dic[pw-1][0]; t[1]=\0; string k=t; j++; dic[j]=dic[pw-1]+k; coutdic[cw-1]; } } coutendl; for(i=0;ij+1;i++) { coutsetw(45)i+1setw(12)dic[i]endl; } coutendl; } 最后的主函数用菜单的方式编写：a.编码 b.译码。那么一个完整的LZW编码及译码的简单算法就大致可 以编写出来了。 在实验设计过程中,遇到的主要问题是对文件操作和字典的生成比较难,参考了相关书籍,和同学讨论后,才 对文件的操作及字典的生成有了了解,并主要用数组的形式生成字典.对于这个算法的编写我觉得设计难 度比较大,一方