发布时间 : 星期一 文章LZW编码算法详解更新完毕开始阅读0c9f0af0f524ccbff12184d8
LZW编码算法详解
LZW(Lempel-Ziv & Welch)编码又称字串表编码，是Welch将Lemple和Ziv所提出来的无损压缩技术改进后的压缩方法。GIF图像文件采用的是一种改良的LZW压缩算法，通常称为GIF-LZW压缩算法。下面简要介绍GIF-LZW的编码与解码方程
解：例 现有来源于二色系统的图像数据源（假设数据以字符串表示）：aabbbaabb，试对其进行LZW编码及解码。
1）根据图像中使用的颜色数初始化一个字串表（如表1），字串表中的每个颜色对应一个索引。在初始字串表的LZW_CLEAR和LZW_EOI分别为字串表初始化标志和编码结束标志。设置字符串变量S1、S2并初始化为空。
2）输出LZW_CLEAR在字串表中的索引3H(见表2第一行)。
3）从图像数据流中第一个字符开始，读取一个字符a，将其赋给字符串变量S2。判断S1+S2=“a”在字符表中，则S1=S1+S2=“a”（见表2第二行）。 4）读取图像数据流中下一个字符a，将其赋给字符串变量S2。判断S1+S2=“aa”不在字符串表中，输出S1=“a”在字串表中的索引0H，并在字串表末尾为S1+S2=\添加索引4H，且S1=S2=“a”（见表2第三行）。
5）读下一个字符b赋给S2。判断S1+S2=“ab”不在字符串表中，输出S1=“a”在字串表中的索引0H，并在字串表末尾为S1+S2=“ab”添加索引5H，且S1=S2=“b”（见表2第四行）。
6）读下一个字符b赋给S2。S1+S2=“bb”不在字串表中，输出S1=“b”在字串表中的索引1H，并在字串表末尾为S1+S2=“bb”添加索引6H，且S1=S2=“b”（见表2第五行）。
7）读字符b赋给S2。S1+S2=“bb”在字串表中，则S1=S1+S2=“bb”（见表2第六行）。
8）读字符a赋给S2。S1+S2=“bba”不在字串表中，输出S1=“bb”在字串表中的索引6H，并在字串表末尾为S1+S2=“bba”添加索引7H，且S1=S2=“a”（见表2第七行）。
9）读字符a赋给S2。S1+S2=“aa”在字串表中，则S1=S1+S2=“aa”（见表2第八行）。
10）读字符b赋给S2。S1+S2=“aab”不在字串表中，输出S1=“aa”在字串表中的索引4H，并在字串表末尾为S1+S2=“aab”添加索引8H，且S1=S2=“b”（见表2第九行）。
11）读字符b赋给S2。S1+S2=“bb”，在字串表中，则S1=S1+S2=“b”（见表2第十行）。
12）输出S1中的字符串\在字串表中的索引1H（见表2第十一行）。 13）输出结束标志LZW_EOI的索引3H，编码完毕。 最后的编码结果为\
下面对上述编码结果\进行解码。同样先初始化字符串表，结果如表1所示。
1）首先读取第一个编码Code=3H，由于它为LZW_CLEAR，无输出（见表3第一行）。
2）读入下一个编码Code=0H，由于字符串表中存在该索引，因此输出字符串表中0H对应的字符串\，同时使OldCode=Code=0H（见表3第二行）。 3）读下一个编码Code=0H，字符串表中存在该索引，输出0H所对应的字符串\，然后将OldCode=0H所对应的字符串\加上Code=0H所对应的字符串的第一个字符\，即\添加到字串表中，其索引为4H，同时使OldCode=Code=0H（见表3第三行）。
4）读下一个编码Code=1H，字串表中存在该索引，输出1H所对应的字符串\，然后将OldCode=0H所对应的字符串\加上Code=1H所对应的字符串的第一个字符\，即\添加到字串表中，其索引为5H，同时使OldCode=Code=1H（见表3第四行）。
5）读入下一个编码Code=6H，由于字串表中不存在该索引，因此输出
OldCode=1H所对应的字符串\加上OldCode的第一个字符\\，同时将\添加到字符串表中，其索引为6H，同时使OldCode=Code=6H（见表3第五行）。
6）读下一个编码Code=4H，字串表中存在该索引，输出4H所对应的字符串\，然后将OldCode=6H所对应的字符串\加上Code=4H所对应的字符串的第一个字符\，即\添加到字串表中，其索引为7H，同时使OldCode=Code=4H（见表3第六行）。
7）读下一个编码Code=6H，字串表中存在该索引，输出6H所对应的字符串\，然后将OldCode=4H所对应的字符串\加上Code=6H所对应的字符串的第一个字符\，即\添加到字串表中，其索引为8H，同时使OldCode=Code=6H（见表3第七行）。
8）读下一个编码Code=3H，它等于LZW_EOI，数据解码完毕（见表3第八行）。 最后的解码结果为aabbbaabb。
由此可见，LZW编码算法在编码与解码过程中所建立的字符串表是一样的，都是动态生成的，因此在压缩文件中不必保存字符串表。
1.LZW的全称是什么?
Lempel-Ziv-Welch (LZW).
2. LZW的简介和压缩原理是什么？
LZW压缩算法是一种新颖的压缩方法，由Lemple-Ziv-Welch 三人共同创造，用他们的名字命名。它采用了一种先进的串表压缩，将每个第一次出现的串放在一个串表中，用一个数字来表示串，压缩文件只存贮数字，则不存贮串，从而使图象文件的压缩效率得到较大的提高。奇妙的是，不管是在压缩还是在解压缩的过程中都能正确的建立这个串表，压缩或解压缩完成后，这个串表又被丢弃。
LZW算法中，首先建立一个字符串表，把每一个第一次出现的字符串放入串表中，并用一个数字来表示，这个数字与此字符串在串表中的位置有关，并将这个数字存入压缩文件中，如果这个字符串再次出现时，即可用表示它的数字来代替，并将这个数字存入文件中。压缩完成后将串表丢弃。如\字符串，如果在压缩时用266表示，只要再次出现，均用266表示，并将\字符串存入串表中，在图象解码时遇到数字266，即可从串表中查出266所代表的字符串\，在解压缩时，串表可以根据压缩数据重新生成。 3.在详细介绍算法之前，先列出一些与该算法相关的概念和词汇
1)'Character': 字符，一种基础数据元素，在普通文本文件中，它占用1个单独的byte，而在图像中，它却是一种代表给定像素颜色的索引值。 2)'CharStream':数据文件中的字符流。
3)'Prefix':前缀。如这个单词的含义一样，代表着在一个字符最直接的前一个字符。一个前缀字符长度可以为0,一个prefix和一个character可以组成一个字符串(string),