词典编码-pic修改.ppt

实验二 词典编码 实验环境 VC++6.0或者Turbo C 实验目的 理解词典编码的思想。 掌握LZW算法。 实验内容与步骤 根据LZW算法原理对一段具体的字符进行编译。 在编码过程中写出流程图，以便充分理解LZW算法原理。 实验结果要求 LZW算法的编译码程序。 实验报告包括：对一段字符串编译码；编译码流程图；以及在编码过程中中遇到的问题、解决方法和本次实验心得体会。 LZW编码算法步骤 LZW编码举例 位置 1 2 3 4 5 6 7 8 9 字符 A B C A B A B A A 步骤 位置 码字 词典 输出 （1） A （2） B （3） C 1 1 （4） AB （1） 2 2 （5） BC （2） 3 3 （6） CA （3） 4 4 （7） ABA （4） 5 6 （8） ABAA （7） 6 —— —— —— （1） 输入数据流： 编码过程： LZW编码算法参考程序 LZW编码算法参考程序(续) LZW编码算法参考程序(续) /*扩展前缀*/ /*查找缀—符串是否在词典中*/ LZW编码算法参考程序(续) /*缀——符串不在词典中的情况*/ LZW译码算法 两个术语： 1.当前码字：当前正在处理的码字，cW表示当前码字，string.cW表示当前缀-符串 2.先前码字：先于当前码字的码字，用pW表示，string.pW表示先前缀-符串 LZW译码算法：先记住先前码字(pW)，从码字流中读当前码字(cW)之后输出当前缀-符串string.cW，然后把用string.cW的第一个字符扩展的先前缀-符串string.pW添加到词典中。 LZW译码算法 LZW译码举例 步骤 输入码字 词典 输出 码字 字串 （1） A （2） B （3） C 1 （1） —— —— A 2 （2） （4） AB B 3 （3） （5） BC C 4 （4） （6） CA AB 5 （7） （7） ABA ABA 6 （1） （8） ABAA A 译码过程： 译码算法参考程序 译码算法参考程序(续) /*K-输入码字的个数*/ 译码算法参考程序(续) 译码算法参考程序(续) 译码算法参考程序(续) /*当前缀—符串不在词典中的情况*/ /*输出词典中的项*/