LZW 编码详解

《LZW 编码详解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、行程编码适合于对二值图像的编码，如果图像是由很多块颜色或灰度相同的大面积区域组成的，采用行程编码可以达到很大的压缩比。通常，为了达到比较好的压缩效果，一般不单独使用行程编码，而是和其他编码方法结合使用。如：在JPEG中，就综合使用了行程编码以及哈夫曼编码。1977年,以色列人Lempel和Ziv共同提出了查找冗余字符和用较短的符号标记替代冗余字符的概念，简称LZ压缩技术。1985年,美国人Welch将LZ压缩技术从概念发展到实用阶段,简称LZW压缩技术。广泛用于图象压缩领域。LZW（Lempel-Ziv&Welch）编码又称字串表编码，属于一

2、种无损编码，LZW编码与行程编码类似，也是对字符串进行编码从而实现压缩，但它在编码的同时还生成了特定字符串以及与之对应的索引字符串表。LZW编码压缩的数据并与一个字典库(库开始是空的)中字符串插入字典中。字符串数据在字典库中的位置索引，的字符串对比，LZW压缩使用字典库查找方案。它读入待如有匹配的字符串，则输出该否则将该步骤1：将词典初始化为包含所有可能的单字步骤2：当前字符C:=字符流中的下一个字符。字符，当前前缀P初始化为空。LZW编码算法令P:=C，现在的P仅包含一个字符C步骤3：判断P＋C是否在词典中（1）如果“是”，则用C扩展P，即

3、让P:=P＋C（2）如果“否”，则输出与当前前缀P相对应的码字；将P＋C添加到词典中；步骤4：判断码字流中是否还有码字要译（1）如果“是”，就返回到步骤2；（2）如果“否”把代表当前前缀P的码字输出到码字流；结束。LZW编码举例位置123456789字符ABBABABAC步骤位置码字词典输出1A2B3C114AB1225BB2336BA2447ABA4568ABAC763输入数据流：编码过程：初始化字符串表字符串索引a0Hb1Hc2Hd3HLZW_CLEAR4HLZW_EOI5HLZW编码实例aabcabbbbd输入数据S2S1+S2输出结

4、果S1生成的新字符串及索引NULLaabcabbbbdNULLNULLaaaaa4H0H0Habbccaababbbbbbbbd1H2H7H1HBH3H5Hbcaabbbbbdaa<6H>ab<7H>bc<8H>ca<9H>abbbbbbdS1为NULL,故输出结果为空S1+S2在字符表中,S1=S1+S2aa不存在,故输出S1=“a”的索引0HS1+S2不在字符表中,S1=S2=“a”ab不存在,故输出S1=“a”的索引0HS1+S2不在字符表中,S1=S2=“b”S1+S2结果已存在,故输出结果为空S1+S2在字符

5、表中,S1=S1+S2此时已无输入输出S1的索引3H输出LZW_EOI标志的索引LZW编码步骤设来源于二色系统的图像数据源：aabbbaabb（1）根据图像中使用的颜色数初始化一个字符串表，字符串表中的每个颜色对应一个索引。在初始字符串表的LZW_CLEAR和LZW_EOI分别为字符表初始化标志和编码结束标志。字符串索引a0Hb1HLZW_CLEAR2HLZW_EOI3HLZW编码步骤序号输入数据S2S1+S2输出结果S1生成新字符及索引1NULLNULL2HNULL（2）输出LZW_CLEAR在字串表中的索引2H。LZW编码步骤序号输入数

6、据S2S1+S2输出结果S1生成新字符及索引1NULLNULL2HNULL2aaa（3）从图像数据流中第一个字符开始，读取一个字符a，将其赋给字符串变量S2。判断S1+S2=”a”在字符串表中，则S1=S1+S2=“a”LZW编码步骤序号输入数据S2S1+S2输出结果S1生成新字符及索引1NULLNULL2HNULL2aaa3aaa0Haaa<4H>（4）读下一个字符a，将其赋给S2。判断S1+S2=”aa”不在字符串表中，输出S1=“a”在字串表中的索引0H，并在字符串表末尾为S1+S2=“aa”添加索引4H，且S1=S2=“a”LZW编

7、码步骤序号输入数据S2S1+S2输出结果S1生成新字符及索引1NULLNULL2HNULL2aaa3aaa0Haaa<4H>4bab0Hbab<5H>（5）读下一个字符b赋给S2。判断S1+S2=”ab”不在字符串表中，输出S1=“a”在字串表中的索引0H，并在字符串表末尾为S1+S2=“ab”添加索引5H，且S1=S2=“b”LZW编码步骤序号输入数据S2S1+S2输出结果S1生成新字符及索引1NULLNULL2HNULL2aaa3aaa0Haaa<4H>4bab0Hbab<5H>5bbb1HbBb<6H>（6）读下一个字符b赋给S2。S1

8、+S2=”bb”不在字符串表中，输出S1=“b”在字串表中的索引1H，并在字符串表末尾为S1+S2=“bb”添加索引6H，且S1=S2=“b”。LZW编码步骤序号输