开题报告张如霞

《开题报告张如霞》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、毕业设计（论文）开题报告课题名称LZ78字典编码码的特性分析副标题系（院）名称:电子与信息工程系专业:姓名:学号:电子信息工程张如霞1114036二O—四年一、毕业设计（论文）课题背景（含文献综述）数据压缩技术比较系统的研究，开始于在40年代初形成的信息论。早期科学家研究的是在已知消息中各种符号出现的频率时，要想办法构造出一种编码技术，使得消息的所占空间尽可能的减少。尽管当时计算机尚未出现，但是那时进行的研究与如今计算机屮所使用的压缩技术有很人的联系。数据压缩的研究过程一肓都有两个重要的方向，一是建立信源和数据压缩的数学模型，二是工程技术人员所进疔的工作，建立能实现数据压缩功能

2、的系统。当数据压缩使得存储空间减少的时候，程序的执行时间就相应的减少。因为存储最的减少导致磁盘存取次数的减少，尽管数据压缩/解压缩会增加额外的程序指令，但是这花费的时间远远少于数据存取的时间，总体來说，执行时间将减少。所以，数据压缩技术在计算机技术飞速发展的今天，依旧有着十分重要的作用。以Huffman编码为代表的压缩模型都是基于対信息单个字符岀现频率的统计而设计的，直到70年代末期，这种思想在数据压缩领域一自占据着统治地位。但是，往往一项技术在某一领域形成了惯例，人们就很难创造出在思想上与其人相径庭的哪怕是更简单更实用的技术来。肓到1977年,JacobZiv和Abraham

3、Lempel发表了论文《顺序数据压缩的一个通用算法》。1978年，他们又发表了该论文的续篇《通过可变比率编码的独立序列的压缩》。这两篇论文提出的两个压缩技术被称为LZ77和LZ78算法。【必77算法使用固定大小窗II进行术语匹配，而不是在所有已经编码的信息屮1兀配。而"78算法放弃了文本窗口的概念，采用树形结构构造字典和保存短语，从而确保文件屮的内容均能反映到字典屮。它们的思路和字典颇为相似,因此，人们将基于这一思路的编码方法称作字典式编码。字典式编码不但在压缩效果上大大超过了哈夫曼编码，而且，对于好的实现，它的压缩和解压缩的速度也是界常的惊人。LZ78算法设置的字典开始是空的

4、，它的大小受限于可用的存储空间。编码器输岀双字段的标识，第一个字段是指向字典的指针，第二个字段是字符的编码。标识屮不含匹配串长度,因为隐含在字典中，每一个标识对应一个输入字符串，当标识被写进压缩流屮后，该字符串就被添加到字典屮。字典在位置0以空串开始，随着字符的输入和编码，字符串被添加到字典上的位置1,2……上，当从输入流中读入下一个字符X时，就在字典中搜索X这个单字符串词条，如杲没有找到，就把X加进字典的下一个可用位置，并输出表示“X”的标识（0,X）。如果找到了带有X的词条（比如在位置1上），则当读入下一个字符Y时，就在字典屮搜索含有双字符串XY的词条。如果没找到，就把串x

5、y添加到字典的下一个可用位置上，并输出标识（1，Y）表示串xy,因为串子字典中的位置为1,。如此继续直到输入完毕。这就是"78算法工艺流程。Lz78最大的优点是在每个编码步骤中减少了缀■符串（String）比较的数目，而压缩率与LZ77类似。但是基于编码之前，Iz78算法的设置并没有单独字符的字典编码，需要在读入一个字符的同时，将其编入自己的字典，如果下一次读入在已有的字典中没有找到该字符，就再编入新的字典中。如此循环。在理论上，Iz78的重要性是当输入数据山一•静态无噪信源产牛.时，随着数据人小的增加，压缩趋于最优化。以信源的爛值来编码无限长的串。但是Iz78事实上收敛得相当

6、慢，这种优化实际上要等到数据文件趋于无限长时才能真正的实现。1984年,T.Welch给出TLZ78算法的实用变型LZW。它的压缩速度比LZSS快的多。理论再次证明,当输入数据文件由以稳定的备态经历的码源产生时，LZW算法的压缩效果随着输入文件的增长而渐渐地趋近于最佳压缩。这是一个好的发现，是压缩编码技术得到进-步的提升。如果只是在原先的技术上操作，在时I、可和空I、可上也许满足不了我们对信息搜寻的要求。白从出现了这儿种编码，我们看到了一路以來，技术的变化和发展，也能感受到对于压缩信息，我们从繁化简的技术风格也H新月异。--切为了快速浏览信息和掌握信息。在编码技术的不断成熟和创

7、新Z下,有了当下更加实用化的信息资源。二、毕业设计(论文)方案介绍(主要内容)学习掌握字典编码的内容和流程方法，比较不同编码之间的联系和差异。"78对lz77的某些方曲做出了改进，其字典可以很人，是依赖于整个被编码的上下文的，字典和匹配长度都无须传递，由解码器白动同步建立和维护。它发生匹配时，不是保存一个三元组，而是一个二元组：匹配位置和不匹配的第一个字符。同时，还要将这个字符串保存到内存屮，为此，它需要一个不断增长的编码字串表。利用案例加深体验字典编码形成的实用意义。研究lz78算法的优缺