LZW 编码详解

《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+S2输出结果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在字符表中,S1=S1+S2此时已无输入输出S1的索引3H输出LZW_EOI标志的索引 LZW编码步骤设来源于二色系统的图像数据源：aabbbaabb（1）根据图像中使用的颜色数初始化一个字符串表，字符串表中的每个颜色对应一个索引。在初始字符串表的LZW_CLEAR和LZW_EOI分别为字符表初始化标志和编码结束标志。字符串索引a0Hb1HLZW_CLEAR2HLZW_EOI3H LZW编码步骤序号输入数据S2S1+S2输出结果S1生成新字符及索引1NULLNULL2HNULL（2）输出LZW_CLEAR在字串表中的索引2H。 LZW编码步骤序号输入数据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编码步骤序号输入数据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+S2=”bb”不在字符串表中，输出S1=“b”在字串表中的索引1H，并在字符串表末尾为S1+S2=“bb”添加索引6H，且S1=S2=“b”。 LZW编码步骤序号输入数据S2S1+S2输出结果S1生成新字符及索引1NULLNULL2HNULL2aaa3aaa0Haaa<4H>4bab0Hbab<5H>5bbb1Hbbb<6H>6bbbbb（7）读字符b赋给S2。S1+S2=”bb”在字符串表中，则S1=S1+S2=“bb”。 LZW编码步骤序号输入数据S2S1+S2输出结果S1生成新字符及索引1NULLNULL2HNULL2aaa3aaa0Haaa<4H>4bab0Hbab<5H>5bbb1Hbbb<6H>6bbbbb7abba6Habba<7H>（8）读字符a赋给S2。S1+S2=”bba”不在字符串表中，输出S1=“bb”在字串表中的索引6H，并在字符串表末尾为S1+S2=“bba”添加索引7H，且S1=S2=“a” LZW编码步骤序号输入数据S2S1+S2输出结果S1生成新字符及索引1NULLNULL2HNULL2aaa3aaa0Haaa<4H>4bab0Hbab<5H>5bbb1Hbbb<6H>6bbbbb7abba6Habba<7H>8aaaaa（9）读字符a赋给S2。S1+S2=”aa”在字符串表中，则S1=S1+S2=“aa” LZW编码步骤序号输入数据S2S1+S2输出结果S1生成新字符及索引1NULLNULL2HNULL2aaa3aaa0Haaa<4H>4bab0Hbab<5H>5bbb1Hbbb<6H>6bbbbb7abba6Habba<7H>8aaaaa9baab4HbAab<8H>（10）读字符b赋给S2。S1+S2=”aab”不在字符串表中，输出S1=“aa”在字串表中的索引4H，并在字符串表末尾为S1+S2=“aab”添加索引8H，且S1=S2=“b” LZW编码步骤序号输入数据S2S1+S2输出结果S1生成新字符及索引1NULLNULL2HNULL2aaa3aaa0Haaa<4H>4bab0Hbab<5H>5bbb1Hbbb<6H>6bbbbb7abba6Habba<7H>8aaaaa9baab4HbAab<8H>10bbbbb（11）读字符b赋给S2。S1+S2=”bb”，在字符串表中，则S1=S1+S2=“b” LZW编码步骤序号输入数据S2S1+S2输出结果S1生成新字符及索引1NULLNULL2HNULL2aaa3aaa0Haaa<4H>4bab0Hbab<5H>5bbb1Hbbb<6H>6bbbbb7abba6Habba<7H>8aaaaa9baab4HbAab<8H>10bbbbb116H（12）输出S1中的字符串”b”在字串表中的索引1H LZW编码步骤序号输入数据S2S1+S2输出结果S1生成新字符及索引1NULLNULL2HNULL2aaa3aaa0Haaa<4H>4bab0Hbab<5H>5bbb1Hbbb<6H>6bbbbb7abba6Habba<7H>8aaaaa9baab4HbAab<8H>10bbbbb116H123H（13）输出结束标志LZW_EOI的索引3H，编码完毕 解码步骤1）读第一个编码code=2H,无输出2）读code=0H,输出0H对应的a,oldcode=code=0H3)code=0H,输出0H对应的a,然后将oldcode=0H所对应的字符串“a”加上code=0H对应的字符串的第一个字符”a”,即”aa”添加到字典中，其索引为4H，同时oldcode=code=0H 4)读入code=1H,输出“b”,然后将oldcode=0H所对应的字符串“a”加上code=1H对应的字符串的第一个字符”b”,即”ab”添加到字典中，其索引为5H，同时oldcode=code=1H5)读入code=6H,由于字典中不存在该索引，将oldcode=1H所对应的字符串“b”加上oldcode=1H对应的字符串的第一个字符”b”,即”bb”添加到字典中，其索引为6H，同时oldcode=code=6H 6)读入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生成新字符及索引12H20Ha0H30Haaa0Haa<4H>41Habb1Hab<5H>56Hbbbb6Hbb<6H>64Hbbaaa4Hbba<7H>76Haabbb6Haab<8H>83H ①由于LZW算法的关键是通过翻译表来实对LZW算法的分析增加表中长串的数量，则压缩比也就越高，即串越长，输出越少。串，然后对其进行编码，现压缩的，而且每次找出的串是在表中最长的因此，如果我们设法 ②串表中的每一个串均具有前缀特性，即：则字的前缀K一定在串表中（称之为前缀条件）。如果Kx(K为一个串，x为一个字符）在串表中， 算术编码是一种从整个符号序列出发，采用递推形式连续编码的方法，与建立在符号和码字对应基础上的块码不同，在算术编码中，源符号和码字间的一一对应关系并不存在。1个算术码字要赋给整个信源符号码字，而每个码字本身确定了0和1之间的1个实数区间。 算术编码具体方法是将被编码的信源消息表示成实数轴0-1之间的一个间隔，消息越长，编码表示的间隔就越小，即这一间隔所采用算术编码每个符号的平均编码长度可以为小数。需的二进制位数就越多。算术编码 待编码的数据序列为“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）d=［0.8,1.0] a=［0,0.4）,b=［0.4,0.6）,c=［0.6,0.8）,d［0.8,1.0）StartN=StartB+LeftC×LEndN=StartB+RightC×L输入d:其初始间隔为［0.8,1.0)输入a:其初始间隔为［0,0.4)StartN=0.8+0×(1.0-0.8)=0.8“a”的实际编码区间在［0.8,0.88)之间“a”的取值范围应在前一符号间隔［0.8,1.0)的［0,0.4)子区间内EndN=0.8+0.4×(1.0-0.8)=0.88 a=［0,0.4）,b=［0.4,0.6）,c=［0.6,0.8）,d［0.8,1.0）StartN=StartB+LeftC×LEndN=StartB+RightC×L输入c:其初始间隔为［0.6,0.8)StartN=0.8+0.6×(0.88-0.8)=0.848“c”的取值范围应在前一符号间隔［0.8,0.88)的［0.6,0.8)子区间内EndN=0.8+0.8×(0.88-0.8)=0.864“c”的实际编码区间在［0.848,0.864)之间 a=［0,0.4）,b=［0.4,0.6）,c=［0.6,0.8）,d［0.8,1.0）StartN=StartB+LeftC×LEndN=StartB+RightC×L输入a:其初始间隔为［0,0.4)StartN=0.848+0×(0.864-0.848)=0.848“a”取值范围应在前一符号间隔［0.848,0.864)的［0,0.4)子区间内EndN=0.848+0.4×(0.864-0.848)=0.8544“a”的实际编码区间在［0.848,0.8544)之间 a=［0,0.4）,b=［0.4,0.6）,c=［0.6,0.8）,d［0.8,1.0）StartN=StartB+LeftC×LEndN=StartB+RightC×L输入b:其初始间隔为［0.4,0.6)StartN=0.848+0.4×(0.8544-0.848)=0.85056“b”取值范围应在前一符号间隔［0.848,0.8544)的［0.4,0.6)子区间内EndN=0.848+0.6×(0.8544-0.848)=0.85184“b”的实际编码区间在［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）,d［0.8,1.0）StartN=StartB+LeftC×LEndN=StartB+RightC×L新间隔的起始位置和结束位置表示前一间隔的起始位置前一间隔的长度当前编码符号的初始区间的左端和右端 第一个被压缩的符号为“d”，其初始间隔为［0.8,1.0)；第二个被压缩的符号为“a”，由于前面的符号“d”的取值区间被限制在［0.8,1.0)范围内，所以“a”的取值范围应在前一符号间隔［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)的子区间内.第四个被压缩的符号为“a”，StartN=0.848+0×(0.864-0.848)=0.848EndN=0.848+0.4×(0.864-0.848)=0.8544 第五个被压缩的符号为“b”StartN=0.848+0.4×(0.8544-0.848)=0.85056EndN=0.848+0.6×(0.8544-0.848)=0.85184数据序列“dacab”已被描述为一个实数区间［0.85056,0.85184］，在此区间内的任一实数值都惟一对应该数据序列。这样，就可以用一个实数表示这一数据序列。把区间［0.85056,0.85184］用二进制形式表示为［0.110110011011,0.110110100001］。 ［0.110110011011,0.110110100001］。0.1101101位于这个区间内并且其编码最短，故把其作为数据序列“dacab”的编码输出。不考虑“0.”，把1101101作为本例中的数据序列的算术编码。由此可见，数据序列“dacab”用7比特的二进制代码就可以表示，平均码长为1.4比特／字符。 算术编码对信源“baacc”进行算术编码（1）计算信源中各符号出现的概率P(a)=0.4，P(b)=0.2，P(c)=0.4。（2）将数据序列中的各数据符号在区间［0,1］内的间隔（赋值范围）设定为a=［0,0.4）,b=［0.4,0.6）,c=［0.6,1.0］。 算术编码(3)第一个被压缩的符号为“b”，其初始间隔为［0.4,0.6)；(4)第二个被压缩的符号为“a”，由于前面的符号“b”的取值区间被限制在［0.4,0.6)范围内，所以“a”的取值范围应在前一符号间隔［0.4,0.6)的［0,0.4)子区间内:起始位为0.4+0×(0.6-0.4)=0.4终止位为0.4+0.4×(0.6-0.4)=0.48即“a”的实际编码区间在［0.4,0.48)之间。 算术编码(5)第三个被压缩的符号为“a”，由于前面的符号“a”的取值区间被限制在［0.4,0.48)范围内，所以“a”的取值范围应在前一符号间隔［0.4,0.48)的［0,0.4)子区间内:起始位为0.4+0×(0.48-0.4)=0.4终止位为0.4+0.4×(0.48-0.4)=0.432即“a”的实际编码区间在［0.4,0.432)之间。