《LZW编码算法详解.docx》由会员分享，可在线阅读，更多相关《LZW编码算法详解.docx（7页珍藏版）》请在课桌文档上搜索。
1、LZW编码算法详解1.ZW（Lempel-Ziv&WeICh）编码又称字串表编码，是Welch将Lemple和Ziv所提出来的无损压缩技术改良后的压缩方法。GIF图像文件采用的是一种改良的LZW压缩算法，通常称为GIFTZW压缩算法。下面简要介绍GIF-LZW的编码与解码方程解:例现有来源于二色系统的图像数据源（假设数据以字符串表示）：aabbbaabb,试对其进展LZW编码及解码。1）根据图像中使用的颜色数初始化一个字串表如表1）,字串表中的每个颜色对应一个索引。在初始字串表的LZW_CLEAR和LZW_EOI分别为字串表初始化标志和编码完毕标志。设置字符串变量SI、S2并初始加为空。2）输
2、出LZTLCLEAR在字串表中的索引3H（见表2第一行）。3）从图像数据流中第一个字符开场，读取一个字符a,将其赋给字符串变量S2。判断Sl+S2=a在字符表中，那么S1=S1+S2=（见表2第二行）。4读取图像数据流中下一个字符a,将其赋给字符串变量S2o判断Sl+S2=aa不在字符串表中，输出Sl=a在字串表中的索引OH,并在字串表末尾为Sl+S2=aa添加索引4H,且S1=S2=（见表2第三行）。5）读下一个字符b赋给S2。判断Sl+S2=ab不在字符串表中，输出Sl=a在字串表中的索引0H,并在字串表末尾为Sl+S2=ab添加索引5H,且Sl=S2=b（见表2第四行）.6）读下一个字符
3、b赋给S2。Sl+S2=bb不在字串表中，输出Sl=b在字串表中的索引1H,并在字串表末尾为Sl+S2=bb添加索引6H,且S1=S2=b（见表2第五行）。7）读字符b赋给S2。Sl+S2=bb在字串表中，那么S1=S1+S2=bb（见表2第六行）。8）读字符a赋给S2。Sl+S2=bba不在字串表中，输出Sl=bb在字串表中的索引6H,并在字串表末尾为SI表末“bba添加索引7H,且S1=S2=a（见表2第七行）。9）读字符a赋给S2。Sl+S2=aa”在字串表中，那么S1=S1+S2=aa见表2第八行）。10）读字符b赋给S2。Sl+S2=aab不在字串表中，输出Sl=aa在字串表中的索引
4、4H,并在字串表末尾为Sl+S2=aab添加索引8H,且S1=S2=b（见表2第九行）。11）读字符b赋给S2。Sl+S2=bb,在字串表中，那么S1=S1+S2=b（见表2第十行）。12）输出Sl中的字符串b在字串表中的索引IH（见表2第H一行）。13）输出完毕标志LZW_EOI的索引3H,编码完毕。最后的编码结果为30016463下面对上述编码结果“30016463进展解码。同样先初始化字符串表，结果如表1所示。1）首先读取第一个编码COde=3H,由于它为LZW/LEAR,无输出见表3第一行）。2）读入下一个编码Code=0H,由于字符串表中存在该索引，因此输出字符串表中OH对应的字符串
5、a，同时使OldCode=COde=OH（见表3第二行）。3）读下一个编码Cocle=OH,字符串表中存在该索引，输出OH所对应的字符串然后将OldCode=OH所对应的字符串加上Code=OH所对应的字符串的第一个字符a，即aa添加到字串表中，其索引为4H,同时使OldCode=Code=OH（见表3第三行）。4）读下一个编码COde=IH,字串表中存在该索引，输出IH所对应的字符串b，然后将OldCode=OH所对应的字符串a加上Code=IH所对应的字符串的第一个字符b，即ab添加到字串表中，其索引为5H,同时使OldCode=Code=IH（见表3第四行）。5）读入下一个编码Code=
6、6H,由于字串表中不存在该索引，因此输出OldCode=IH所对应的字符串b加上OldCode的第一个字符b“，即bb，同时将bb添加到字符串表中，其索引为6H,同时使Oldeode=Code=6H（见表3第五行）。6）读下一个编码CoCle=4H,字串表中存在该索引，输出4H所对应的字符串aa”,然后将01dCode=6H所对应的字符串bb加上Code=4H所对应的字符串的第一个字符a，即bba添加到字串表中，其索引为7H,同时使Oldeode=COde=4H（见表3第六行）。7）读下一个编码Code=6H,字串表中存在该索引，输出6H所对应的字符串bb，然后将OldCodeMH所对应的字符
7、串aa加上Code=6H所对应的字符串的第一个字符b，即aab添加到字串表中，其索引为8H,同时使01dCode=Code=6H（见表3第七行）。8）读下一个编码COde=3H,它等于LZW_EOI,数据解码完毕（见表3第八行）。最后的解码结果为aabbbaabbo由此可见，LZW编码算法在编码与解码过程中所建设的字符串表是一样的，都是动态生成的，因此在压缩文件中不必保存字符串表。1 .LZW的全称是什么？LemPel-ZiV-WelCh(LZW).LZW的简介和压缩原理是什么LZW压缩算法是种新颖的压缩方法，由1.emple-Ziv-Welch三人共同创造，用他们的名字命名。它采用了种先进的
8、串表压缩，g每个第次出现的串放在个串表中，用个数字来表示串，压缩文件只存贮数字，那么不存贮串，从而使图象文件的压缩效率得到较大的提高。奇妙的是，不管是在压缩还是在解压缩的过程中都能正确的建设这个串表，压缩或解压缩完成后，这个串表又被丢弃。1.ZW算法中，首先建设一个字符串表，把每一个第一次出现的字符串放入串表中，并用一个数字来表示，这个数字与此字符串在串表中的位置有关，并将这个数字存入压缩文件中，如果这个字符串再次出现时，即可用表示它的数字来代替，并将这个数字存入文件中。压缩完成后将串表丢弃。如Print”字符串，如果在压缩时用266表示，只要再次出现，均用266表示，并将print”字符串存
9、入串表中，在图象解码时遇到数字266,即可从串表中查出266所代表的字符串Prin匕在解压缩时，串表可以根据压缩数据重新生成。2 .在详细介绍算法之前，先列出一些与该算法相关的概念和词汇I)CharaCteL字符，一种根基数据元素，在普通文本文件中，它占用1个单独的byte,而在图像中，它却是一种代表给定像素颜色的索引值。2)CharStreamV数据文件中的字符流。3)Prefi前缀。如这个单词的含义一样，代表着在一个字符最直接的前一个字符。一个前缀字符长度可以为0,一个prefix和一个character可以组成个字符串(String),4),Suffi:后缀，是一个字符，一个字符串可以由
10、(AB)来组成，A是前缀,B是后缀,当A长度为0的时候，代表Root,根5)Code:码,用于代表一个字符串的位置编码6)Enuy:一个Code和它所代表的字符串(String)3 .压缩算法的简单例如，不是完全实现LZW算法，只是从最直观的角度看IZW算法的思想对原始数据Abccaabcddaaccdb进展lzw压缩原始数据中，只包括4个字符(CharaCter),A,B,CQ,四个字符可以用个2bit的数表示，0-A,1-B,2-C,3-D,从最直观的角度看，原始字符串存在重复字符：Abccaabcddaaccdb,用4代表ab,5代表cc,上面的字符串可以替代表示为：45A4CDDAA5
11、DB,这样是不是就比原数据短了一些呢！4 .LZW算法的适用范围为了区别代表串的值(COde)和原来的单个的数据值(StrinQ),需要使它们的数值域不重合,上面用0-3来代表A-D,那么AB就必须用大于3的数值来代替，再举另外一个例子，原来的数值范围可以用8bit来表示，那么就认为原始的数的范围是。255,压缩程序生成的标号的范围就不能为。255(如果是0-255,就重复了)。只能从256开场，但是这样一来就超过了8位的表示范围了，所以必须要扩展数据的位数，至少扩展一位，但是这样不是增加了1个字符占用的空间了么但是却可以用一个字符代表几个字符，比方原来255是8t但是现在用256米表示254
12、,255两个数，还是划得来的。从这个原理可以看出LZW算法的适用范围是原始数据串最好是有大量的子串屡次重复出现，重复的越多，压缩效枷反之那么越差，可能真的不减反增了。6.LZW算法中特殊标记随着新的串(StrMa)不断被发现,标号也会不断地j长，如果原数据过大，生成的标号集(StlInatabl9越来越大，这时钥作这个集合就会产生效率问题,若何防止这个问题呢?Gif在采用IZW算法的做法是当标号集足够大的时候，就不能增大了，干脆从头开场再来，在这个位置要插入一个标号，就是去除标志CLEAR,表示从这里我重新开场构造字典，以前的所有标记作废，开场使用新的标记。这时候又有一个问题出现，足够大是多大
13、这个标号集的大小为比较适宜呢理论上是标号集大小越大，那么压缩比率就越高，但开销也越高。一般根据处理速度和内存空间连个因素来选定。GIF标准规定的是12位，超过12位的表达范围就推倒重来，并且GlF为了提高压缩率，采用的是变长的字长。比方说原始数据是8位，那么一开场，先加上一位再说，开场的字长就成了9位，然后开场加标号，当标号加到512时，也就是超过9为所能表达的最大数据时，也就意味着后面的标号要用10位字长才能表示了，那么从这里开场，后面的字长就是10位了。依此类推，到了272也就是4096时，在这里插一个去除标志，从后面开场，从9位再来。GIF规定的去除标志CLEAR的数值是原始数据字长表示
14、的最大值加1,如果原始数据字长是8,那么去除标志就是256,如果原始数据字长为4那么就是16。另外GIF还规定了一个完毕标志END,它的值是去除标志CLEAR再加1。由于GIF规定的位数有1位(单色图)，4位(16色)和8位256色)，而1位的情况下如果只扩展1位，只能表示4种状态，那么加上一个去除标志和完毕标志就用完了，所以1位的情况下就必须扩大到3位。其它两种情况初始的字长就为5位和9位。7、用IZW算法压缩原始数据的例如分析输入流，也就是原始的数据为:255,24,54,255,24,255,255,24,5,123,45,255,24,5,24,54这个正好可以看到是gif文件中像素数
15、组的一局部，若何对它进展压缩因为原始数据可以用8bit来表示，故去除标志Clear=255+1=256,完毕标志为End=256+1=257,目前标号集为0123255CLEAREND第一步,读取第一个字符为255,在标记表里面查找，255已经存在，我们己经认识255了，不做处理第二步,取第二个字符,此时前缀为A,形成当前的Entry为(255,24),在标记集合不存在,我们并不认识255,24好，这次你小子来了，我就记住你，把它在标记集合中标记为258,然后输出前缀A,保存后缀24,并作为下一次的前缀(后缀变前缀)第三步，取第三个字符为54,当前Entry(24,54),不认识，记录(24,
16、54)为标号259,并输出24,后缀变前缀第四部：取第四个字符255,Entry=(54,255),不认识，记录(54,255)为标号260,输出54,后缀变前缀第五步取第5个字符24,entry=(255,24),啊，认识你，这不是老258么，于是把字符串规约为258,并作为前缀第六步取第六个字符255,entry=(258,255),不认识，记录(258,255)为261,输出258,后缀变前缀一直处理到最后一个字符,用一个表记录处理过程CLEAR=256,END=257第几步前缀后缀Entry认识(丫/N)输出标号1255(,255)225524(255,24)N25525832454(
17、24,54)N24259454255(54,255)N54260525524(255,24)Y6258255(258,255)N2582617255255(255,255)N255262上面这个例如有些不能完整表达，另外一个例子是原输入数据为:ABabababbbababaacdacdadcabaaabab.采用LZW算法对其进展压缩，压缩过程用一个表来表述为：注意原数据中只包含4个character,A,B,C,D用两bit即可表述，根据IZW算法，首先扩展一位变为3为,Clear=2的2次方+1=4;End=4+1=5;初始标号集因该为012345ABCDClearEnd而压缩过程为:第几
18、步1前缀A后缀Entry(,A)认识(YN)输出标号2AB(A,B)NA63BA(B,A)NB74AB(A,B)Y56A(6,A)N686AB(A,B)Y76A(6,A)Y88B(8.B)N899BB(B,B)NB1010BB(B,B)Y1110A(10,A)N101112AB(A,B)Y当进展到第12步的时候，标号集应该为01234567891011ABCDClearEndABBA6A8BBB10A1.ZW算法育LZW就是通过建设一个字符串表,用较短的代码来表示较长的字符串来实现压缩.LZW压缩算法是UniSyS的专利,有效期到2003年,所以对它的使用是有限制的字符串和编码的对应关系是在压
19、缩过程中动态生成的,并且隐含在压缩数据中,解压的时候根据表来进展恢复,算是一种无损压缩.根据LemPel-Ziv-WeIchEncoding,简称LZW的压缩算法，用任何一中语言来实现它.1.ZW压缩算法的基本概念：LZW压缩有三个重要的对象：数据流（CharStream）编码流（COdeStream）和编译表（StringTable）o在编码时，数据流是输入对象（文本文件的据序列），编码流就是输出对象（经过压缩运算的编码数据）；在解码时，编码流那么是输入对象，数据流是输出对象：而编译表是在编码和解码时都须要用借助的对象。字符（CharaCter）：最根基的数据元素，在文本文件中就是一个字节，
20、在光栅数据中就是一个像素的颜色在指定的颜色列表中的索引值；字符串（String）：由几个连续的字符组成；前缀（PrefiX）：也是一个字符串，不过通常用在另一个字符的前面，而且它的长度可以为0；根（Root）：一个长度的字符串；编码（COde）：一个数字，按照固定长度（编码长度）从编码流中取出，编译表的映射值；图案：一个字符串，按不定长度从数据流中读出,映射到编译表条目.1.ZW压缩算法的基本原理：提取原始文本文件数据中的不同字符，基于这些字符创立一个编译表，然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大小。看起来和调色板图象的实现原理差不多，但是应该注意到的是，
21、我们这里的编译表不是事先创立好的，而是根据原始文件数据动态创立的，解码时还要从已编码的数据中复原出原来的编译表.1.ZW算法1.ZW算法基于转换串表（字典）T,将输入字符串映射成定长（通常为12位）的码字。在12位4096种可能的代码中，256个代表单字符，剩下3840给出现的字符串。1.ZW字典中的字符串具有前缀性，即KT=To1.ZW算法流程：1）初始化：将所有的单字符串放入串表2）读第一个输入字符给前缀串3）Step:读下一个输入字符K;if没有这样的K（输入已穷尽）：码字（3）输出；完毕。IfK已存在于串表中：z=K;repeatStep；else3K不在于串表中：码字（3）输出；3K
22、加进串表；z=K;repeatStep.例子：ababcbababaaaaaaa1.ZW编码：a,b,c,ab,ba,abc,cb,bab,baba,aa,aaa,aaaa1.ZW压缩的特点1.ZW码能有效利用字符出现频率冗余度进展压缩，且字典是自适应生成的，但通常不能有效地利用位置冗余度。具体特点如下：I）LZW压缩技术对于可预测性不大的数据具有较好的处理效果，常用于GIF格式的图像压缩，其平均压缩比在2）1以上，最高压缩比可到达3：1。2）对于数据流中连续重复出现的字节和字串，LZW压缩技术具有很高的压缩比。3）除了用于图像数据处理以外，LZW压缩技术还被用于文本程序等数据压缩领域。4）LZW压缩技术有很多变体，例如常见的ARC、RKARCsPKZlP高效压缩程序。5）对于任意宽度和像素位长度的图像，都具有稳定的压缩过程。压缩和解压缩速度较快。6）对机器硬件条件要求不高，在Intel80386的计算机上即可进展压缩和解压缩。
