《LZW编码算法详解》由会员分享，可在线阅读，更多相关《LZW编码算法详解（7页珍藏版）》请在金锄头文库上搜索。
1、 .wd.LZW编码算法详解LZW(Lempel-Ziv & Welch)编码又称字串表编码，是Welch将Lemple和Ziv所提出来的无损压缩技术改良后的压缩方法。GIF图像文件采用的是一种改良的LZW压缩算法，通常称为GIF-LZW压缩算法。下面简要介绍GIF-LZW的编码与解码方程解：例 现有来源于二色系统的图像数据源假设数据以字符串表示：aabbbaabb，试对其进展LZW编码及解码。1根据图像中使用的颜色数初始化一个字串表如表1，字串表中的每个颜色对应一个索引。在初始字串表的LZW_CLEAR和LZW_EOI分别为字串表初始化标志和编码完毕标志。设置字符串变量S1、S2并初始化为空
2、。2输出LZW_CLEAR在字串表中的索引3H(见表2第一行)。3从图像数据流中第一个字符开场，读取一个字符a，将其赋给字符串变量S2。判断S1+S2=“a在字符表中，那么S1=S1+S2=“a见表2第二行。4读取图像数据流中下一个字符a，将其赋给字符串变量S2。判断S1+S2=“aa不在字符串表中，输出S1=“a在字串表中的索引0H，并在字串表末尾为S1+S2=aa添加索引4H，且S1=S2=“a见表2第三行。5读下一个字符b赋给S2。判断S1+S2=“ab不在字符串表中，输出S1=“a在字串表中的索引0H，并在字串表末尾为S1+S2=“ab添加索引5H，且S1=S2=“b见表2第四行。 6
3、读下一个字符b赋给S2。S1+S2=“bb不在字串表中，输出S1=“b在字串表中的索引1H，并在字串表末尾为S1+S2=“bb添加索引6H，且S1=S2=“b见表2第五行。7读字符b赋给S2。S1+S2=“bb在字串表中，那么S1=S1+S2=“bb见表2第六行。8读字符a赋给S2。S1+S2=“bba不在字串表中，输出S1=“bb在字串表中的索引6H，并在字串表末尾为S1+S2=“bba添加索引7H，且S1=S2=“a见表2第七行。9读字符a赋给S2。S1+S2=“aa在字串表中，那么S1=S1+S2=“aa见表2第八行。10读字符b赋给S2。S1+S2=“aab不在字串表中，输出S1=“a
4、a在字串表中的索引4H，并在字串表末尾为S1+S2=“aab添加索引8H，且S1=S2=“b见表2第九行。11读字符b赋给S2。S1+S2=“bb，在字串表中，那么S1=S1+S2=“b见表2第十行。12输出S1中的字符串b在字串表中的索引1H见表2第十一行。13输出完毕标志LZW_EOI的索引3H，编码完毕。最后的编码结果为30016463“。下面对上述编码结果30016463进展解码。同样先初始化字符串表，结果如表1所示。 1首先读取第一个编码Code=3H，由于它为LZW_CLEAR，无输出见表3第一行。 2读入下一个编码Code=0H，由于字符串表中存在该索引，因此输出字符串表中0H对
5、应的字符串a，同时使OldCode=Code=0H见表3第二行。 3读下一个编码Code=0H，字符串表中存在该索引，输出0H所对应的字符串a，然后将OldCode=0H所对应的字符串a加上Code=0H所对应的字符串的第一个字符a，即aa添加到字串表中，其索引为4H，同时使OldCode=Code=0H见表3第三行。 4读下一个编码Code=1H，字串表中存在该索引，输出1H所对应的字符串b，然后将OldCode=0H所对应的字符串a加上Code=1H所对应的字符串的第一个字符b，即ab添加到字串表中，其索引为5H，同时使OldCode=Code=1H见表3第四行。 5读入下一个编码Code
6、=6H，由于字串表中不存在该索引，因此输出OldCode=1H所对应的字符串b加上OldCode的第一个字符b“，即bb，同时将bb添加到字符串表中，其索引为6H，同时使OldCode=Code=6H见表3第五行。 6读下一个编码Code=4H，字串表中存在该索引，输出4H所对应的字符串aa，然后将OldCode=6H所对应的字符串bb加上Code=4H所对应的字符串的第一个字符a，即bba添加到字串表中，其索引为7H，同时使OldCode=Code=4H见表3第六行。 7读下一个编码Code=6H，字串表中存在该索引，输出6H所对应的字符串bb，然后将OldCode=4H所对应的字符串aa加
7、上Code=6H所对应的字符串的第一个字符b，即aab添加到字串表中，其索引为8H，同时使OldCode=Code=6H见表3第七行。 8读下一个编码Code=3H，它等于LZW_EOI，数据解码完毕见表3第八行。最后的解码结果为aabbbaabb。由此可见，LZW编码算法在编码与解码过程中所建设的字符串表是一样的，都是动态生成的，因此在压缩文件中不必保存字符串表。1.LZW的全称是什么? Lempel-Ziv-Welch (LZW).2. LZW的简介和压缩原理是什么 LZW压缩算法是一种新颖的压缩方法，由Lemple-Ziv-Welch 三人共同创造，用他们的名字命名。它采用了一种先进的串
8、表压缩，将每个第一次出现的串放在一个串表中，用一个数字来表示串，压缩文件只存贮数字，那么不存贮串，从而使图象文件的压缩效率得到较大的提高。奇妙的是，不管是在压缩还是在解压缩的过程中都能正确的建设这个串表，压缩或解压缩完成后，这个串表又被丢弃。 LZW算法中，首先建设一个字符串表，把每一个第一次出现的字符串放入串表中，并用一个数字来表示，这个数字与此字符串在串表中的位置有关，并将这个数字存入压缩文件中，如果这个字符串再次出现时，即可用表示它的数字来代替，并将这个数字存入文件中。压缩完成后将串表丢弃。如print 字符串，如果在压缩时用266表示，只要再次出现，均用266表示，并将print字符串
9、存入串表中，在图象解码时遇到数字266，即可从串表中查出266所代表的字符串print，在解压缩时，串表可以根据压缩数据重新生成。3.在详细介绍算法之前，先列出一些与该算法相关的概念和词汇1)Character: 字符，一种根基数据元素，在普通文本文件中，它占用1个单独的byte，而在图像中，它却是一种代表给定像素颜色的索引值。 2)CharStream:数据文件中的字符流。 3)Prefix:前缀。如这个单词的含义一样，代表着在一个字符最直接的前一个字符。一个前缀字符长度可以为0,一个prefix和一个character可以组成一个字符串(string), 4)Suffix: 后缀，是一个字
10、符，一个字符串可以由(A,B)来组成，A是前缀,B是后缀,当A长度为0的时候，代表Root，根 5)Code:码,用于代表一个字符串的位置编码 6)Entry:一个Code和它所代表的字符串(string)4.压缩算法的简单例如，不是完全实现LZW算法，只是从最直观的角度看lzw算法的思想对原始数据ABCCAABCDDAACCDB进展LZW压缩 原始数据中，只包括4个字符(Character),A,B,C,D,四个字符可以用一个2bit的数表示，0-A,1-B,2-C,3-D,从最直观的角度看，原始字符串存在重复字符：ABCCAABCDDAACCDB，用4代表AB,5代表CC，上面的字符串可以
11、替代表示为:45A4CDDAA5DB,这样是不是就比原数据短了一些呢！5.LZW算法的适用范围为了区别代表串的值(Code)和原来的单个的数据值(String)，需要使它们的数值域不重合，上面用0-3来代表A-D,那么AB就必须用大于3的数值来代替，再举另外一个例子，原来的数值范围可以用8bit来表示，那么就认为原始的数的范围是0255，压缩程序生成的标号的范围就不能为0255如果是0-255，就重复了。只能从256开场，但是这样一来就超过了8位的表示范围了，所以必须要扩展数据的位数，至少扩展一位，但是这样不是增加了1个字符占用的空间了么但是却可以用一个字符代表几个字符，比方原来255是8bi
12、t,但是现在用256来表示254，255两个数，还是划得来的。从这个原理可以看出LZW算法的适用范围是原始数据串最好是有大量的子串屡次重复出现，重复的越多，压缩效果越好。反之那么越差，可能真的不减反增了。6.LZW算法中特殊标记随着新的串(string)不断被发现，标号也会不断地增长，如果原数据过大，生成的标号集string table)会越来越大，这时候操作这个集合就会产生效率问题。若何防止这个问题呢?Gif在采用lzw算法的做法是当标号集足够大的时候，就不能增大了，干脆从头开场再来，在这个位置要插入一个标号，就是去除标志CLEAR，表示从这里我重新开场构造字典，以前的所有标记作废，开场使用
13、新的标记。 这时候又有一个问题出现，足够大是多大这个标号集的大小为比较适宜呢理论上是标号集大小越大，那么压缩比率就越高，但开销也越高。 一般根据处理速度和内存空间连个因素来选定。GIF标准规定的是12位，超过12位的表达范围就推倒重来，并且GIF为了提高压缩率，采用的是变长的字长。比方说原始数据是8位，那么一开场，先加上一位再说，开场的字长就成了9位，然后开场加标号，当标号加到512时，也就是超过9为所能表达的最大数据时，也就意味着后面的标号要用10位字长才能表示了，那么从这里开场，后面的字长就是10位了。依此类推，到了212也就是4096时，在这里插一个去除标志，从后面开场，从9位再来。 G
14、IF规定的去除标志CLEAR的数值是原始数据字长表示的最大值加1，如果原始数据字长是8，那么去除标志就是256，如果原始数据字长为4那么就是16。另外GIF还规定了一个完毕标志END，它的值是去除标志CLEAR再加1。由于GIF规定的位数有1位单色图，4位16色和8位256色，而1位的情况下如果只扩展1位，只能表示4种状态，那么加上一个去除标志和完毕标志就用完了，所以1位的情况下就必须扩大到3位。其它两种情况初始的字长就为5位和9位。7、用lzw算法压缩原始数据的例如分析 输入流，也就是原始的数据为:255,24,54,255,24,255,255,24,5,123,45,255,24,5,24,54. 这个正好可以看到是gif文件中像素数组的一局部，若何对它进展压缩 因为原始数据可以用8bit来表示，故去除标志Clear=255+1 =256,完毕标志为End=256+1=257，目前标号集为 0 1 2 3 .255 CLEAR END 第一步,读取第一个字符为255,在标记表里面查找，255已经存在，我们已经认识255了，不做处理 第二步,取第二个字符，此时前缀为A,形成当前的Entry为(255,24),在标记集合不存在，我们并不认识255,24好，这次你小子来了，我就记住你，把它在标记集合中标记为258,然后输出前缀A,
