LZ77算法实现

LZ77压缩算法的实现专业：班级：学号：姓名：报告日期：1LZ77压缩算法的实现学生姓名：指导老师：摘要文本压缩是根据一定方法对大量数据进行编码处理以达到信息压缩存储过程，被压缩的数据应该能够通过解码恢复到压缩以前的原状态，而不会发生信息丢失现象。发展到现在已经有很多关于文本压缩的算法，主要有LZ编码、Huffman编码、算术编码等无损压缩和预测编码、量化、变换编码等有损压缩。本文将讨论LZ77算法实现过程，以及LZ77算法的优劣性和改进方法。关键词多媒体技术；文本压缩算法；LZ77算法；C++程序设计；数据结构；字符串查找；文本匹配；2目录1引言...........................................................................................................................................31.1课程设计目的.....................................................................................................................31.2课程设计内容.....................................................................................................................32算法基本原理...............................................................................................................................42.1算法概述.............................................................................................................................42.2LZ77压缩..........................................................................................................................42.3LZ77解压缩......................................................................................................................53LZZ算法实现..............................................................................................................................63.1三元组的设计....................................................................................................................63.2查找匹配串........................................................................................................................64实验结果和结果分析...................................................................................................................84.1实验结果...........................................................................................................................84.2实验结果分析...................................................................................................................95结束语.........................................................................................................................................10参考文献.........................................................................................................................................11附录1：LZ77主要代码清单........................................................................................................1231引言随着计算机技术的快速发展,各种系统数据量越来越大,给信息存储特别是网络传输带来诸多的困难,己成为有效获取和使用信息的瓶颈。为了节省信息的存储空间和提高信息的传输效率,必须对大量的实际数据进行压缩。实践证明,采用数据压缩技术可以节省80%以上的费用,且一些难点问题通过压缩技术能够实现。数据压缩技术种类繁多、应用广泛,技术不断发展,一些分支已成为当今研究的焦点。按照编码的失真程度数据压缩可以分为有损压缩和无损压缩。有损压缩即原始数据不能完全恢复,主要应用于图像和数字化的语音方面。无损压缩就是经过一个压缩后,能够产生和输入完全一致的压缩技术,主要用于存储数据库记录或处理文本文件。其中，LZ77算法是无损压缩中常用到的算法。1.1课程设计目的研究多媒体数据压缩技术是实现实时有效地处理、传输和存储庞大的多媒体数据的关键技术。许多应用领域对多媒体信息的实时压缩提出了更高的要求，快速、高效的压缩算法是解决这一问题的关键。针对多媒体数据在空间、时间、结构、视觉、知识等方面所产生的冗余,利用有损压缩和无损压缩等方法,对图像、音频、视频等多媒体数据进行压缩,以保留尽可能少的有用信息。本文主要是把所学的数据结构和算法设计的知识应用于实践，对LZ77压缩算法加以研究。通过课程设计，可以更好地掌握和理解文本压缩算法，学习常用的压缩算法，并通过比较压缩算法，来加深对多媒体技术的理解。1.2课程设计内容本次课程设计为LZ77算法的实现，通过用C++语言来这个算法，然后用随机生成的数据来分别对程序进行压缩和解压，检验压缩结果是否正确和测试程序压缩的效率。42算法基本原理2.1算法概述这一算法是由JacobZiv和AbrahamLempel于1977年提出，所以命名为LZ77。传统的算法，如Huffman算法都是建立在静态的字典模型上，但是静态字典模型并不是好的选择。首先，静态模型的适应性不强，我们必须为每类不同的信息建立不同的字典；其次，对静态模型，我们必须维护信息量并不算小的字典，这一额外的信息量影响了最终的压缩效果。LZ77采用了自适应的字典模型，也就是说，将已经编码过的信息作为字典，如果要编码的字符串曾经出现过，就输出该字符串的出现位置及长度，否则输出新的字符串。如下图2.1所示。图2.1LZ77算法举例2.2LZ77压缩LZ77算法使用滑动窗口的方法，来寻找文件中的相同部分，也就是匹配串。这里说的串，是指一个任意字节的序列，而不仅仅是可以在文本文件中显示出来的那些字节的序列。这里的串强调的是它在文件中的位置，它的长度随着匹配的情况而变化。LZ77从文件的开始处开始，一个字节一个字节的向后进行处理。一个固定大小的窗口（在当前处理字节之前，并且紧挨着当前处理字节），随着处理的字节不断的向后滑动。对于文件中的每个字节，用当前处理字节开始的串，和窗口中的每个串进行匹配，寻找最长的匹配串。窗口中的每个串指，窗口中每个字节开始的串。如果当前处理字节开始的串在窗口中有匹配串，就用(之间的距离，匹配长度)这样一对信息，来替换当前串，然后从刚才处理完的串之后的下一个字节，继续处理。如果当前处理字节开始的串在窗口中没有匹配串，就不做改动的输出当前处理字节。处理文件中第一个字节的时候，窗口在当前处理字节之前，也就是还没有滑到文件上，这时窗口中没有任何内容，被处理的字节就会不做改动的输出。随着处理的不断向后，窗口越来越多的滑入文件，最后整个窗口滑入文件，然后整个5窗口在文件上向后滑动，直到整个文件结束。下图2.2是LZ77算法示意图。图2.2LZ77算法示意图算法基本流程：1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤2，否则进行步骤3。2、输出三元符号组(off,len,c)。其中off为窗口中匹配字符串相对窗口边界的偏移，len为可匹配的长度，c为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤1。3、输出三元符号组(0,0,c)。其中c为下一个字符。然后将窗口向后滑动len+1个字符，继续步骤1。2.3LZ77解压缩从文件开始到文件结束，每次先读一位标志位，通过这个标志位来判断下面是一个(之间的距离，匹配长度)对，还是一个没有改动的字节。如果是一个（之间的距离，匹配长度）对，就读出固定位数的（之间的距离，匹配长度）对，然后根据对中的信息，将匹配串输出到当前位置。如果是一个没有改动的字节，就读出一个字节，然后输出这个字节。我们可以看到，LZ77压缩时需要做大量的匹配工作，而解压缩时需要做的工作很少，也就是说解压缩相对于压缩将快的多。这对于需要进行一次压缩，多次解压缩的情况，是一个巨大的优点。63LZZ算法实现3.1三元组的设计我们必须精心设计三元组中每个分量的表示方法，才能达到较好的压缩效果。一般来讲，编码的设计要根据待编码的数值的分布情况而定。对于三元组的第一个分量——窗口内的偏移，通常的经验是，偏移接近窗口尾部的情况要多于接近窗口头部的情况，这是因为字符串在与其接近的位置较容易找到匹配串，但对于普通的窗口大小（例如4096字节）来说，偏移值基本还是均匀分布的，我们完全可以用固定的位数来表示它。编码off需要的位数bitnum=upper_bound(log2(MAX_WND_SIZE))。由此，如果窗口大小为4096，用12位就可以对偏移编码。如果窗口大小为2048，用11位就可以了。复杂一点的程序考虑到在压缩开始时，窗口大小并没有达到MAX_WND_SIZE，而是随着压缩的进行增长，因此可以根据窗口的当前大小动态计算所需要的位数，这样可以略微节省一点空间。对于第二个分量——字符串长度，它在大多数时候不会太大，少数情况下才会发生大字符串的匹配。一般运用Golomb编码。3.2查找匹配串在滑动窗口中查找最长的匹配串，是LZ77算法中的核心问题。容易知道，LZ77算法中空间和时间的消耗集中于对匹配串的查找算法。每次滑动窗口之后，都要进行下一个匹配串的查找，如果查找算法的时间效率在O(n2)或者更高，总的算法时间效率就将达到O(n3)，这是我们无法容忍的。正常的顺序匹配算法显然无法满足我们的要求。可以使用以下几种方案。1、限制可匹配字符串的最大长度（例如20个字节），将窗口中每一个20字节长的串抽取出来，按照大小顺序组织