GIF数据压缩算法

《GIF数据压缩算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、LZW算法和GIF数据压缩GIF文件的图象数据使用了可变长度编码的LZW压缩算法(Variable-Length_CodeLZWCompression)，本文详细介绍了这种算法。可变长度编码的LZW压缩算法(Variable-Length_CodeLZWCompression)，是从LZW(LempelZivCompression)压缩算法演变过来的，通过压缩原始数据的重复部分来达到减少文件大小的目的。标准的LZW压缩原理：先来解释一下几个基本概念：LZW压缩有三个重要的对象：数据流(CharSt

2、ream)、编码流(CodeStream)和编译表(StringTable)。在编码时，数据流是输入对象（图象的光栅数据序列），编码流就是输出对象（经过压缩运算的编码数据）；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都须要用借助的对象。字符(Character)：最基础的数据元素，在文本文件中就是一个字节，在光栅数据中就是一个像素的颜色在指定的颜色列表中的索引值；字符串(String)：由几个连续的字符组成；前缀(Prefix)：也是一个字符串，不过通常用在另一个字符

3、的前面，而且它的长度可以为0；根(Root)：单个长度的字符串；编码(Code)：一个数字，按照固定长度（编码长度）从编码流中取出，编译表的映射值；图案：一个字符串，按不定长度从数据流中读出,映射到编译表条目.LZW压缩的原理：提取原始图象数据中的不同图案，基于这些图案创建一个编译表，然后用编译表中的图案索引来替代原始光栅数据中的相应图案，减少原始数据大小。看起来和调色板图象的实现原理差不多，但是应该注意到的是，我们这里的编译表不是事先创建好的，而是根据原始图象数据动态创建的，解码时还要从已编码的

4、数据中还原出原来的编译表（GIF文件中是不携带编译表信息的），为了更好理解编解码原理，我们来看看具体的处理过程：编码器(Compressor)编码数据，第一步，初始化一个编译表，假设这个编译表的大小是12位的，也就是最多有4096个单位，另外假设我们有32个不同的字符（也可以认为图象的每个像素最多有32种颜色），表示为a，b，c，d，e...，初始化编译表：第0项为a，第1项为b，第2项为c...一直到第31项，我们把这32项就称为根。开始编译，先定义一个前缀对象CurrentPrefix，记为[

5、.c.]，现在它是空的，然后定义一个当前字符串CurrentString，标记为[.c.]k，[.c.]就为CurrentPrefix，k就为当前读取字符。现在来读取数据流的第一个字符，假如为p，那么CurrentString就等于[.c.]p（由于[.c.]为空，实际上值就等于p），现在在编译表中查找有没有CurrentString的值，由于p就是一个根字符，我们已经初始了32个根索引，当然可以找到，把p设为CurrentPrefix的值，不做任何事继续读取下一个字符，假设为q，CurrentS

6、tring就等于[.c.]q（也就是pq），看看在编译表中有没有该值，当然。没有，这时我们要做下面的事情：将CurrentString的值（也就是pq）添加到编译表的第32项，把CurrentPrefix的值（也就是p）在编译表中的索引输出到编码流，修改CurrentPrefix为当前读取的字符（也就是q）。继续往下读，如果在编译表中可以查找到CurrentString的值([.c.]k)，则把CurrentString的值([.c.]k)赋予CurrentPrefix；如果查找不到，则添加Cur

7、rentString的值([.c.]k)到编译表，把CurrentPrefix的值([.c.])在编译表中所对应的索引输出到编码流，同时修改CurrentPrefix为k，这样一直循环下去直到数据流结束。伪代码看起来就像下面这样：编码器伪代码InitializeStringTable;[.c.]=Empty;[.c.]k=FirstCharacterinCharStream;while([.c.]k!=EOF){if([.c.]kisintheStringTable){[.c.]=[.c.]k;}

8、else{add[.c.]ktotheStringTable;OutputtheIndexof[.c.]intheStringTabletotheCodeStream;[.c.]=k;}[.c.]k=NextCharacterinCharStream;}OutputtheIndexof[.c.]intheStringTabletotheCodeStream;来看一个具体的例子,我们有一个字母表a，b，c，d.有一个输入的字符流abacaba。现在来初始化编译表：#0=a,#1=b,