4 LZW算法
使用的术语与LZ78的类似，仅增加了一个术语—前缀根(Root)，它是由单个字符串组成的缀-符串(String)
4.1 编码原理
LZW只输出代表字典中的缀-符串(String)的码字(code word)
意味着在开始时字典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根(Root)
由于所有可能出现的单个字符都事先包含在字典中，每个编码步骤开始时都使用一字符前缀(one-character prefix)，因此在字典中搜索的第1个缀-符串有两个字符
4.2 编码算法
LZW编码是围绕称为
字典的转换表
来完成的
这张转换表用来存放称为前缀(Prefix)的字符序列，并且为每个表项分配一个码字(Code word)，或者叫做序号
这张转换表实际上是把8位ASCII字符集进行扩充，增加的符号用来表示在文本或图像中出现的可变长度ASCII字符串
扩充后的代码可用9位、10位、11位、12位甚至更多的位来表示
Welch的论文中用了12位，12位可以有4096个不同的12位代码，这就是说，转换表有4096个表项，其中256个表项用来存放已定义的字符，剩下3840个表项用来存放前缀(Prefix)
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)，并给一个代码
算法的执行
步骤1
开始时的字典包含所有可能的根(Root)，而当前前缀P是空的
步骤2
当前字符© :=字符流中的下一个字符
步骤3
判断缀-符串P+C是否在字典中
(1) “是” ：P := P+C
(2) “否”
① 把代表当前前缀P的码字输出到码字流;
② 把缀-符串P+C添加到字典;
③ 令P := C
步骤4
码字流中是否还有码字要译
(1) “是” 回到步骤2
① 把代表当前前缀P的码字输出到码字流
② 结束
LZW编码算法可用伪码表示
开始时假设编码字典包含若干个已经定义的单个码字
4.3 译码算法
-
当前码字(Current code word)
当前正在处理的码字，用cW表示，用string.cW表示当前缀-符串
-
先前码字(Previous code word)
先于当前码字的码字，用pW表示，用string.pW表示先前缀-符串
算法开始时，译码字典与编码字典相同，包含所有可能的前缀根(roots)
在译码过程中会记住先前码字(pW)，从码字流中读当前码字(cW)
之后输出当前缀-符串string.cW，然后把用string.cW的第一个字符扩展的先前缀-符串string.pW添加到字典中。
执行步骤
步骤1：在开始译码时字典包含所有可能的前缀根(Root)。
步骤2：cW :=码字流中的第一个码字。
步骤3：输出当前缀-符串string.cW到码字流。
步骤4： 先前码字pW := 当前码字cW。
步骤5： 当前码字cW := 码字流中的下一个码字。
步骤6： 判断先前缀-符串string.pW是否在字典中
(1) 如果“是”，则：
① 把先前缀-符串string.pW输出到字符流。
② 当前前缀P :=先前缀-符串string.pW。
③ 当前字符C :=当前前缀-符串string.cW的第一个字符。
④ 把缀-符串P+C添加到字典。
(2) 如果“否”，则：
① 当前前缀P :=先前缀-符串string.pW。
② 当前字符C :=当前缀-符串string.cW的第一个字符。
③ 输出缀-符串P+C到字符流，然后把它添加到字典中。
步骤7： 判断码字流中是否还有码字要译
(1) 如果“是”，就返回到步骤4。
(2) 如果“否”, 结束。
例
“字典” 添加到字典中的缀-符串，它的索引在括号中
每个译码步骤译码器读一个码字，输出相应的缀-符串，并把它添加到字典中
例如，在步骤4中，先前码字(2)存储在先前码字(pW)中，当前码字(cW)是(4)，当前缀-符串string.cW是输出(“A B”)，先前缀-符串string.pW (“B”)是用当前缀-符串string.cW (“A”)的第一个字符，其结果(“B A”) 添加到字典中，它的索引号是(6)
LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因为它不需要执行那么多的缀-符串比较操作
对LZW算法进一步的改进是增加可变的码字长度，以及在字典中删除老的缀-符串
在GIF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法