LZW数据压缩算法

在 LZW算法中使用的术语与LZ78使用的相同，仅增加了一个术语—前缀根(Root)，它是由单个字符串组成的缀-符串(String)。在编码原理上，LZW与LZ78相比有如下差别：①LZW只输出代表词典中的缀-符串(String)的码字(code word)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根(Root)。②由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀(one-character prefix)，因此在词典中搜索的第1个缀-符串有两个字符。
　　现将LZW编码算法和译码算法介绍如下。
　　1. 编码算法
　　LZW编码是围绕称为词典的转换表来完成的。这张转换表用来存放称为前缀(Prefix)的字符序列，并且为每个表项分配一个码字(Code word)，或者叫做序号，如表4-15所示。这张转换表实际上是把8位ASCII字符集进行扩充，增加的符号用来表示在文本或图像中出现的可变长度 ASCII字符串。扩充后的代码可用9位、10位、11位、12位甚至更多的位来表示。Welch的论文中用了12位，12位可以有4096个不同的12 位代码，这就是说，转换表有4096个表项，其中256个表项用来存放已定义的字符，剩下3840个表项用来存放前缀(Prefix)。

表4-15 词典

码字(Code word )	前缀(Prefix )
1
…	…
193	A
194	B
…	…
255
…	…
1305	abcdefxyF01234
…	…

　　LZW编码器(软件编码器或硬件编码器)就是通过管理这个词典完成输入与输出之间的转换。LZW编码器的输入是字符流 (Charstream)，字符流可以是用8位ASCII字符组成的字符串，而输出是用n位(例如12位)表示的码字流(Codestream)，码字代表单个字符或多个字符组成的字符串。
　　LZW编码器使用了一种很实用的分析(parsing)算法，称为贪婪分析算法(greedy parsing algorithm)。在贪婪分析算法中，每一次分析都要串行地检查来自字符流(Charstream)的字符串，从中分解出已经识别的最长的字符串，也就是已经在词典中出现的最长的前缀(Prefix)。用已知的前缀(Prefix)加上下一个输入字符C也就是当前字符(Current character)作为该前缀的扩展字符，形成新的扩展字符串——缀-符串(String)：Prefix.C。这个新的缀-符串(String)是否要加到词典中，还要看词典中是否存有和它相同的缀-符串String。如果有，那么这个缀-符串(String)就变成前缀(Prefix)，继续输入新的字符，否则就把这个缀-符串(String)写到词典中生成一个新的前缀(Prefix)，并给一个代码。
　　LZW编码算法的具体执行步骤如下：
　　步骤1： 开始时的词典包含所有可能的根(Root)，而当前前缀P是空的；
　　步骤2： 当前字符(C) :=字符流中的下一个字符；
　　步骤3： 判断缀-符串P+C是否在词典中
　　　(1) 如果“是”：P := P+C // (用C扩展P)；
　　　(2) 如果“否”
　　　　① 把代表当前前缀P的码字输出到码字流;
　　　　② 把缀-符串P+C添加到词典;
　　　　③ 令P := C //(现在的P仅包含一个字符C);
　　步骤4： 判断码字流中是否还有码字要译
　　　(1) 如果“是”，就返回到步骤2；
　　　(2) 如果“否”
　　　　① 把代表当前前缀P的码字输出到码字流;
　　　　② 结束。
　　LZW编码算法可用伪码表示。开始时假设编码词典包含若干个已经定义的单个码字。例如，256个字符的码字，用伪码可以表示成：

　　Dictionary[j]

　　2. 译码算法

　　Dictionary[j]

表4-16 被编码的字符串

位置	1	2	3	4	5	6	7	8	9
字符	A	B	B	A	B	A	B	A	C

表4-17 LZW的编码过程

步骤	位置	词典	输出
		(1)	A
		(2)	B
		(3)	C
1	1	(4)	A B	(1)
2	2	(5)	B B	(2)
3	3	(6)	B A	(2)
4	4	(7)	A B A	(4)
5	6	(8)	A B A C	(7)
6	--	--	--	(3)

　　表4-18解释了译码过程。每个译码步骤译码器读一个码字，输出相应的缀-符串，并把它添加到词典中。例如，在步骤4中，先前码字(2)存储在先前码字(pW )中，当前码字(cW )是(4)，当前缀-符串string.cW 是输出(“A B”)，先前缀-符串string.pW ("B")是用当前缀-符串string.cW ("A")的第一个字符，其结果("B A") 添加到词典中，它的索引号是(6)

表4-18 LZW的译码过程

步骤	代码	词典	输出
		(1)	A
		(2)	B
		(3)	C
1	(1)	--	--	A
2	(2)	(4)	A B	B
3	(2)	(5)	B B	B
4	(4)	(6)	B A	A B
5	(7)	(7)	A B A	A B A
6	(3)	(8)	A B A C	C

　　LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因为它不需要执行那么多的缀-符串比较操作。对LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀-符串。在GIF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法。
　　LZW算法取得了专利，专利权的所有者是美国的一个大型计算机公司—Unisys(优利系统公司)，除了商业软件生产公司之外，可以免费使用LZW算法

 

(完）

create@2010-10-28