欢迎来到天天文库
浏览记录
ID:49689377
大小:92.00 KB
页数:8页
时间:2020-03-03
《LZW编码算法详解.doc》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、LZW编码算法详解LZW(Lempel-Ziv&Welch)编码又称字串表编码,是Welch将Lemple和Ziv所提出来的无损压缩技术改进后的压缩方法。GIF图像文件采用的是一种改良的LZW压缩算法,通常称为GIF-LZW压缩算法。下面简要介绍GIF-LZW的编码与解码方程解:例现有来源于二色系统的图像数据源(假设数据以字符串表示):aabbbaabb,试对其进行LZW编码及解码。1)根据图像中使用的颜色数初始化一个字串表(如表1),字串表中的每个颜色对应一个索引。在初始字串表的LZW_CLEAR和LZW_EOI分别为
2、字串表初始化标志和编码结束标志。设置字符串变量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="aa"添加索引4H,且S1=S2=“a”(见表2第三行)。5)读下一个字符
3、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”不在字串表中,
4、输出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第十行)。 1
5、2)输出S1中的字符串"b"在字串表中的索引1H(见表2第十一行)。 13)输出结束标志LZW_EOI的索引3H,编码完毕。 最后的编码结果为"30016463“。下面对上述编码结果"30016463"进行解码。同样先初始化字符串表,结果如表1所示。 1)首先读取第一个编码Code=3H,由于它为LZW_CLEAR,无输出(见表3第一行)。 2)读入下一个编码Code=0H,由于字符串表中存在该索引,因此输出字符串表中0H对应的字符串"a",同时使OldCode=Code=0H(见表3第二行)。 3)读下一个
6、编码Code=0H,字符串表中存在该索引,输出0H所对应的字符串"a",然后将OldCode=0H所对应的字符串"a"加上Code=0H所对应的字符串的第一个字符"a",即"aa"添加到字串表中,其索引为4H,同时使OldCode=Code=0H(见表3第三行)。 4)读下一个编码Code=1H,字串表中存在该索引,输出1H所对应的字符串"b",然后将OldCode=0H所对应的字符串"a"加上Code=1H所对应的字符串的第一个字符"b",即"ab"添加到字串表中,其索引为5H,同时使OldCode=Code=1H
7、(见表3第四行)。 5)读入下一个编码Code=6H,由于字串表中不存在该索引,因此输出OldCode=1H所对应的字符串"b"加上OldCode的第一个字符"b“,即"bb",同时将"bb"添加到字符串表中,其索引为6H,同时使OldCode=Code=6H(见表3第五行)。 6)读下一个编码Code=4H,字串表中存在该索引,输出4H所对应的字符串"aa",然后将OldCode=6H所对应的字符串"bb"加上Code=4H所对应的字符串的第一个字符"a",即"bba"添加到字串表中,其索引为7H,同时使Old
8、Code=Code=4H(见表3第六行)。 7)读下一个编码Code=6H,字串表中存在该索引,输出6H所对应的字符串"bb",然后将OldCode=4H所对应的字符串"aa"加上Code=6H所对应的字符串的第一个字符"b",即"aab"添加到字串表中,其索引为8H,同时使OldCode=Code=6H(见表3
此文档下载收益归作者所有