LZW編碼

LZW（Lempel-Ziv & Welch）編碼又稱字串表編碼，是Welch將Lempel和Ziv所提出的無損壓縮技術(shù)改進(jìn)后的壓縮方法。GIF圖像文件采用的是一種改良的LZW壓縮算法， 通常稱為GIF-LZW壓縮算法。下面簡要介紹GIF-LZW的編碼與解碼方法。

例8-5  現(xiàn)有來源于二色系統(tǒng)的圖像數(shù)據(jù)源（假設(shè)數(shù)據(jù)以字符串表示）：aabbbaabb，試對其進(jìn)行LZW編碼及解碼。

解：1）根據(jù)圖像中使用的顏色數(shù)初始化一個字符串表（如表8-1），字符串表中的每個顏色對應(yīng)一個索引。在初始字符串表的LZW_CLEAR和LZW_EOI分別為字符表初始化標(biāo)志和編碼結(jié)束標(biāo)志。設(shè)置字符串變量S1、 S2并初始化為空。

表8-1 初始化字符串表

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

3）從圖像數(shù)據(jù)流中第一個字符開始，讀取一個字符a，將其賦給字符串變量S2。判斷S1+S2=”a”在字符串表中，則S1=S1+S2=“a” （見表8-2第二行）。

4）讀取圖像數(shù)據(jù)流中下一個字符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）輸出結(jié)束標(biāo)志LZW_EOI的索引3H，編碼完畢。

最后的編碼結(jié)果為“30016513”。

表8-2 GIF-LZW的編碼過程

    下面對上述編碼結(jié)果“20016463”進(jìn)行解碼。同樣先初始化字符串表， 結(jié)果如表8-1所示。

1）              首先讀取第一個編碼Code=3H， 由于它為LZW_CLEAR，無輸出（見表8-3第一行）。

2）              讀入下一個編碼Code=0H，由于字符串表中存在該索引，因此輸出字符串表中0H對應(yīng)的字符串“a”， 同時使OldCode=Code=0H（見表8-3第二行）。

3）              讀下一個編碼Code=0H，字符串表中存在該索引，輸出0H所對應(yīng)的字符串“a”，然后將OldCode=0H所對應(yīng)的字符串“a”加上Code=0H所對應(yīng)的字符串的第一個字符“a”，即“aa”添加到字串表中，其索引為4H，同時使oldCode=Code=0H（見表8-3第三行）。

4）              讀下一個編碼Code=1H，字串表中存在該索引，輸出1H所對應(yīng)的字符串“b”，然后將OldCode=0H所對應(yīng)的字符串“a”加上Code=1H所對應(yīng)的字符串的第一個字符“b”，即“ab”添加到字串表中，其索引為5H， 同時使OldCode=Code=1H（見表8-3第四行）。

5）              讀入下一個編碼Code=6H，由于字符串表中不存在該索引， 因此輸出OldCode=1H所對應(yīng)的字符串“b”加上OldCode的第一個字符“b”，即“bb”，同時將“bb”添加到字符串表中，其索引為6H， 同時使OldCode=Code=6H（見表8-3第五行）。

6）              讀下一個編碼Code=4H，字串表中存在該索引，輸出4H所對應(yīng)的字符串“aa”，然后將OldCode=6H所對應(yīng)的字符串“bb”加上Code=4H所對應(yīng)的字符串的第一個字符“a”，即“bba”添加到字串表中，其索引為7H， 同時使OldCode=Code=4H（見表8-3第六行）。

7）              讀下一個編碼Code=6H，字串表中存在該索引，輸出6H所對應(yīng)的字符串“bb”，然后將OldCode=4H所對應(yīng)的字符串“aa”加上Code=6H所對應(yīng)的字符串的第一個字符“b”，即“aab”添加到字串表中，其索引為8H， 同時使OldCode=Code=6H（見表8-3第七行）。

8）              讀下一個編碼Code=3H， 它等于LZW_EOI， 數(shù)據(jù)解碼完畢（見表8-3第八行）。

 最后的解碼結(jié)果為aabbbaabb。

表8-3 GIF-LZW的解碼過程