《lzw压缩算法的c语言实现》由会员分享，可在线阅读，更多相关《lzw压缩算法的c语言实现（18页珍藏版）》请在金锄头文库上搜索。
1、标准的LZW压缩原理：先来解释一下几个基本概念：LZW压缩有三个重要的对象：数据流(CharStream)、编码流(CodeStream)和编译 表(String Table)。在编码时，数据流是输入对象(图象的光栅数据序列)，编码流 就是输出对象(经过压缩运算的编码数据)；在解码时，编码流则是输入对象，数据 流是输出对象；而编译表是在编码和解码时都须要用借助的对象。字符(Character):最基础的数据元素，在文本文件中就是一个字节，在光栅数据中就 是一个像素的颜色在指定的颜色列表中的索引值；字符串(Str ing)：由几个连续的字符组成；前缀(Prefix):也是一个字符串，不过通常用在
2、另一个字符的前面，而且它的长度可以为0； 根(Root):单个长度的字符串；编码(Code):个数字，按照固定长度(编码长度)从编码流中取出，编译表的映射值； 图案：一个字符串，按不定长度从数据流中读出,映射到编译表条目.LZW 压缩的原理：提取原始图象数据中的不同图案，基于这些图案创建一个编译表， 然后用编译表中的图案索引来替代原始光栅数据中的相应图案，减少原始数据大小。看 起来和调色板图象的实现原理差不多，但是应该注意到的是，我们这里的编译表不是事 先创建好的，而是根据原始图象数据动态创建的，解码时还要从已编码的数据中还原出 原来的编译表(GIF文件中是不携带编译表信息的)，为了更好理解编
3、解码原理，我们 来看看具体的处理过程：编码器(Compressor)编码数据，第一步，初始化一个编译表，假设这个编译表的大小是12 位的，也就是最 多有4096个单位，另外假设我们有32个不同的字符(也可以认为图象的每个像素最多有32 种颜色)，表示为a，b，c，d，e.，初始化编译表：第0项为a,第1项为b,第2项为c. 一直到第 31 项，我们把这 32 项就称为根。开始编译，先定义一个前缀对象Current Prefix，记为.c.,现在它是空的，然后 定义一个当前字符串CurrentString,标记为.c.k, .c.就为Current Prefix，k就为当前读取字符。现在来读取数
4、据流的第一个字符，假如为p,那么Current String就等 于.c.p (由于.c.为空，实际上值就等于p),现在在编译表中查找有没有Current String的值，由于p就是一个根字符，我们已经初始了 32个根索引，当然可以找到，把p 设为 Current Prefix 的值，不做任何事继续读取下一个字符，假设为 q， Current String 就等于.c.q (也就是pq),看看在编译表中有没有该值，当然。没有，这时我们要做下 面的事情：将CurrentString的值(也就是pq)添加到编译表的第32项，把Current Prefix的值(也就是p)在编译表中的索引输出到编码
5、流，修改Current Prefix为当前读取的字符(也就是q)。继续往下读，如果在编译表中可以查找到CurrentString的值(.c.k),则把Current String的值(.c.k)赋予Current Prefix；如果查找不到，则添加CurrentString的值(.c.k)到编译表，把Current Prefix的值(.c.)在编译表中所对应的索引 输出到编码流，同时修改Current Prefix为k，这样一直循环下去直到数据流结束。伪代码看起来就像下面这样：编码器伪代码Initialize String Table;.c. = Empty;.c.k = First Char
6、acter in CharStream;while (.c.k != EOF )if ( .c.k is in the StringTable).c. = .c.k;elseadd .c.k to the StringTable;OutputtheIndex of.c. in the StringTableto the CodeStream;.c.= k;.c.k=NextCharacterin CharStream;Output theIndexof .c.in the StringTable to theCodeStream;来看一个具体的例子，我们有一个字母表a, b, c, d.有一个
7、输入的字符流abacaba。现在来初始化编译表：#0=a,#l=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，
8、.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）好了，现在来看看解码数据。数据的解码，其实就是数据编码的逆向过程，要从 已经编译的数据（编码流）中找出编译表，然后对照编译表还原图象的光栅数据。首
9、先，还是要初始化编译表。GIF文件的图象数据的第一个字节存储的就是LZW编 码的编码大小（一般等于图象的位数），根据编码大小，初始化编译表的根条目（从 0到2的编码大小次方），然后定义一个当前编码Current Code,记作code，定义一 个Old Code,记作old。读取第一个编码到code，这是一个根编码，在编译表中可 以找到，把该编码所对应的字符输出到数据流，old=code；读取下一个编码到code，这就有两种情况：在编译表中有或没有该编码，我们先来看第一种情况：先 输出当前编码code所对应的字符串到数据流，然后把old所对应的字符（串）当成 前缀prefix .，当前编码co
10、de所对应的字符串的第一个字符当成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 所 对应的索引时，我们不知到该索引对应的字符串（在解码器的编译表中还没有该索引， 事实上，这个索引将
11、在下一步添加），这时需要用猜测法：现在假设上面的 p.所 对应的索引值是#58，那么上面的字符串经过编译之后是#58#59，我们在解码器中读 到#59 时，编译表的最大索引只有#58， #59 所对应的字符串就等于#58所对应的字符串 （也就是p.）加上这个字符串的第一个字符（也就是p），也就是p.p。事实上， 这种猜测法是很准确（有点不好理解，仔细想一想吧）。上面的解码过程用伪代码表 示就像下面这样：解码器伪代码Initialize String Table;code = First Code in the CodeStream;Output the String for code to t
12、he CharStream;old = code;code = Next Code in the CodeStream;while （code != EOF ）if （ code is in the StringTable）Output theStri ngfor code to the CharStream; /输出code所对应的字符串.=tra nslation for old; /old 所对应的字符串k = first character of tra nslation for code; / code所对应的字符串的 第一个字符add.k to the StringTable;ol
13、d = code;else.= translation for old;k = first character of .;Output.k to CharStream;add.k to the StringTable;old = code;code = Next Code in the CodeStream;词典编码词典编码主要利用数据本身包含许多重复的字符串的特性.例如:吃葡萄不吐葡萄皮, 不吃葡萄倒吐葡萄皮. 我们如果用一些简单的代号代替这些字符串,就可以实现压缩,实际上 就是利用了信源符号之间的相关性.字符串与代号的对应表就是词典 . 实用的词典编码算法 的核心就是如何动态地形成词典,以
14、及如何选择输出格式以减小冗余 . 第一类词典编码第一 类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过 ,然后用已 经出现过的字符串替代重复的部分 ,它的输出仅仅是指向早期出现过的字符串的 指针 . LZ77 算法 LZ77 算法在某种意义上又可以称为滑动窗口压缩 ,该算法将一个虚拟的,可以 跟随压缩进程滑动的窗口作为词典,要压缩的字符串如果在该窗口中出现,则输出其出现位置 和长度.使用固定大小窗口进行词语匹配 ,而不是在所有已经编码的信息中匹配 ,是因为匹配 算法的时间消耗往往很多,必须限制词典的大小才能保证算法的效率;随着压缩的进程滑动词 典窗口,使其中总包含最近编码过的信息 ,是因为对大多数信息而言,要编码的字符串往往在 最近的上下文中更容易找到匹配串. LZ77 编码的基本流程 1,从当前压缩位置开始,考察未编 码的数据,并试图在滑动窗口中找出最长的匹配字符串 ,如果找到,则进行步骤 2,否则进行步 骤 3. 2,输出三元符号组 ( off, len, c ). 其中 off 为窗口中匹配字符串相对窗口边界的偏 移,len为可匹配的长度,c为下一个字符，即不匹配的第一个字符.然后将窗口向后滑动len + 1 个字符,继续步骤 1. 3,输出三元符号组 ( 0, 0, c ).其中 c 为下一个字符.然后将窗口向后 滑动1个
