基于字典编码的数据压缩技术的改进与实现

《基于字典编码的数据压缩技术的改进与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、毕业设计报告1.目录毕业设计报告11.目录12.前言13.对字典编码的认识23.1.数据压缩简史23.1.1.通用无损数据压缩23.1.2.多媒体信息的压缩33.2.数据压缩的基本理论与分类43.2.1.什么是熵43.2.2.模型43.2.3.编码53.2.4.压缩技术概貌53.3.字典编码原理64.字典编码方法的分类与特点64.1.LZ77算法64.2.LZ78算法74.3.LZSS算法74.4.LZW算法85.＂不足＂与改进105.1.对技术的改进105.1.1.零搜索105.1.2.动态编码长度105.2.设计方法的改进106.算法实现116.1.数据结构116

2、.1.1.常量定义：116.1.2.编码类：116.1.3.解码类：126.2.编码算法136.2.1.流程描述136.2.2.核心代码136.3.解码算法176.3.1.流程描述176.3.2.核心代码187.总结231.前言1946年,第一台计算机ENIAC诞生.之后的五十多年里,计算机领域有了突飞猛进的发展,计算机所能处理的数据也是成倍的增长.这就对数据存储设备有了更高的要求,同时,数据压缩技术也应运而生.尤其是近年来的”信息爆炸”概念的提出,使得数据压缩成为人们争相研究的对象,因此学习一下数据压缩的知识,研究数据压缩的技术是十分有必要的.2.对字典编码的认识2

3、.1.数据压缩简史2.1.1.通用无损数据压缩很早以前,科学家就在研究中发现，大多数信息的表达都存在着一定的冗余度，通过采用一定的模型和编码方法，可以降低这种冗余度。1948&1949贝尔实验室的ClaudeShannon(1948)和MIT的R.M.Fano(1949)几乎同时提出了最早的对符号进行有效编码从而实现数据压缩的Shannon-Fano编码方法。1952D.A.Huffman第一次发表了他的论文“最小冗余度代码的构造方法”(AMethodfortheConstructionofMinimumRedundancyCodes)。从此，数据压缩开始在商业程序中

4、实现并被应用在许多技术领域。在数据压缩领域，Huffman的这一论文事实上开创了数据压缩技术一个值得回忆的时代，60年代、70年代乃至80年代的早期，数据压缩领域几乎一直被Huffman编码及其分支所垄断。如果不是下面的这两个以色列人，也许我们今天还要在Huffman编码的0和1的组合中流连忘返。1977以色列人JacobZiv和AbrahamLempel发表了论文“顺序数据压缩的一个通用算法”(AUniversalAlogrithemforSequentialDataCompression)。1978他们发表了该论文的续篇“通过可变比率编码的独立序列的压缩”(Com

5、pressionofIndividualSequencesviaVariable-RateCoding)。所有的一切都改变了，在这两篇论文中提出的两个压缩技术被称为LZ77和LZ78。简单地说，这两种压缩方法的思路完全不同于从Shannon到Huffman到算术压缩的传统思路，倒是和本章开头所举的成语辞典的例子颇为相似，因此，人们将基于这一思路的编码方法称作“字典”式编码。字典式编码不但在压缩效果上大大超过了Huffman，而且，对于好的实现，其压缩和解压缩的速度也异常惊人。1982Storer与Szymanski对LZ77算法进行了改进，并提出相应的LZSS算法。1

6、984TerryWelch发表了名为“高性能数据压缩技术”(ATechniqueforHigh-PerformanceDataCompression)的论文，描述了他在SperryResearchCenter(现在是Unisys的一部分)的研究成果。他实现了LZ78算法的一个变种——LZW。LZW继承了LZ77和LZ78压缩效果好、速度快的优点，而且在算法描述上更容易被人们接受（有的研究者认为是由于Welch的论文比Ziv和Lempel的更容易理解），实现也比较简单。不久，UNIX上出现了使用LZW算法的Compress程序，该程序性能优良，并有高水平的文档，很快成为

7、了UNIX世界的压缩程序标准。紧随其后的是MS-DOS环境下的ARC程序(SystemEnhancementAssociates,1985)，还有象PKWare、PKARC等仿制品。LZ78和LZW一时间统治了UNIX和DOS两大平台。1985-人们对LZ77进行了改进，随之诞生了一批我们今天还在大量使用的压缩程序。HaruyasuYoshizaki(Yoshi)的LHarc和RobertJung的ARJ是其中两个著名的例子。LZ77得以和LZ78、LZW一起垄断当今的通用数据压缩领域。目前，基于字典方式的压缩已经有了一个被广泛认可的标准，从古老的P