LZ77算法实现.doc

LZ77压缩算法的实现专 业： 班 级： 学 号： 姓 名： 报告日期： LZ77压缩算法的实现学生姓名： 指导老师： 摘 要 文本压缩是根据一定方法对大量数据进行编码处理以达到信息压缩存储过程，被压缩的数据应该能够通过解码恢复到压缩以前的原状态，而不会发生信息丢失现象。发展到现在已经有很多关于文本压缩的算法，主要有LZ编码、Huffman 编码、算术编码等无损压缩和预测编码、量化、变换编码等有损压缩。本文将讨论LZ77算法实现过程，以及LZ77算法的优劣性和改进方法。关键词 多媒体技术；文本压缩算法；LZ77算法；C+程序设计；数据结构；字符串查找；文本匹配；0目 录1 引 言31.1课程设计目的31.2课程设计内容32 算法基本原理42.1算法概述42.2 LZ77压缩42.3 LZ77解压缩5 3 LZZ算法实现63.1三元组的设计63.2查找匹配串64 实验结果和结果分析84.1 实验结果84.2 实验结果分析95 结束语10参考文献11附录1：LZ77主要代码清单121 引 言随着计算机技术的快速发展,各种系统数据量越来越大,给信息存储特别是网络传输带来诸多的困难,己成为有效获取和使用信息的瓶颈。为了节省信息的存储空间和提高信息的传输效率,必须对大量的实际数据进行压缩。实践证明,采用数据压缩技术可以节省80%以上的费用,且一些难点问题通过压缩技术能够实现。数据压缩技术种类繁多、应用广泛,技术不断发展,一些分支已成为当今研究的焦点。按照编码的失真程度数据压缩可以分为有损压缩和无损压缩。有损压缩即原始数据不能完全恢复,主要应用于图像和数字化的语音方面。无损压缩就是经过一个压缩后,能够产生和输入完全一致的压缩技术,主要用于存储数据库记录或处理文本文件。其中，LZ77算法是无损压缩中常用到的算法。1.1课程设计目的研究多媒体数据压缩技术是实现实时有效地处理、传输和存储庞大的多媒体数据的关键技术。许多应用领域对多媒体信息的实时压缩提出了更高的要求，快速、高效的压缩算法是解决这一问题的关键。针对多媒体数据在空间、时间、结构、视觉、知识等方面所产生的冗余,利用有损压缩和无损压缩等方法,对图像、音频、视频等多媒体数据进行压缩,以保留尽可能少的有用信息。本文主要是把所学的数据结构和算法设计的知识应用于实践，对LZ77压缩算法加以研究。通过课程设计，可以更好地掌握和理解文本压缩算法，学习常用的压缩算法，并通过比较压缩算法，来加深对多媒体技术的理解。1.2课程设计内容本次课程设计为LZ77算法的实现，通过用C+语言来这个算法，然后用随机生成的数据来分别对程序进行压缩和解压，检验压缩结果是否正确和测试程序压缩的效率。2 算法基本原理2.1算法概述这一算法是由Jacob Ziv 和 Abraham Lempel 于 1977 年提出，所以命名为 LZ77。传统的算法，如Huffman 算法都是建立在静态的字典模型上，但是静态字典模型并不是好的选择。首先，静态模型的适应性不强，我们必须为每类不同的信息建立不同的字典；其次，对静态模型，我们必须维护信息量并不算小的字典，这一额外的信息量影响了最终的压缩效果。LZ77采用了自适应的字典模型，也就是说，将已经编码过的信息作为字典，如果要编码的字符串曾经出现过，就输出该字符串的出现位置及长度，否则输出新的字符串。如下图2.1所示。图 2.1 LZ77算法举例2.2 LZ77压缩LZ77算法使用滑动窗口的方法，来寻找文件中的相同部分，也就是匹配串。这里说的串，是指一个任意字节的序列，而不仅仅是可以在文本文件中显示出来的那些字节的序列。这里的串强调的是它在文件中的位置，它的长度随着匹配的情况而变化。LZ77从文件的开始处开始，一个字节一个字节的向后进行处理。一个固定大小的窗口（在当前处理字节之前，并且紧挨着当前处理字节），随着处理的字节不断的向后滑动。对于文件中的每个字节，用当前处理字节开始的串，和窗口中的每个串进行匹配，寻找最长的匹配串。窗口中的每个串指，窗口中每个字节开始的串。如果当前处理字节开始的串在窗口中有匹配串，就用(之间的距离，匹配长度) 这样一对信息，来替换当前串，然后从刚才处理完的串之后的下一个字节，继续处理。如果当前处理字节开始的串在窗口中没有匹配串，就不做改动的输出当前处理字节。处理文件中第一个字节的时候，窗口在当前处理字节之前，也就是还没有滑到文件上，这时窗口中没有任何内容，被处理的字节就会不做改动的输出。随着处理的不断向后，窗口越来越多的滑入文件，最后整个窗口滑入文件，然后整个窗口在文件上向后滑动，直到整个文件结束。下图2.2是LZ77算法示意图。图 2.2 LZ77算法示意图算法基本流程：1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。2、输出三元符号组 ( off, len, c )。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为可匹配的长度，c 为下一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。3、输出三元符号组 ( 0, 0, c )。其中 c 为下一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。2.3 LZ77解压缩从文件开始到文件结束，每次先读一位标志位，通过这个标志位来判断下面是一个(之间的距离，匹配长度) 对，还是一个没有改动的字节。如果是一个（之间的距离，匹配长度）对，就读出固定位数的（之间的距离，匹配长度）对，然后根据对中的信息，将匹配串输出到当前位置。如果是一个没有改动的字节，就读出一个字节，然后输出这个字节。我们可以看到，LZ77压缩时需要做大量的匹配工作，而解压缩时需要做的工作很少，也就是说解压缩相对于压缩将快的多。这对于需要进行一次压缩，多次解压缩的情况，是一个巨大的优点。3 LZZ算法实现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 字节长的串抽取出来，按照大小顺序组织成二叉有序树。在这样的二叉有序树中进行字符串的查找，其效率是很高的。树中每一个节点大小是 20(key) + 4(off) + 4(left child) + 4(right child) = 32。树中共有 MAX_WND_SIZE - 19 个节点，假如窗口大小为 4096 字节，树的大小大约是 130k 字节。空间消耗也不算多。这种方法对匹配串长度的限制虽然影响了压缩程序对一些特殊数据（又很长的匹配串）的压缩效果，但就平均性能而言，压缩效果还是不错的。2、将窗口中每个长度为 3 （视情况也可取 2 或 4）的字符串建立索引，先在此索引中匹配，之后对得出的每个可匹配位置进行顺序查找，直到找到最长匹配字符串。因为长度为 3 的字符串可以有 2563 种情况，我们不可能用静态数组存储该索引结构。使用 Hash 表是一个明智的选择。我们可以仅用 MAX_WND_SIZE - 1 的数组存储每个索引点，Hash 函数的参数当然是字符串本身的 3 个字符值了，Hash 函数算法及 Hash 之后的散列函数很容易设计。每个索引点之后是该字符串出现的所有位置，我们可以使用单链表来存储每一个位置。值得注意的是，对一些特殊情况比如 aaaaaa.之类的连续字串，字符串 aaa 有很多连续出现位置，但我们无需对其中的每一个位置都进行匹配，只要对最左边和最右边的位置操作就可以了。解决的办法是在链表节点中纪录相同字符连续出现的长度，对连续的出现位置不再建立新的节点。这种方法可以匹配任意长度的字符串，压缩效果要好一些，但缺点是查找耗时多于第一种方法。3、使用字符树( trie )来对窗口内的字符串建立索引，因为字符的取值范围是 0 - 255，字符树本身的层次不可能太多，3 - 4 层之下就应该换用其他的数据结构例如 Hash 表等。这种方法可以作为第二种方法的改进算法出现，可以提高查找速度，但空间的消耗较多。4 实验结果和结果分析4.1 实验结果对算法的测试，采取多方位的测试。主要为如下几个方面：1，对大文件进行测试，从网络获取文本；2，对小文件进行测试，用代码随机生成；3，对重复率高的文本进行测试，用代码生成。1，大文件测试，文本从网络获取的圣经，语言为英文，文件大小4363KB，压缩后大小为1560KB，压缩率了将近2/3，如下图4.1所示。图 4.1 大文件压缩2，小文件测试，文本从BCC获取的一片新闻，语言为英文，文件大小5KB，压缩后大小为3KB，压缩率了将近1/2，如下图4.2所示。图 4.2 小文件压缩3，对重复率高的文本，对“aghasfasdfasdf”多次出现在文本中，出现率达到70%。文件大小27KB，压缩后只有3KB，压缩率达到了将近1/10。如下图4.3所示。图 4.3 重复率高的文本压缩4.2 实验结果分析通过的算法的分析可以看出，LZ77对重复率较高的文件而且文件比较大时，压缩率比较高，尤其是当重复率很高时，压缩率会极高。这是由于采用了自适应的字典编码系统，能够直接从已经处理完的文本串中直接获取字串。上面的分析也是和实验结果相符合的。LZ77可以作为一种通用算法的压缩，对于文本的效果很不错，而且解压过程所消耗的时间非常少，复杂度只有O(N)。该算法同时也可以和其它压缩算法相结合使用，以得到更好的压缩效果。 5 结束语通过本次课程设计，我掌握了数据压缩的基本方法，同时也增强了自己的动手能力。一个好的压缩算法不仅要考虑数据压缩的可执行性，还要考虑压缩过程中的算法复杂度，同时良好的设计，将会给算法带来质的飞越。然而，实际上很难做到十全十美，原因是各要求有时相互抵触，要节约算法的执行时间往往要以牺牲更多的存储空间为代价：而为了节省存储空间又可能要以更多的时间为代价。因此，只能根据具体情况有所侧重：如果程序的使用次数较少，则应该力求算法简明易懂，而易于转换为上机程序；如果程序反复多次使用，则应该尽可能选用快速算法；如果解决问题的数据量极大，机器的内存空间较小，则在编写算法时应该考虑如何节省空间。本次课程设计培养了了我们独立思考的能力，提高了我的动手操作水平。在具体设计操作中，我巩固了上学期所学的数据结构与算法的理论知识，进一步提高了自己的编程能力。这也是课程设计的最终目的所在。通过实际操作，开发了自己的逻辑思维能力，培养了分析问题、解决问题的能力。但在程序设计的过程中我也深刻的感受到自己实力的不足，无法灵活的运用各种开发工具，对于课程所讲的东西也无法在脱离课本的情况中完成，我意识到自己在今后的学习生活中，一定要勤于思考，扎实掌握理论知识，灵活运用课上所学的东西，做一个优秀的程序员。参考文献1Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest. 北京. 算法导论(第三版)M. 机械工业出版社:Thomas H.Cormen, 20132 刘汝佳, 黄亮. 北京. 清华大学出版社. 算法艺术与信息学竞赛.3 王晓东. 北京. 清华大学出版社. 算法设计与分析（第二版）.4 彭国安. 武汉. 武汉大学出版社. 多媒体应用技术. 5 Wikipedia. Chian. LZ77与LZ78编码. 附录1：LZ77主要代码清单/ 程序名称：main.cpp/ 程序功能：LZ77算法主程序/ 程序作者：/ 学号: / 最后修改日期：2014-6-5/*#include #include #include #include #include #include lz77.h#include Lz77.cppFILE* in;FILE* out;BYTE soubuf65536;BYTE destbuf65536 + 16;int GetFileSize(char *filename) FILE *filep = fopen(filename,rb); fseek(filep,0L,SEEK_END); int length = ftell(filep); fclose(filep); return length;int LZ77Compress() in = fopen(input.txt, rb); if (in = NULL) puts(Cant open source file); return 0; out = fopen(compress.txt, wb); if (out = NULL) puts(Cant open dest file); fclose(in); return 0; fseek(in, 0, SEEK_END); long soulen = ftell(in); fseek(in, 0, SEEK_SET); CCompressLZ77 cc; WORD flag1, flag2; int last = soulen, act; while ( last 0 ) act = min(65536, last); fread(soubuf, act, 1, in); last -= act; if (act = 65536) flag1 = 0; else flag1 = act; fwrite(&flag1, sizeof(WORD), 1, out); int destlen = cc.Compress(BYTE*)soubuf, act, (BYTE*)destbuf); if (destlen = 0) flag2 = flag1; fwrite(&flag2, sizeof(WORD), 1, out); fwrite(soubuf, act, 1, out); else flag2 = (WORD)destlen; fwrite(&flag2, sizeof(WORD), 1, out); fwrite(destbuf, destlen, 1, out); fclose(in); fclose(out); printf( 原始文件大小：%10d字节 压缩后大小：%10d字节n, GetFileSize(input.txt),GetFileSize(compress.txt); return 0;int LZ77DCompress() in = fopen(compress.txt, rb); if (in = NULL) puts(Cant open source file); return 0; out = fopen(decompress.txt, wb); if (out = NULL) puts(Cant open dest file); fclose(in); return 0; fseek(in, 0, SEEK_END); long soulen = ftell(in); fseek(in, 0, SEEK_SET); CCompressLZ77 cc; WORD flag1, flag2; int last = soulen, act; while (last 0) fread(&flag1, sizeof(WORD), 1, in); fread(&flag2, sizeof(WORD), 1, in); last -= 2 * sizeof(WORD); if (flag1 = 0) act = 65536; else act = flag1; last-= flag2 ? (flag2) : act; if (flag2 = flag1) fread(soubuf, act, 1, in); else fread(destbuf, flag2, 1, in); if (!cc.Decompress(BYTE*)soubuf, act, (BYTE*)destbuf) puts(Decompress error); fclose(in); fclose(out); return 0; fwrite(BYTE*)soubuf, act, 1, out); fclose(in); fclose(out); printf( 压缩文件大小：%10d字节 解压后大小：%10d字节n, GetFileSize(compress.txt),GetFileSize(decompress.txt); return 0;int main(int argc, char* argv) printf(-LZ77压缩-n);int temp;while(1) printf( 请选择压缩文件或者解压文件(0/1)? : ); scanf(%d,&temp); if(!temp) LZ77Compress(); else LZ77DCompress(); printf(-n); return 0;*/ 程序名称：LZ77.h/ 程序功能：LZ77滑动窗口类程序/ 程序作者：张浩盛伦/ 学号: 201150080130/ 最后修改日期：2014-6-5/*#define _MAX_WINDOW_SIZE65536class CCompresspublic:CCompress() ;virtual CCompress() ;public:virtual int Compress(BYTE* src, int srclen, BYTE* dest) = 0;virtual BOOL Decompress(BYTE* src, int srclen, BYTE* dest) = 0;protected:void CopyBitsInAByte(BYTE* memDest, int nDestPos, BYTE* memSrc, int nSrcPos, int nBits);void CopyBits(BYTE* memDest, int nDestPos, BYTE* memSrc, int nSrcPos, int nBits);void In