LZW-编码详解

1、LZWLZW编码编码 行程编码适合于对行程编码适合于对二值图像的编码二值图像的编码，如果，如果图像是由很多块颜色或灰度相同的大面积区域图像是由很多块颜色或灰度相同的大面积区域组成的，采用行程编码可以达到很大的压缩比。组成的，采用行程编码可以达到很大的压缩比。 通常，为了达到比较好的压缩效果，一般通常，为了达到比较好的压缩效果，一般不单独使用行程编码不单独使用行程编码，而是和其他编码方法结合，而是和其他编码方法结合使用。如：在使用。如：在JPEGJPEG中，就综合使用了行程编码以中，就综合使用了行程编码以及哈夫曼编码。及哈夫曼编码。19771977年年, ,以色列人以色列人LempelLempe

2、l和和ZivZiv共同提出了查找冗余字符共同提出了查找冗余字符和用较短的符号标记替代冗余字符的概念，简称和用较短的符号标记替代冗余字符的概念，简称LZLZ压缩压缩技术。技术。 1985 1985年年, ,美国人美国人WelchWelch将将LZLZ压缩技术从概念发展到实用压缩技术从概念发展到实用阶段阶段, ,简称简称LZWLZW压缩技术。广泛用于图象压缩领域。压缩技术。广泛用于图象压缩领域。 LZW LZW（Lempel-Ziv & WelchLempel-Ziv & Welch）编码又称字串表编码，）编码又称字串表编码，属于一种无损编码，属于一种无损编码，LZWLZW编码与行

3、程编码类似，也是对字编码与行程编码类似，也是对字符串进行编码从而实现压缩，但它在编码的同时还生成符串进行编码从而实现压缩，但它在编码的同时还生成了特定字符串以及与之对应的索引字符串表。了特定字符串以及与之对应的索引字符串表。 LZW LZW编码编码 压缩的数据并与一个字典库压缩的数据并与一个字典库( (库开始是空的库开始是空的) )中中字符串插入字典中。字符串插入字典中。字符串数据在字典库中的字符串数据在字典库中的位置索引位置索引，的字符串对比，的字符串对比，LZWLZW压缩使用压缩使用字典库字典库查找方案。查找方案。它读入待它读入待如有匹配的字符串，则输出该如有匹配的字符串，则输出该否则将该

4、否则将该 步骤步骤1：将词典初始化为包含所有可能的单字：将词典初始化为包含所有可能的单字步骤步骤2 2：当前字符当前字符C:=C:=字符流中的下一个字符。字符流中的下一个字符。字符，当前前缀字符，当前前缀P P初始化为空。初始化为空。LZWLZW编码算法编码算法令令P:=CP:=C，现在的，现在的P P仅包含仅包含一个字符一个字符C C步骤步骤3 3：判断判断P PC C是否在词典中是否在词典中（1 1）如果）如果“是是”，则用，则用C C扩展扩展P P，即让，即让P:=PP:=PC C（2 2）如果）如果“否否”，则，则输出与当前前缀输出与当前前缀P P相对应的码字；相对应的码字；将将P P

5、C C添加到词典中；添加到词典中；步骤步骤4 4：判断码字流中是否还有码字要译：判断码字流中是否还有码字要译（1 1）如果）如果“是是”，就返回到步骤，就返回到步骤2 2；（2 2）如果）如果“否否”把代表当前前缀把代表当前前缀P P的码字输出到码字流；的码字输出到码字流；结束。结束。LZWLZW编码举例编码举例位置位置123456789字符字符ABBABABAC步骤步骤位置位置码字码字词典词典输出输出1A2B3C114AB1225BB2336BA2447ABA4568ABAC763输入数据流：输入数据流：编码过程：编码过程：初始化字符串表初始化字符串表 字符串 索引 a 0 H b1 H c

6、2 H d3 H LZW_CLEAR 4 H LZW_EOI 5 H LZW编码实例编码实例 aabcabbbbd 输入数据输入数据S2S2S1+S2S1+S2输出结果输出结果S1S1生成的新字符串及索引生成的新字符串及索引NULLNULLa aa ab bc ca ab bb bb bb bd dNULLNULLNULLNULLa aa aa aaaaa4H4H0H0H0H0Hababbcbccacaabababbabbbbbbbbbbbbdbbd1H1H2H2H7H7H1H1HBHBH3H3H5H5Hb bc ca aababb bb bbbbbd daa aa ab ab bc bc c

7、a ca abb abb bb bb bbd bbd S1S1为为NULL,NULL,故故输出结果为空输出结果为空S1+S2S1+S2在字符表在字符表中中,S1=S1+S2,S1=S1+S2aaaa不存在不存在, ,故输出故输出S1=“a”S1=“a”的索引的索引0H0HS1+S2S1+S2不在字符不在字符表中表中,S1=S2=“a”,S1=S2=“a”abab不存在不存在, ,故输出故输出S1=“a”S1=“a”的索引的索引0H0HS1+S2S1+S2不在字符不在字符表中表中,S1=S2=“b”,S1=S2=“b”S1+S2S1+S2结果已存结果已存在在, ,故输出结果故输出结果为空为空S1

8、+S2S1+S2在字符表在字符表中中,S1=S1+S2,S1=S1+S2此时已无此时已无输入输入输出输出S1S1的索的索引引3H3H输出输出LZW_EOILZW_EOI标志的索引标志的索引LZWLZW编码步骤编码步骤设来源于二色系统的图像数据源设来源于二色系统的图像数据源 ：aabbbaabbaabbbaabb（1 1）根据图像中使用的颜色数初始化一个字符串表，）根据图像中使用的颜色数初始化一个字符串表， 字符串表中的每个颜色对应一个索引。字符串表中的每个颜色对应一个索引。 在初始字符串表的在初始字符串表的LZW_CLEARLZW_CLEAR和和LZW_EOILZW_EOI分别为字符表分别为字

9、符表 初始化标志和编码结束标志。初始化标志和编码结束标志。 字符串索引a0Hb1HLZW_CLEAR2HLZW_EOI3HLZWLZW编码步骤编码步骤序号序号输入数据输入数据S2S2S1+S2S1+S2输出结果输出结果S1S1生成新字符及索引生成新字符及索引1 1NULLNULLNULLNULL2H2HNULLNULL（2 2）输出）输出LZW_CLEARLZW_CLEAR在字串表中的索引在字串表中的索引2H2H。LZWLZW编码步骤编码步骤序号序号输入数据输入数据S2S2S1+S2S1+S2输出结果输出结果S1S1生成新字符及索引生成新字符及索引1 1NULLNULLNULLNULL2H2H

10、NULLNULL2 2a aa aa a（3 3）从图像数据流中第一个字符开始，读取一个字符）从图像数据流中第一个字符开始，读取一个字符a a，将其赋给字符串变量将其赋给字符串变量S2S2。判断。判断S1+S2=S1+S2=”a a”在字符串表中，在字符串表中，则则S1=S1+S2=S1=S1+S2=“a a” LZWLZW编码步骤编码步骤序号序号输入数据输入数据S2S2S1+S2S1+S2输出结果输出结果S1S1生成新字符及索引生成新字符及索引1 1NULLNULLNULLNULL2H2HNULLNULL2 2a aa aa a3 3a aaaaa0H0Ha aaaaa（4 4）读下一个字符

11、）读下一个字符a a，将其赋给，将其赋给S2S2。判断。判断S1+S2=S1+S2=”aaaa”不在不在字符串表中，输出字符串表中，输出S1=S1=“a a”在字串表中的索引在字串表中的索引0H0H，并在字符，并在字符串表末尾为串表末尾为S1+S2=S1+S2=“aaaa”添加索引添加索引4H4H，且，且S1= S2=S1= S2=“a a” LZWLZW编码步骤编码步骤序号序号输入数据输入数据S2S2S1+S2S1+S2输出结果输出结果S1S1生成新字符及索引生成新字符及索引1 1NULLNULLNULLNULL2H2HNULLNULL2 2a aa aa a3 3a aaaaa0H0Ha

12、aaaaa4 4b babab0H0Hb babab（5 5）读下一个字符）读下一个字符b b赋给赋给S2S2。判断。判断S1+S2=S1+S2=”abab”不在字符串不在字符串表中，输出表中，输出S1=S1=“a a”在字串表中的索引在字串表中的索引0H0H，并在字符串表末，并在字符串表末尾为尾为S1+S2=S1+S2=“abab”添加索引添加索引5H5H，且，且S1= S2=S1= S2=“b b” LZWLZW编码步骤编码步骤序号序号输入数据输入数据S2S2S1+S2S1+S2输出结果输出结果S1S1生成新字符及索引生成新字符及索引1 1NULLNULLNULLNULL2H2HNULLN

13、ULL2 2a aa aa a3 3a aaaaa0H0Ha aaaaa4 4b babab0H0Hb babab5 5b bbbbb1H1Hb bBbBb（6 6）读下一个字符）读下一个字符b b赋给赋给S2S2。S1+S2=S1+S2=”bbbb”不在字符串表中，不在字符串表中，输出输出S1=S1=“b b”在字串表中的索引在字串表中的索引1H1H，并在字符串表末尾为，并在字符串表末尾为S1+S2=S1+S2=“bbbb”添加索引添加索引6H6H，且，且S1= S2=S1= S2=“b b” 。LZWLZW编码步骤编码步骤序号序号输入数据输入数据S2S2S1+S2S1+S2输出结果输出结果

14、S1S1生成新字符及索引生成新字符及索引1 1NULLNULLNULLNULL2H2HNULLNULL2 2a aa aa a3 3a aaaaa0H0Ha aaaaa4 4b babab0H0Hb babab5 5b bbbbb1H1Hb bbbbb6 6b bbbbbbbbb（7 7）读字符）读字符b b赋给赋给S2S2。S1+S2=S1+S2=”bbbb”在字符串表中，则在字符串表中，则S1= S1+S2=S1= S1+S2=“bbbb” 。LZWLZW编码步骤编码步骤序号序号输入数据输入数据S2S2S1+S2S1+S2输出结果输出结果S1S1生成新字符及索引生成新字符及索引1 1NUL

15、LNULLNULLNULL2H2HNULLNULL2 2a aa aa a3 3a aaaaa0H0Ha aaaaa4 4b babab0H0Hb babab5 5b bbbbb1H1Hb bbbbb6 6b bbbbbbbbb7 7a abbabba6H6Ha abbabba（8 8）读字符）读字符a a赋给赋给S2S2。S1+S2=S1+S2=”bbabba”不在字符串表中，输出不在字符串表中，输出S1=S1=“bbbb”在字串表中的索引在字串表中的索引6H6H，并在字符串表末尾为，并在字符串表末尾为S1+S2=S1+S2=“bbabba”添加索引添加索引7H7H，且，且S1= S2=S1

16、= S2=“a a” LZWLZW编码步骤编码步骤序号序号输入数据输入数据S2S2S1+S2S1+S2输出结果输出结果S1S1生成新字符及索引生成新字符及索引1 1NULLNULLNULLNULL2H2HNULLNULL2 2a aa aa a3 3a aaaaa0H0Ha aaaaa4 4b babab0H0Hb babab5 5b bbbbb1H1Hb bbbbb6 6b bbbbbbbbb7 7a abbabba6H6Ha abbabba8 8a aaaaaaaaa（9 9）读字符）读字符a a赋给赋给S2S2。S1+S2=S1+S2=”aaaa”在字符串表中，则在字符串表中，则S1=

17、S1+S2=S1= S1+S2=“aaaa” LZWLZW编码步骤编码步骤序号序号输入数据输入数据S2S2S1+S2S1+S2输出结果输出结果S1S1生成新字符及索引生成新字符及索引1 1NULLNULLNULLNULL2H2HNULLNULL2 2a aa aa a3 3a aaaaa0H0Ha aaaaa4 4b babab0H0Hb babab5 5b bbbbb1H1Hb bbbbb6 6b bbbbbbbbb7 7a abbabba6H6Ha abbabba8 8a aaaaaaaaa9 9b baabaab4H4Hb bAabAab（1010）读字符）读字符b b赋给赋给S2S2。

18、S1+S2=S1+S2=”aabaab”不在字符串表中，不在字符串表中，输出输出S1=S1=“aaaa”在字串表中的索引在字串表中的索引4H4H，并在字符串表末尾，并在字符串表末尾为为S1+S2=S1+S2=“aabaab”添加索引添加索引8H8H，且，且S1= S2=S1= S2=“b b” LZWLZW编码步骤编码步骤序号序号输入数据输入数据S2S2S1+S2S1+S2输出结果输出结果S1S1生成新字符及索引生成新字符及索引1 1NULLNULLNULLNULL2H2HNULLNULL2 2a aa aa a3 3a aaaaa0H0Ha aaaaa4 4b babab0H0Hb baba

19、b5 5b bbbbb1H1Hb bbbbb6 6b bbbbbbbbb7 7a abbabba6H6Ha abbabba8 8a aaaaaaaaa9 9b baabaab4H4Hb bAabAab1010b bbbbbbbbb（1111）读字符）读字符b b赋给赋给S2S2。S1+S2=S1+S2=”bbbb”，在字符串表中，在字符串表中，则则 S1= S1+S2=S1= S1+S2=“b b” LZWLZW编码步骤编码步骤序号序号输入数据输入数据S2S2S1+S2S1+S2输出结果输出结果S1S1生成新字符及索引生成新字符及索引1 1NULLNULLNULLNULL2H2HNULLNUL

20、L2 2a aa aa a3 3a aaaaa0H0Ha aaaaa4 4b babab0H0Hb babab5 5b bbbbb1H1Hb bbbbb6 6b bbbbbbbbb7 7a abbabba6H6Ha abbabba8 8a aaaaaaaaa9 9b baabaab4H4Hb bAabAab1010b bbbbbbbbb11116H6H（1212）输出）输出S1S1中的字符串中的字符串”b b”在字串表中的索引在字串表中的索引1H1H LZWLZW编码步骤编码步骤序号序号输入数据输入数据S2S2S1+S2S1+S2输出结果输出结果S1S1生成新字符及索引生成新字符及索引1 1N

21、ULLNULLNULLNULL2H2HNULLNULL2 2a aa aa a3 3a aaaaa0H0Ha aaaaa4 4b babab0H0Hb babab5 5b bbbbb1H1Hb bbbbb6 6b bbbbbbbbb7 7a abbabba6H6Ha abbabba8 8a aaaaaaaaa9 9b baabaab4H4Hb bAabAab1010b bbbbbbbbb11116H6H12123H3H（1313）输出结束标志）输出结束标志LZW_EOILZW_EOI的索引的索引3H3H，编码完毕，编码完毕 解码步骤1）读第一个编码code=2H,无输出2）读code=0H,输

22、出0H对应的a,oldcode=code=0H3)code=0H,输出0H对应的a,然后将oldcode=0H所对应的字符串“a”加上code=0H对应的字符串的第一个字符”a”,即”aa”添加到字典中，其索引为4H，同时oldcode=code=0H4)读入code=1H,输出“b”,然后将oldcode=0H所对应的字符串“a”加上code=1H对应的字符串的第一个字符”b”,即”ab”添加到字典中，其索引为5H，同时oldcode=code=1H5)读入code=6H,由于字典中不存在该索引，将oldcode=1H所对应的字符串“b”加上oldcode=1H对应的字符串的第一个字符”b”

23、,即”bb”添加到字典中，其索引为6H，同时oldcode=code=6H6)读入code=4H,输出“aa”,然后将oldcode=6H所对应的字符串“bb”加上code=4H对应的字符串的第一个字符”a”,即”bba”添加到字典中，其索引为7H，同时oldcode=code=4H7)读入code=6H,输出“bb”,然后将oldcode=4H所对应的字符串“aa”加上code=6H对应的字符串的第一个字符”b”,即”aab”添加到字典中，其索引为8H，同时oldcode=code=6H8)读入code=3H,解码完毕。解码过程行号输入数据code新串输出结果oldcode生成新字符及索引1

24、2H20Ha0H30Haaa0Haa41Habb1Hab56Hbbbb6Hbb64Hbbaaa4Hbba76Haabbb6Haab83H 由于由于LZW算法的关键是通过翻译表来实算法的关键是通过翻译表来实对对LZWLZW算法的分析算法的分析增加表中长串的数量，则压缩比也就越高，即增加表中长串的数量，则压缩比也就越高，即串越长，输出越少。串越长，输出越少。串，然后对其进行编码，串，然后对其进行编码，现压缩的，而且每次找出的串是在表中最长的现压缩的，而且每次找出的串是在表中最长的因此，如果我们设法因此，如果我们设法 串表中的每一个串均具有串表中的每一个串均具有前缀特性前缀特性，即：，即：则字的前缀

25、则字的前缀K K一定在串表中（称之为一定在串表中（称之为前缀条件前缀条件）。）。如果如果Kx(KKx(K为一个串，为一个串，x x为一个字符）在串表中，为一个字符）在串表中， 算算 术术 编编 码码 是一种从整个符号序列出发，采用递推形式连续编码的是一种从整个符号序列出发，采用递推形式连续编码的方法，与建立在符号和码字对应基础上的块码不同，在算术方法，与建立在符号和码字对应基础上的块码不同，在算术编码中，源符号和码字间的一一对应关系并不存在。编码中，源符号和码字间的一一对应关系并不存在。1 1个算个算术码字要赋给整个信源符号码字，而每个码字本身确定了术码字要赋给整个信源符号码字，而每个码字本身

26、确定了0 0和和1 1之间的之间的1 1个实数区间。个实数区间。 算术编码算术编码具体方法具体方法是将被编码的信源消息是将被编码的信源消息表示成实数轴表示成实数轴0-1之间的一个间隔，之间的一个间隔，消息越消息越长长，编码表示的间隔就越小，即这一间隔所，编码表示的间隔就越小，即这一间隔所 采用算术编码每个符号的平均编码长度采用算术编码每个符号的平均编码长度可以为可以为小数小数。需需的二进的二进制位数就越多。制位数就越多。 算算 术术 编编 码码 待编码的数据序列为待编码的数据序列为“dacab”dacab”，信源中各符号出现的概，信源中各符号出现的概率依次为率依次为P(a)=0.4P(a)=0

27、.4，P(b)=0.2P(b)=0.2，P(c)=0.2P(c)=0.2， P(d)=0.2P(d)=0.2。 数据序列中的各数据符号在区间数据序列中的各数据符号在区间0, 10, 1内的间隔（赋内的间隔（赋值范围）设定为值范围）设定为: :a=0, 0.4）b=0.4, 0.6）c=0.6, 0.8）d=0.8, 1.0 a=a=0, 0.40, 0.4）, b=, b=0.4, 0.60.4, 0.6）, c=, c=0.6, 0.80.6, 0.8）, d, d0.8, 1.00.8, 1.0）StartN=StartB+LeftCL EndN=StartB+RightCL 输入输入d:

28、d: 其初始间隔为其初始间隔为0.8, 1.0)输入输入a:a:其初始间隔为其初始间隔为0, 0.4)StartN=0.8+0(1.0-0.8)=0.8“a”“a”的实际编码区间在的实际编码区间在0.8, 0.88)0.8, 0.88)之间之间 “a a”的取值范围应在前一的取值范围应在前一符号间隔符号间隔0.8, 1.0)0.8, 1.0)的的0, 0.4)0, 0.4)子区间内子区间内EndN=0.8+0.4(1.0-0.8)=0.88a=a=0, 0.40, 0.4）, b=, b=0.4, 0.60.4, 0.6）, c=, c=0.6, 0.80.6, 0.8）, d, d0.8,

29、1.00.8, 1.0）StartN=StartB+LeftCL EndN=StartB+RightCL 输入输入c:c: 其初始间隔为其初始间隔为0.6, 0.8)StartN=0.8+0.6(0.88-0.8)=0.848“c c”的取值范围应在前一的取值范围应在前一符号间隔符号间隔0.8, 0.88)0.8, 0.88)的的0.6, 0.8)0.6, 0.8)子区间内子区间内EndN=0.8+0.8(0.88-0.8)=0.864“c”“c”的实际编码区间在的实际编码区间在0.848, 0.864)0.848, 0.864)之间之间 a=a=0, 0.40, 0.4）, b=, b=0.

30、4, 0.60.4, 0.6）, c=, c=0.6, 0.80.6, 0.8）, d, d0.8, 1.00.8, 1.0）StartN=StartB+LeftCL EndN=StartB+RightCL 输入输入a:a:其初始间隔为其初始间隔为0, 0.4)StartN=0.848+0(0.864-0.848)=0.848“a a”取值范围应在前一符取值范围应在前一符号间隔号间隔0.848, 0.864)0.848, 0.864)的的0, 0.4)0, 0.4)子区间内子区间内EndN=0.848+0.4(0.864-0.848)=0.8544“a”“a”的实际编码区间在的实际编码区间在0

31、.848, 0.8544)0.848, 0.8544)之间之间 a=a=0, 0.40, 0.4）, b=, b=0.4, 0.60.4, 0.6）, c=, c=0.6, 0.80.6, 0.8）, d, d0.8, 1.00.8, 1.0）StartN=StartB+LeftCL EndN=StartB+RightCL 输入输入b:b:其初始间隔为其初始间隔为0.4, 0.6)StartN=0.848+0.4(0.8544-0.848)=0.85056“b b”取值范围应在前一符取值范围应在前一符号间隔号间隔0.848, 0.8544)0.848, 0.8544)的的0.4, 0.6)0.

32、4, 0.6)子区间内子区间内EndN=0.848+0.6(0.8544-0.848)=0.85184“b”“b”的实际编码区间在的实际编码区间在0.85056, 0.85184)0.85056, 0.85184)之间之间 设待编码的数据序列为设待编码的数据序列为“dacab”， 信源中各符号出现的信源中各符号出现的概率依次为概率依次为P(a)=0.4，P(b)=0.2，P(c)=0.2， P(d)=0.2。 数据序列中的各数据符号在区间数据序列中的各数据符号在区间0, 1内的间隔（赋值内的间隔（赋值范围）设定为范围）设定为a=0, 0.4）, b=0.4, 0.6）, c=0.6, 0.8）

33、, d0.8, 1.0）StartN=StartB+LeftCL EndN=StartB+RightCL 新间隔的起始位新间隔的起始位置和结束位置置和结束位置表示前一间隔的起表示前一间隔的起始位置始位置前一间隔的长度前一间隔的长度当前编码符号的初始区间的左端和右端当前编码符号的初始区间的左端和右端 第一个被压缩的符号为第一个被压缩的符号为“d”，其初始间隔为，其初始间隔为0.8, 1.0)； 第二个被压缩的符号为第二个被压缩的符号为“a”，由于前面的符号，由于前面的符号“d”的取值的取值区间被限制在区间被限制在0.8, 1.0)范围内，所以范围内，所以“a”的取值范围应在前一的取值范围应在前一

34、符号间隔符号间隔0.8, 1.0)的的0, 0.4)子区间内，子区间内， 根据上式可知根据上式可知 StartN=0.8+0(1.0-0.8)=0.8EndN=0.8+0.4(1.0-0.8)=0.88 “a”的实际编码区间在的实际编码区间在0.8, 0.88)之间。之间。 第三个被压缩的符号为第三个被压缩的符号为“c”， 其编码取值范围应在其编码取值范围应在0.8, 0.88)区间的区间的0.6, 0.8)的子区间内的子区间内.864. 0)8 . 088. 0(8 . 08 . 0848. 0)8 . 088. 0(6 . 08 . 0NNEndStart第四个被压缩的符号为第四个被压缩的

35、符号为“a”，StartN=0.848+0(0.864-0.848)=0.848EndN=0.848+0.4(0.864-0.848)=0.8544 第五个被压缩的符号为第五个被压缩的符号为“b”StartN=0.848+0.4(0.8544-0.848)=0.850 56EndN=0.848+0.6(0.8544-0.848)=0.851 84 数据序列数据序列“dacab”已被描述为一个实数区间已被描述为一个实数区间0.85056, 0.851 84，在此区间内的任一实数值都惟一对应该数据序列。这样，在此区间内的任一实数值都惟一对应该数据序列。这样，就可以用一个实数表示这一数据序列。把区间就可以用一个实数表示这一数据序列。把区间0.85056, 0.85184用二进制形式表示为用二进制形式表示为0.110110011011, 0.110110100001。 0.110110011011, 0.110110100001。0.1101101位于这个区间内并且其编码最短，位于这个区间内并且其编码最短， 故把其作为数故