南京理工大学多媒体实验报告

1、无损数据压缩实验报告 级: 号: 名: 2012年1月10日 LZW 算法压缩编码技术 1. 设计思路 ： LZW就是通过建立一个字符串表 ，用较短的代码来表示较长的 字符串来实现压缩 . 字符串和编码的对应关系是在压缩过程中 动态生成的 , 并且隐含在压缩数据中 , 解压的时候根据表来进行 恢复,是一种无损压缩.在本次实验中我们就进行了 LZW编码以及 译码简单算法的编写。 LZW编码又称字串表编码，是无损压缩技术改进后的压缩方法。 它采用了一种先进的串表压缩，将每个第一次出现的串放在一个串 表当中，用一个数字来表示串，压缩文件只进行数字的存贮，则不 存贮串，从而使图像文件的压缩效率得到了较

2、大的提高。 LZW 压缩算法的基本原理：提取原始文本文件数据中的不同字 符，基于这些字符创建一个编译表，然后用编译表中的字符的索 引来替代原始文本文件数据中的相应字符，减少原始数据大小。 应该注意到的是，这里的编译表不是事先创建好的，而是根据原 始文件数据动态创建的，解码时还要从已编码的数据中还原出原 来的编译表 . 对于字符串流，我们要进行分析，从词典中寻找最长 匹配串，即字符串P在词典中，而字符串P+后一个字符C不在词 典中。此时，输出P对应的码字，将P+C放入词典中。经过努力, 我初步知道了对于一个字符串进行编码的过程。 2.步骤 (1)根据需要得建立一个初始化词典。这里字根分别为A B

3、 C。具体的初始 化算法如下： void init()/ 词典初始化 dic0=A; dic1=B; dic2=C;/ 字根为 A,B,C for(int i=3;i30;i+)/ 其余为空 dici=; (2) 对于编码算法的建立，则需先建立一个查找函数，用于查找返回序号： int find(string s) int temp=-1; for(int i=0;i30;i+) if(dici=s) temp=i+1; (3) return temp; 编写编码算法 : void code(string str) int();/ 初始化 char temp2; temp0=str0;/ 取第一

4、个字符 temp1=0; string w=temp; int i=1; int j=3;/ 目前字典存储的最后一个位置 coutn 编码为： ; for(;) 取下一字符 char t2; t0=stri;/ t1=0; string k=t; if(k=) / 为空，字符串结束 cout -1) w=w+k; i+; else cout find(w); string wk=w+k; dicj+=wk; w=k; i+; coutendl; for(i=0;ij;i+) coutsetw(45)i+1setw(12)diciendl; coutendl; (4) 译码是编码的逆过程。在译码

5、中根缀表仍为 A,B,C 。且定义如下变量 StringP : 前一步码字流 pW : StringP 的第一个字符 StringC : 当前的码字流 cW : StringC 的第一个字符 结合老师给的前两步译码过程，得到译码算法如下： void decode(int c) init(); int pw,cw; cw=c0; H. int j=2; coutn 译码为： coutdiccw-1; for(int i=0;in-1;i+) pw=cw; cw=ci+1; if(cw=j+1) coutdiccw-1; char t2; t0=diccw-10; t1=0; string k=t

6、; j+; dicj=dicpw-1+k; else char t2; t0=dicpw-10; t1=0; string k=t; j+; dicj=dicpw-1+k; coutdiccw-1; coutendl; for(i=0;ij+1;i+) coutsetw(45)i+1setw(12)diciendl; coutendl; (5) 最后的主函数用菜单的方式编写： a. 编码 b. 译码。 3. 程序源代码： #include #include #include using namespace std; string dic30; int n; int find(string s)

7、 int temp=-1; for(int i=0;i30;i+) if(dici=s) temp=i+1; return temp; void init() dic0=A; dic1=B; dic2=C; for(int i=3;i30;i+) dici=; void code(string str) init();/ 初始化 char temp2; temp0=str0; temp1=0; string w=temp; int i=1; int j=3; H. coutn 编码为： for(;) char t2; t0=stri; t1=0; string k=t; if(k=) cout

8、 -1) w=w+k; i+; else cout find(w); string wk=w+k; dicj+=wk; w=k; i+; coutendl; for(i=0;ij;i+) coutsetw(45)i+1setw(12)diciendl; coutendl; void decode(int c) init(); int pw,cw; cw=c0; int j=2; H. coutn 译码为： coutdiccw-1; for(int i=0;in-1;i+) pw=cw; cw=ci+1; if(cw=j+1) coutdiccw-1; char t2; t0=diccw-10;

9、 t1=0; string k=t; j+; dicj=dicpw-1+k; else char t2; t0=dicpw-10; t1=0; string k=t; j+; dicj=dicpw-1+k; coutdiccw-1; coutendl; for(i=0;ij+1;i+) coutsetw(45)i+1setw(12)diciendl; coutendl; void main() string str; while(1) coutnnt1. 编码 t2. 译码 nn; coutcha; if(cha=1) coutstr; code(str); else 输入要编码的字符串（由A

10、、B C组成）：; int c30; coutn; coutn for(int i=0;ici; decode(c); 消息码字依次是： H. 4.设计截图 uoU 4in() ttrlik) ftr; cK逢弘 cMr ch4； ClAEh： Iffctia Z 薛为，i 3 Ml tn AC cc cs cotnSi入臭由 C clntr; coil(stri; 狗 * 译衿 Int cl； UMCA啪刊feJtt，- cifl” ： cout-n8.W?RX.- format l-：l) 4C04(C； C: Doc use nts “nd =)110200208创天中文VC111102

11、00208. cppj ELJ 厂19:04 译 A W； SfeSff I Sfexft 2iBM/ niO2002Ce NdMI桶宾电 f lU030020e J 送晋鉴=JC：Pocf 8 ond S讥tin”八加t3桌面lebuR卫釦 a序列长K*, 6 t 2 I 3 , 9 力，B*cnc I 勢 2停 i.SBW anioaooace.功ai科矣hojccss. *t*s - ffiffl 15:09 5.心得体会 ： 这次设计，刚开始的时候感觉无从下手，因为对 LZW 算法的 不熟悉，总感觉压缩与解压是一个很深奥的东西。 但是通过自己不懈 的努力和同学的帮助，最终我还是完成了实验。 对于我来说， 收获最大的是方法和能力；