长篇连载 无损数据压缩 <转贴>

这篇文章很好，请大家在全文未连载完之前不要回贴。以免影响阅读的完整性。

谢谢！！！

[编辑 -  1/22/03 by  bradley]

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

应你的要求，已将后面的及全文全部放了上来，希望能对你有用。 [/quote]
解渴！！！！！！！ :P
3x

文章中的图没有！如果是本书，可否将整书都放上来！ :P

我这儿也没图，不好意思。

文章中的图没有！如果是本书，可否将整书都放上来！ :P

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

应你的要求，已将后面的及全文全部放了上来，希望能对你有用。

这里是全文，有兴趣的可以直接下载。

LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因为它不需要执行那么多的缀-符串比较操作。对LZW算法进一步的改进是增加可变的码字长度，以及在词典中删除老的缀-符串。在GIF图象格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法。

LZW算法取得了专利，专利权的所有者是美国的一个大型计算机公司―Unisys(优利系统公司)，除了商业软件生产公司之外，可以免费使用LZW算
（全文完）

表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
 

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

表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-16 被编码的字符串

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

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


 “步骤”栏表示编码步骤；
 “位置”栏表示在输入数据中的当前位置；
 “词典”栏表示添加到词典中的缀-符串，它的索引在括号中；
 “输出”栏表示码字输出。

LZW译码算法可用伪码表示如下:

----------------------------------------------------------------

Dictionary[j] ← all n single-character， j＝1, 2， …，n

j ← n+1

cW ← first code from Codestream

Charstream ← Dictionary[cW]

pW ← cW

While((cW ← next Code word)!=NULL)

Begin

If cW is in Dictionary

Charstream ← Dictionary[cW]

Prefix ← Dictionary[pW]

cW ← first Character of Dictionary[cW]

Dictionary[j] ← Prefix.cW

j ← n+1

pW ← cW

else

Prefix ← Dictionary[pW]

cW ← first Character of Prefix

Charstream ← Prefix.cW

Dictionary[j] ← Prefix.C

pW ← cW

j ← n+1

end
----------------------------------------------------------------

 步骤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) 如果“否”, 结束。  

LZW译码算法的具体执行步骤如下：


 步骤1： 在开始译码时词典包含所有可能的前缀根(Root)；
 
 步骤2： cW ：=码字流中的第一个码字；
 
 步骤3： 输出当前缀-符串string.cW到码字流；
 
 步骤4： 先前码字pW：= 当前码字cW；
 
 步骤5： 当前码字cW ：= 码字流中的下一个码字；
 

(2) 译码算法

LZW译码算法中还用到另外两个术语：①当前码字(Current code word)：指当前正在处理的码字，用cW表示，用string.cW表示当前缀-符串；②先前码字(Previous code word)：指先于当前码字的码字，用pW表示，用string.pW表示先前缀-符串。

LZW译码算法开始时，译码词典与编码词典相同，它包含所有可能的前缀根(roots)。LZW算法在译码过程中会记住先前码字(pW)，从码字流中读当前码字(cW)之后输出当前缀-符串string.cW，然后把用string.cW的第一个字符扩展的先前缀-符串string.pW添加到词典中。

LZW编码算法可用伪码表示。开始时假设编码词典包含若干个已经定义的单个码字，例如256个字符的码字，用伪码可以表示成：

--------------------------------------------------------------------

Dictionary[j] ← all n single-character， j＝1, 2， …，n

j ← n+1

Prefix ← read first Character in Charstream

while((C ← next Character)!=NULL)

Begin

If Prefix.C is in Dictionary

Prefix ← Prefix.C

else

Codestream ← cW for Prefix

Dictionary[j] ← Prefix.C

j ← n+1

Prefix ← C

end

Codestream ← cW for Prefix

--------------------------------------------------------------------

 步骤4： 判断码字流中是否还有码字要译
(1) 如果“是”，就返回到步骤2；
(2) 如果“否”
① 把代表当前前缀P的码字输出到码字流;
② 结束。  

LZW编码算法的具体执行步骤如下：


 步骤1： 开始时的词典包含所有可能的根(Root)，而当前前缀P是空的；
 
 步骤2： 当前字符(C) ：=字符流中的下一个字符；
 
 步骤3： 判断缀-符串P+C是否在词典中
(1) 如果“是”：P ：= P+C // (用C扩展P) ；
(2) 如果“否”
① 把代表当前前缀P的码字输出到码字流;
② 把缀-符串P+C添加到词典;
③ 令P ：= C //(现在的P仅包含一个字符C);
 

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，并给一个代码。