lzw编解码实验归纳总结报告含程序和注释.doc

《lzw编解码实验归纳总结报告含程序和注释.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、一、实验名称LZW编码及译码二、实验目的1、熟悉和巩固信息论课程中有关信源编码中LZW编码的原理、方法。2、会用VC调试和验证LZW编码译码程序，提高分析程序的能力3、将所学的理论知识进行上机实践。三、实验要求设计一个LZW编码/译码系统，掌握LZW编码的特点、存储方法和基本原理，培养利用C++语言编写程序以及调试程序的能力，运用信息论知识解决实际问题的能力。用C语言实现LZW编/译码的相关函数的基本框架设计，如LZW树的构建，LZW编码的实现，LZW译码的实现等。四、实验原理由韦尔奇在1984年开发的LZW算法，是LZ系列码中应用最

2、广泛、变形最多的。它是先建立初始字典，在分解输入流为短语词条，这个短语若不在初始字典中，就将其存入字典，这些新词条和初始字典共同构成编码器字典。而初始字典可由信源符号集构成，每一个符号是一个词条。1、编码原理：LZW编码器使用了一种很实用的分析(parsing)算法，称为贪婪分析算法(greedyparsingalgorithm)。在贪婪分析算法中，每一次分析都要串行地检查来自字符流(Charstream)的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀(Prefix)。用已知的前缀(Prefix)加上下

3、一个输入字符C也就是当前字符(Currentcharacter)作为该前缀的扩展字符，形成新的扩展字符串——缀-符串(String)：Prefix.C。这个新的缀-符串(String)是否要加到词典中，还要看词典中是否存有和它相同的缀-符串String。如果有，那么这个缀-符串(String)就变成前缀(Prefix)，继续输入新的字符，否则就把这个缀-符串(String)写到词典中生成一个新的前缀(Prefix)，并给一个代码。编码示例：被编码的字符串位置123456789字符ABBABABACLZW的编码过程步骤位置词典输出　　(

4、1)A　　　(2)B　　　(3)C　11(4)AB(1)22(5)BB(2)33(6)BA(2)44(7)ABA(4)56(8)ABAC(7)6------(3)2、解码原理：LZW译码算法中会用到另外两个术语：①当前码字(Currentcodeword)：指当前正在处理的码字，用cW表示，用string.cW表示当前缀-符串；②先前码字(Previouscodeword)：指先于当前码字的码字，用pW表示，用string.pW表示先前缀-符串。LZW译码算法开始时，译码词典与编码词典相同，它包含所有可能的前缀根(roots)。LZW

5、算法在译码过程中会记住先前码字(pW)，从码字流中读当前码字(cW)之后输出当前缀-符串string.cW，然后把用string.cW的第一个字符扩展的先前缀-符串string.pW添加到词典中。五、实验内容步骤及方案本实验主要有四个函数：1、编码函数：code()2、译码函数：decode()3、字典查找函数：find()4、字典初始化函数：init()LZW编码算法的具体执行步骤如下：步骤1：开始时的词典包含所有可能的根(Root)，而当前前缀P是空的；步骤2：当前字符(C)：=字符流中的下一个字符；步骤3：判断缀-符串P+C是否

6、在词典中(1)如果“是”：P：=P+C//(用C扩展P)；(2)如果“否”①把代表当前前缀P的码字输出到码字流;②把缀-符串P+C添加到词典;③令P：=C//(现在的P仅包含一个字符C);步骤4：判断码字流中是否还有码字要译(1)如果“是”，就返回到步骤2；(2)如果“否”①把代表当前前缀P的码字输出到码字流;②结束。LZW译码算法的具体执行步骤如下：步骤1：在开始译码时词典包含所有可能的前缀根(Root)。步骤2：cW：=码字流中的第一个码字。步骤3：输出当前缀-符串string.cW到码字流。步骤4：先前码字pW：=当前码字cW。

7、步骤5：当前码字cW：=码字流中的下一个码字。步骤6：判断先前缀-符串string.pW是否在词典中(1)如果“是”，则：①把先前缀-符串string.pW输出到字符流。②当前前缀P：=先前缀-符串string.pW。③当前字符C：=当前前缀-符串string.cW的第一个字符。④把缀-符串P+C添加到词典。(2)如果“否”，则：①当前前缀P：=先前缀-符串string.pW。②当前字符C：=当前缀-符串string.cW的第一个字符。③输出缀-符串P+C到字符流，然后把它添加到词典中。步骤7：判断码字流中是否还有码字要译(1)如果“

8、是”，就返回到步骤4。(2)如果“否”,结束。字典初始化操作：voidinit()//字典初始化{dic[0]="a";dic[1]="b";dic[2]="c";//为简单起见，将字典中的字根设置为a,b,c，即刚开始