LZW编码详解.ppt

LZW编码行程编码适合于对二值图像的编码,如果图像是由很多块颜色或灰度相同的大面积区域组成的,采用行程编码可以达到很大的压缩比。通常,为了达到比较好的压缩效果,一般不单独使用行程编码,而是和其他编码方法结合使用。如:在JPEG中,就综合使用了行程编码以及哈夫曼编码。1977年,以色列人Lempel和Ziv共同提出了查找冗余字符和用较短的符号标记替代冗余字符的概念,简称LZ压缩技术。1985年,美国人Welch将LZ压缩技术从概念发展到实用阶段,简称LZW压缩技术。广泛用于图象压缩领域。LZW(Lempel-Ziv&Welch)编码又称字串表编码,属于一种无损编码,LZW编码与行程编码类似,也是对字符串进行编码从而实现压缩,但它在编码的同时还生成了特定字符串以及与之对应的索引字符串表。LZW编码压缩的数据并与一个字典库(库开始是空的)中字符串插入字典中。字符串数据在字典库中的位置索引,的字符串对比,LZW压缩使用字典库查找方案。它读入待如有匹配的字符串,则输出该否则将该步骤1:将词典初始化为包含所有可能的单字步骤2:当前字符C:=字符流中的下一个字符。字符,当前前缀P初始化为空。LZW编码算法令P:=C,现在的P仅包含一个字符C步骤3:判断P+C是否在词典中(1)如果“是”,则用C扩展P,即让P:=P+C(2)如果“否”,则输出与当前前缀P相对应的码字;将P+C添加到词典中;步骤4:判断码字流中是否还有码字要译(1)如果“是”,就返回到步骤2;(2)如果“否”把代表当前前缀P的码字输出到码字流;结束。LZW编码举例位置123456789字符ABBABABAC步骤位置码字词典输出1A2B3C114AB1225BB2336BA2447ABA4568ABAC763输入数据流:编码过程:初始化字符串表字符串索引a0Hb1Hc2Hd3HLZW_CLEAR4HLZW_EOI5HLZW编码实例aabcabbbbd输入数据S2S1+aababbbbbbbbd1H2H7H1HBH3H5Hbcaabbbbbdaa<6H>ab<7H>bc<8H>ca<9H>abb<AH>bb<BH>bbd<CH>S1为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在字符表中,S1=S1+S2此时已无输入输出S1的索引3H输出LZW_EOI标志的索引