LZ编码实验报告.doc

北京邮电大学实验报告 题目：LZ78压缩编码与译码 专业：信息工程 小组成员（学号）： 赵乙麟（2011210714） 周丽玲（2011210715） 马睿超（2011210691） 一、实验目的 熟悉LZ编码的基本思想，运用LZ算法编写具体程序，实现文本数据压缩与解压缩明白其中字典建立的过程是整个编码的核心。 实验环境 MATLAB 三、实验流程 编码算法： ① 输出与当前前缀P相对应的码字和当前字符Char； ② 把字符串P+Char 添加到词典中。 ③ 令P :=空值。 (3) 判断字符流中是否还有字符需要编码 ① 如果是：返回到步骤2。 ② 如果否：若当前前缀P不空，输出相应于当前前缀P的码字，结束编码。 流程图如下： 2、译码算法： 1) 如果有，返回步骤2 (2) 如果没有，则结束 流程图如下： 四、实验结果分析 说明： 实验代码主要分为LZ压缩编码（LZEncode.m）、解压缩（LZDecode.m）、生成字典（wrdictionary.m）、分析（LZanalysis.m）四部分内容。 压缩编码完成对输入文本的LZ算法压缩，生成字典和编码，统计输入文本信息长度和输出的压缩文件的编码长度，并计算出压缩率； 解压缩部分编码完成对字典的查找、译码还原出原输入的文本； 生成字典部分代码将输入文本编码并生成字典，保存在dictionary.m文件中，方便随时查看； 分析部分代码完成对一次压缩解压缩过程的分析，给出压缩率、误码率、信源熵等参数，便于综合分析。 、输入很短的信源short.txt，分析如下： 信源如图： 压缩编码后生成short1.txt： 生成字典dictionary.m： 译码后生成short2.txt，对比原文件可以看出译码成功且无误码： 整个过程在matlab程序执行过程如下： 由整个过程可得到以下数据与结论： 输入信息长度84、输出编码长度92，压缩率1.0952,； 译码差错为0，说明在无噪声干扰的情况下，编译码执行正确； 信源熵为3.2698； 对于较短的信源，LZ编码并不能实现信源的压缩，相反编码长度反而大于信源长度，因此，LZ编码并不适用于短信息的编码。 、输入较长的信源long.txt，分析如下： 运行截图： 分析如下： 对于较长的信源，压缩比有所降低，压缩效果逐渐有所体现，说明LZ编码的压缩功能在信源很长时的效果更加明显。 查看信源熵和译码后的错误率： 、输入给定文本PAP.txt，分析如下： 程序运行过程，由于给定文本较长，因此压缩时间较慢，压缩生成pap1.txt： 生成字典及译码生成pap2.txt： 查看分析： 原文件与译码后还原文件对比，无差错，编译码成功： 由以上结果可得到如下结论： 对于较长的文章压缩时间较久，说明程序效率还有待提高； 压缩比为1.0211，信源熵为4.3581，对于此长信源依旧没有压缩效果。 、输入相关性较强的信源regular.txt，分析如下： 原信源内容： 编码结果： 原文件和译码还原文件对比，无误码： 分析以上结果可知：当信源的相关性较强时，LZ编码的压缩效果更明显，因此可以得出结论，LZ编码适用于相关性较强且篇幅较强的文本压缩。 、分析各组信源熵和压缩效率之间的关系： 压缩比 1.0952 0.9949 1.0211 0.6748 信源熵 3.2698 4.0168 4.3581 4.0824 表格说明LZ编码与信源的统计特性无关，当编码长度充分大时，错误概率可以任意小，这也是LZ编码的优势所在，因为在实际应用中，确切的获得信源统计特性有时是非常困难的，一旦信源的实际分布与假设分布有差异，编码性能会急剧下降，而LZ编码克服了这一点。因此在实际应用中使用广泛。 五、实验中遇到的问题与解决办法 1、由于代码的原型是在网上找的，因此代码中存在很多问题，甚至是一些简单的格式错误，都需要耐心仔细的纠正，才能使代码正确编译执行。 2、实验中发现，原代码只能按行读取文件内容进行编码，这就导致文章中如果出现换行，编码就会停止，译码也只能还原出换行之前的文章内容，检查代码发现这是由于fgets函数和fread函数使用不当，fgets函数是按行读取的，因此应该使用fread函数，同时还要使用reshape函数将原文转换成文本矩阵格式。 3、实验中发现在统计误码率时，误码率始终是1，检查发现这是因为译码后的文章和译码前的原文已经转换成了文本矩阵的格式，因此无法使用strcmp函数进行字符