LZ编码实验报告.docVIP

北京邮电大学实验报告 题目：LZ78压缩编码与译码 专业：信息工程 小组成员（学号）： 赵乙麟（2011210714） 周丽玲（2011210715） 马睿超（2011210691） 一、实验目的与任务 熟悉LZ编码的基本思想，运用LZ算法编写具体程序，实现文本的无损数据压缩与解压缩，明白其中字典建立的过程是整个编码的核心。 实验环境 MATLAB 三、实验流程 编码算法： 步骤1： 在开始时，词典和当前前缀P 都是空的。 步骤2： 当前字符Char :=字符流中的下一个字符。 步骤3： 判断P+Char是否在词典中： (1) 如果是：用Char扩展P，让P := P+Char ； (2) 如果否： ① 输出与当前前缀P相对应的码字和当前字符Char； ② 把字符串P+Char 添加到词典中。 ③ 令P :=空值。 (3) 判断字符流中是否还有字符需要编码 ① 如果是：返回到步骤2。 ② 如果否：若当前前缀P不空，输出相应于当前前缀P的码字，结束编码。 流程图如下： 2、译码算法： 步骤1：在开始时词典为空； 步骤2：当前码字W:= 码字流中的下一个码字 步骤3：当前字符Char:=紧随码字之后的字符 步骤4：把当前码字的缀-符串（string.W）输出到字符流，然后输出字符Char 步骤5：把string.W + Char添加到词典中 步骤6：判断码字流中是否还有码字要译码， (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、由于代码的原型是在网上找的，因此代码中存