lzw压缩算法的c语言实现

标准的LZW压缩原理：~~~~~~~~~~~~~~~~~~先来解释一下几个基本概念：LZW压缩有三个重要的对象：数据流(CharStream)、编码流(CodeStream)和编译表(StringTable)。在编码时，数据流是输入对象（图象的光栅数据序列），编码流就是输出对象（经过压缩运算的编码数据）；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都须要用借助的对象。字符(Character)：最基础的数据元素，在文本文件中就是一个字节，在光栅数据中就是一个像素的颜色在指定的颜色列表中的索引值；字符串(String)：由几个连续的字符组成；前缀(Prefix)：也是一个字符串，不过通常用在另一个字符的前面，而且它的长度可以为0；根(Root)：单个长度的字符串；编码(Code)：一个数字，按照固定长度（编码长度）从编码流中取出，编译表的映射值；图案：一个字符串，按不定长度从数据流中读出,映射到编译表条目.LZW压缩的原理：提取原始图象数据中的不同图案，基于这些图案创建一个编译表，然后用编译表中的图案索引来替代原始光栅数据中的相应图案，减少原始数据大小。看起来和调色板图象的实现原理差不多，但是应该注意到的是，我们这里的编译表不是事先创建好的，而是根据原始图象数据动态创建的，解码时还要从已编码的数据中还原出原来的编译表（GIF文件中是不携带编译表信息的），为了更好理解编解码原理，我们来看看具体的处理过程：编码器(Compressor)~~~~~~~~~~~~~~~~编码数据，第一步，初始化一个编译表，假设这个编译表的大小是12位的，也就是最多有4096个单位，另外假设我们有32个不同的字符（也可以认为图象的每个像素最多有32种颜色），表示为a，b，c，d，e...，初始化编译表：第0项为a，第1项为b，第2项为c...一直到第31项，我们把这32项就称为根。开始编译，先定义一个前缀对象CurrentPrefix，记为[.c.]，现在它是空的，然后定义一个当前字符串CurrentString，标记为[.c.]k，[.c.]就为CurrentPrefix，k就为当前读取字符。现在来读取数据流的第一个字符，假如为p，那么CurrentString就等于[.c.]p（由于[.c.]为空，实际上值就等于p），现在在编译表中查找有没有CurrentString的值，由于p就是一个根字符，我们已经初始了32个根索引，当然可以找到，把p设为CurrentPrefix的值，不做任何事继续读取下一个字符，假设为q，CurrentString就等于[.c.]q（也就是pq），看看在编译表中有没有该值，当然。没有，这时我们要做下面的事情：将CurrentString的值（也就是pq）添加到编译表的第32项，把CurrentPrefix的值（也就是p）在编译表中的索引输出到编码流，修改CurrentPrefix为当前读取的字符（也就是q）。继续往下读，如果在编译表中可以查找到CurrentString的值([.c.]k)，则把CurrentString的值([.c.]k)赋予CurrentPrefix；如果查找不到，则添加CurrentString的值([.c.]k)到编译表，把CurrentPrefix的值([.c.])在编译表中所对应的索引输出到编码流，同时修改CurrentPrefix为k，这样一直循环下去直到数据流结束。伪代码看起来就像下面这样：编码器伪代码InitializeStringTable;[.c.]=Empty;[.c.]k=FirstCharacterinCharStream;while([.c.]k!=EOF){if([.c.]kisintheStringTable){[.c.]=[.c.]k;}else{add[.c.]ktotheStringTable;OutputtheIndexof[.c.]intheStringTabletotheCodeStream;[.c.]=k;}[.c.]k=NextCharacterinCharStream;}OutputtheIndexof[.c.]intheStringTabletotheCodeStream;来看一个具体的例子,我们有一个字母表a，b，c，d.有一个输入的字符流abacaba。现在来初始化编译表：#0=a,#1=b,#2=c,#3=d.现在开始读取第一个字符a，[.c.]a=a，可以在在编译表中找到，修改[.c.]=a;不做任何事继续读取第二个字符b，[.c.]b=ab，在编译表中不能找，那么添加[.c.]b到编译表：#4=ab，同时输出[.c.]（也就是a）的索引#0到编码流，修改[.c.]=b；读下一个字符a，[.c.]a=ba，在编译表中不能找到：添加编译表#5=ba，输出[.c.]的索引#1到编码流，修改[.c.]=a；读下一个字符c，[.c.]c=ac，在编译表中不能找到：添加编译表#6=ac，输出[.c.]的索引#0到编码流，修改[.c.]=c；读下一个字符a，[.c.]c=ca，在编译表中不能找到：添加编译表#7=ca，输出[.c.]的索引#2到编码流，修改[.c.]=a；读下一个字符b，[.c.]b=ab，编译表的#4=ab，修改[.c.]=ab；读取最后一个字符a，[.c.]a=aba，在编译表中不能找到：添加编译表#8=aba，输出[.c.]的索引#4到编码流，修改[.c.]=a；好了，现在没有数据了，输出[.c.]的值a的索引#0到编码流，这样最后的输出结果就是：#0#1#0#2#4#0.解码器(Decompressor)~~~~~~~~~~~~~~~~~~好了，现在来看看解码数据。数据的解码，其实就是数据编码的逆向过程，要从已经编译的数据（编码流）中找出编译表，然后对照编译表还原图象的光栅数据。首先，还是要初始化编译表。GIF文件的图象数据的第一个字节存储的就是LZW编码的编码大小（一般等于图象的位数），根据编码大小，初始化编译表的根条目（从0到2的编码大小次方），然后定义一个当前编码CurrentCode，记作[code]，定义一个OldCode，记作[old]。读取第一个编码到[code]，这是一个根编码，在编译表中可以找到，把该编码所对应的字符输出到数据流，[old]=[code]；读取下一个编码到[code]，这就有两种情况：在编译表中有或没有该编码，我们先来看第一种情况：先输出当前编码[code]所对应的字符串到数据流，然后把[old]所对应的字符（串）当成前缀prefix[...]，当前编码[code]所对应的字符串的第一个字符当成k，组合起来当前字符串CurrentString就为[...]k，把[...]k添加到编译表，修改[old]=[code]，读下一个编码；我们来看看在编译表中找不到该编码的情况，回想一下编码情况：如果数据流中有一个p[...]p[...]pq这样的字符串，p[...]在编译表中而p[...]p不在，编译器将输出p[...]的索引而添加p[...]p到编译表，下一个字符串p[...]p就可以在编译表中找到了，而p[...]pq不在编译表中，同样将输出p[...]p的索引值而添加p[...]pq到编译表，这样看来，解码器总比编码器『慢一步』，当我们遇到p[...]p所对应的索引时，我们不知到该索引对应的字符串（在解码器的编译表中还没有该索引，事实上，这个索引将在下一步添加），这时需要用猜测法：现在假设上面的p[...]所对应的索引值是#58，那么上面的字符串经过编译之后是#58#59，我们在解码器中读到#59时，编译表的最大索引只有#58，#59所对应的字符串就等于#58所对应的字符串(也就是p[...])加上这个字符串的第一个字符(也就是p)，也就是p[...]p。事实上，这种猜测法是很准确（有点不好理解，仔细想一想吧）。上面的解码过程用伪代码表示就像下面这样：解码器伪代码InitializeStringTable;[code]=FirstCodeintheCodeStream;OutputtheStringfor[code]totheCharStream;[old]=[code];[code]=NextCodeintheCodeStream;while([code]!=EOF){if([code]isintheStringTable){OutputtheStringfor[code]totheCharStream;//输出[code]所对应的字符串[...]=translationfor[old];//[old]所对应的字符串k=firstcharacteroftranslationfor[code];//[code]所对应的字符串的第一个字符add[...]ktotheStringTable;[old]=[code];}else{[...]=translationfor[old];k=firstcharacterof[...];Output[...]ktoCharStream;add[...]ktotheStringTable;[old]=[code];}[code]=NextCodeintheCodeStream;}词典编码词典编码主要利用数据本身包含许多重复的字符串的特性.例如:吃葡萄不吐葡萄皮,不吃葡萄倒吐葡萄皮.我们如果用一些简单的代号代替这些字符串,就可以实现压缩,实际上就是利用了信源符号之间的相关性.字符串与代号的对应表就是词典.实用的词典编码算法的核心就是如何动态地形成词典,以及如何选择输出格式以减小冗余.第一类词典编码第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过,然后用已经出现过的字符串替代重复的部分,它的输出仅仅是指向早期出现过的字符串的指针.LZ77算法LZ77算法在某种意义上又可以称为滑动窗口压缩,该算法将一个虚拟的,可以跟随压缩进程滑动的窗口作为词典,要压缩的字符串如果在该窗口中出现,则输出其出现位置和长度.使用固定大小窗口进行词语匹配,而不是在所有已经编码的信息中匹配,是因为匹配算法的时间消耗往往很多,必须限制词典的大小才能保证算法的效率;随着压缩的进程滑动词典窗口,使其中总包含最近编码过的信息,是因为对大多数信息而言,要编码的字符串往往在最近的上下文中更容易找到匹配串.LZ77编码的基本流程1,从当前压缩位置开始,考察未编码的数据,并试图在滑动窗口中找出最长的匹配字符串,如果找到,则进行步骤2,否则进行步骤3.2,输出三元符号组(off,len,c).其中off为窗口中匹配字符串相对窗口边界的偏移,len为可匹配的长度,c为下一个字符,即不匹配的第一个字符.然后将窗口向后滑动len+1个字符,继续步骤1.3,输出三元符号组(0,0,c).其中c为下一个字符.然后将窗口向后滑动1个字符,继续步骤1.LZ77算法LZ77编码举例CABABBCBAA5,3,AABC752,1,BB540,0,C--431,1,BA220,0,A--11输出匹配串位置步骤LZSS算法LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题,但这个解决方案包含有冗余信息.冗余信息表现在两个方面,一是空指针,二是编码器可能输出额外的字符,这种字符是指可能包含在下一个匹配串中的字符.LZSS算法的思想是如果匹配串的长度比指针本身的长度长就输出指针(匹配串长度大于等于MIN_LENGTH),否则就输出真实字符.另外要输出额外的标志位区分是指针还是字符.LZSS编码的基本流程1,从当前压缩位置开始,考察未编码的字符,并试图在滑动窗口中找出最长的匹配字符串,如果匹配串长度len大于等于最小匹配串长度(len=MIN_LENGTH),则进行步骤2,否则进行步骤3.2,输出指针二元组(off,len).其中off为窗口中匹配字符串相对窗口边界的偏移,len为匹配串的长度,然后将窗口向后滑动len个字符,继续步骤1.3,输出当前字符c,然后将窗口