LZW编码

LZW（Lempel-Ziv & Welch）编码又称字串表编码，是Welch将Lempel和Ziv所提出的无损压缩技术改进后的压缩方法。GIF图像文件采用的是一种改良的LZW压缩算法， 通常称为GIF-LZW压缩算法。下面简要介绍GIF-LZW的编码与解码方法。

例8-5  现有来源于二色系统的图像数据源（假设数据以字符串表示）：aabbbaabb，试对其进行LZW编码及解码。

解：1）根据图像中使用的颜色数初始化一个字符串表（如表8-1），字符串表中的每个颜色对应一个索引。在初始字符串表的LZW_CLEAR和LZW_EOI分别为字符表初始化标志和编码结束标志。设置字符串变量S1、 S2并初始化为空。

表8-1 初始化字符串表

2）输出LZW_CLEAR在字串表中的索引3H（见表8-2第一行）。

3）从图像数据流中第一个字符开始，读取一个字符a，将其赋给字符串变量S2。判断S1+S2=”a”在字符串表中，则S1=S1+S2=“a” （见表8-2第二行）。

4）读取图像数据流中下一个字符a，将其赋给字符串变量S2。判断S1+S2=”aa”不在字符串表中，输出S1=“a”在字串表中的索引0H，并在字符串表末尾为S1+S2=“aa”添加索引4H，且S1= S2=“a” （见表8-2第三行）。

5）读下一个字符b赋给S2。判断S1+S2=”ab”不在字符串表中，输出S1=“a”在字串表中的索引0H，并在字符串表末尾为S1+S2=“ab”添加索引5H，且S1= S2=“b” （见表8-2第四行）。

6）读下一个字符b赋给S2。S1+S2=”bb”不在字符串表中，输出S1=“b”在字串表中的索引1H，并在字符串表末尾为S1+S2=“bb”添加索引6H，且S1= S2=“b” （见表8-2第五行）。

7）读字符b赋给S2。S1+S2=”bb”在字符串表中，则S1= S1+S2=“bb” （见表8-2第六行）。

8）读字符a赋给S2。S1+S2=”bba”不在字符串表中，输出S1=“bb”在字串表中的索引6H，并在字符串表末尾为S1+S2=“bba”添加索引7H，且S1= S2=“a” （见表8-2第七行）。

9）读字符a赋给S2。S1+S2=”aa”在字符串表中，则S1= S1+S2=“aa” （见表8-2第八行）。

10）读字符b赋给S2。S1+S2=”aab”不在字符串表中，输出S1=“aa”在字串表中的索引4H，并在字符串表末尾为S1+S2=“aab”添加索引8H，且S1= S2=“b” （见表8-2第九行）。

11）读字符b赋给S2。S1+S2=”bb”，在字符串表中，则 S1= S1+S2=“b” （见表8-2第十行）。

12）输出S1中的字符串”b”在字串表中的索引1H（见表8-2第十一行）。

13）输出结束标志LZW_EOI的索引3H，编码完毕。

最后的编码结果为“30016513”。

表8-2 GIF-LZW的编码过程

    下面对上述编码结果“20016463”进行解码。同样先初始化字符串表， 结果如表8-1所示。

1）              首先读取第一个编码Code=3H， 由于它为LZW_CLEAR，无输出（见表8-3第一行）。

2）              读入下一个编码Code=0H，由于字符串表中存在该索引，因此输出字符串表中0H对应的字符串“a”， 同时使OldCode=Code=0H（见表8-3第二行）。

3）              读下一个编码Code=0H，字符串表中存在该索引，输出0H所对应的字符串“a”，然后将OldCode=0H所对应的字符串“a”加上Code=0H所对应的字符串的第一个字符“a”，即“aa”添加到字串表中，其索引为4H，同时使oldCode=Code=0H（见表8-3第三行）。

4）              读下一个编码Code=1H，字串表中存在该索引，输出1H所对应的字符串“b”，然后将OldCode=0H所对应的字符串“a”加上Code=1H所对应的字符串的第一个字符“b”，即“ab”添加到字串表中，其索引为5H， 同时使OldCode=Code=1H（见表8-3第四行）。

5）              读入下一个编码Code=6H，由于字符串表中不存在该索引， 因此输出OldCode=1H所对应的字符串“b”加上OldCode的第一个字符“b”，即“bb”，同时将“bb”添加到字符串表中，其索引为6H， 同时使OldCode=Code=6H（见表8-3第五行）。

6）              读下一个编码Code=4H，字串表中存在该索引，输出4H所对应的字符串“aa”，然后将OldCode=6H所对应的字符串“bb”加上Code=4H所对应的字符串的第一个字符“a”，即“bba”添加到字串表中，其索引为7H， 同时使OldCode=Code=4H（见表8-3第六行）。

7）              读下一个编码Code=6H，字串表中存在该索引，输出6H所对应的字符串“bb”，然后将OldCode=4H所对应的字符串“aa”加上Code=6H所对应的字符串的第一个字符“b”，即“aab”添加到字串表中，其索引为8H， 同时使OldCode=Code=6H（见表8-3第七行）。

8）              读下一个编码Code=3H， 它等于LZW_EOI， 数据解码完毕（见表8-3第八行）。

 最后的解码结果为aabbbaabb。

表8-3 GIF-LZW的解码过程