例：编码字符串如表4-11所示，编码过程如表4-12所示。现说明如下：


 “步骤”栏表示编码步骤。
 “位置”栏表示编码位置，输入数据流中的第1个字符为编码位置1。
 “匹配”栏表示窗口中找到的最长的匹配串。
 “字符”栏表示匹配之后在前向缓冲存储器中的第1个字符。
 “输出”栏的输出为：
① 如果匹配串本身的长度Length ? MIN_LENGTH，输出指向匹配串的指针，格式为(Back_chars, Chars_length)。该指针告诉译码器“在这个窗口中向后退Back_chars个字符然后拷贝Chars_length个字符到输出”。
② 如果匹配串本身的长度Length ? MIN_LENGTH，则输出真实的匹配串。

表4-11 输入数据流

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

表4-12 编码过程(MIN_LENGTH = 2)

步骤
 位置  
 匹配串
 输出
 
1
 1
 --
 A
 
2
 2
 A
 A
 
3
 3
 --
 B
 
4
 4
 B
 B
 
5
 5
 --
 C
 
6
 6
 B B
 (3,2)
 
7
 8
 A A B
 (7,3)
 
8
 11
 C
 C
 

在相同的计算机环境下，LZSS算法比LZ77可获得比较高的压缩比，而译码同样简单。这也就是为什么这种算法成为开发新算法的基础。许多后来开发的文档压缩程序都使用了LZSS的思想，例如PKZip, ARJ, LHArc和ZOO等等，其差别仅仅是指针的长短、窗口的大小等有所不同。

LZSS同样可以和熵编码联合使用，例如ARJ就与霍夫曼编码联用，而PKZip则与Shannon-Fano联用，它的后续版本也采用霍夫曼编码。

4.4.4 LZ78算法

在介绍LZ78算法之前，首先说明在算法中用到的几个术语。这些术语是：


 字符流(Charstream)：要被编码的数据序列。
 
 字符(Character)：字符流中的基本数据单元。
 
 前缀(Prefix)： 在一个字符之前的字符序列。
 
 缀-符串(String)：前缀＋字符。
 
 码字(Code word)：码字流中的基本数据单元，代表词典中的一串字符。
 
 码字流(Codestream)： 码字和字符组成的序列，是编码器的输出。
 
 词典(Dictionary)： 缀-符串表。按照词典中的索引号对每条缀-符串(String)指定一个码字(Code word)。
 
 当前前缀(Current prefix)：在编码算法中使用，指当前正在处理的前缀，用符号P表示。
 
 当前字符(Current character)：在编码算法中使用，指当前前缀之后的字符，用符号C表示。  
 
 当前码字(Current code word)： 在译码算法中使用，指当前处理的码字，用W表示当前码字，String.W表示当前码字的缀-符串。  

(1) 编码算法

LZ78的编码思想是不断地从字符流中提取新的“缀-符串(String)”，通俗地理解为新“词条”，然后用“代号”也就是码字(Code word)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Code word)去替换字符流，生成码字流，从而达到压缩数据的目的。

在编码开始时词典是空的，不包含任何缀-符串(string)。在这种情况下编码器就输出一个表示空字符串的特殊码字(例如“0”)和字符流中的第一个字符C，并把这个字符C添加到词典中作为一个由一个字符组成的缀-符串。在编码过程中，如果出现类似的情况，也照此办理。在词典中已经包含某些缀-符串之后，如果“当前前缀P +当前字符C”已经在词典中，就用字符C来扩展这个前缀，这样的扩展操作一直重复到获得一个在词典中没有的缀-符串为止。此时就输出表示当前前缀P的码字(Code word)和字符C，并把P+C添加到词典中作为前缀(Prefix)，然后开始处理字符流中的下一个前缀。

LZ78编码器的输出是“码字-字符(W,C)”对，每次输出一对到码字流中，与码字W相对应的缀-符串(String)用字符C进行扩展生成新的缀-符串，然后添加到词典中。LZ78编码的具体算法如下：

步骤1： 在开始时，词典和当前前缀P都是空的；

步骤2： 当前字符C ：=字符流中的下一个字符；

步骤3： 判断P+C是否在词典中

(1) 如果“是”：用C扩展P，让P ：= P+C ；

(2) 如果“否”：

① 输出与当前前缀P相对应的码字和当前字符C；

② 把字符串P+C 添加到词典中；

③ 令P ：=空值；

(3) 判断字符流中是否还有字符需要编码

① 如果“是”：返回到步骤2；

② 如果“否”：若当前前缀P不是空的，输出相应于当前前缀P的码字，
然后结束编码。

还有吗？我快放假了，放假就不能上了 :(
qiu ni,一次贴玩吧！ :(  :P

2) 译码算法

在译码开始时译码词典是空的，它将在译码过程中从码字流中重构。每当从码字流中读入一对码字-字符(W,C)对时，码字就参考已经在词典中的缀-符串，然后把当前码字的缀-符串string.W和字符C输出到字符流(Charstream)，而把当前缀-符串(string.W+C)添加到词典中。在译码结束之后，重构的词典与编码时生成的词典完全相同。LZ78译码的具体算法如下：

步骤1：  在开始时词典是空的；

步骤2： 当前码字W ：=码字流中的下一个码字；

步骤3： 当前字符C ：= 紧随码字之后的字符；

步骤4： 把当前码字的缀-符串(string.W)输出到字符流，然后输出字符C；

步骤5： 把string.W+C添加到词典中；

步骤6： 判断码字流中是否还有码字要译

(1) 如果“是”，就返回到步骤2；

(2) 如果“否”，则结束。

例：编码字符串如表4-13所示，编码过程如表4-14所示。现说明如下：


 “步骤”栏表示编码步骤；
 “位置”栏表示在输入数据中的当前位置；
 “词典”栏表示添加到词典中的缀-符串，缀-符串的索引等于“步骤”序号；
 “输出”栏以(当前码字W, 当前字符C)简化为(W, C)的形式输出。

表4-13 编码字符串

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

表4-14 编码过程

步骤
 位置  
 词典
 输出  
 
1
 1
 A
 (0,A)
 
2
 2
 B
 (0,B)
 
3
 3
 B C
 (2,C)
 
4
 5
 B C A
 (3,A)
 
5
 8
 B A
 (2,A)
 

与LZ77相比，LZ78的最大优点是在每个编码步骤中减少了缀-符串(String)比较的数目，而压缩率与LZ77类似。

4.4.5 LZW算法

在LZW算法中使用的术语与LZ78使用的相同，仅增加了一个术语―前缀根(Root)，它是由单个字符串组成的缀-符串(String)。在编码原理上，LZW与LZ78相比有如下差别：


 LZW只输出代表词典中的缀-符串(String)的码字(code word)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根(Root)。
 由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀(one-character prefix)，因此在词典中搜索的第1个缀-符串有两个字符。

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);