加载中…LZW算法
(2011-04-02 15:26:32)
标签：
杂谈 |
分类： 算法 |
在LZW算法中使用的术语与LZ78使用的相同，仅增加了术语前缀根(Root)，它是由单个字符串组成的缀-符串(String)。在编码原理上，LZW与LZ78相比有如下差别：
|
|
LZW只输出代表词典中的缀-符串(String)的码字(code word)。这就意味在开始时词典不能是空的，它必须包含可能在字符流出现中的所有单个字符，即前缀根(Root)。 |
|
|
由于所有可能出现的单个字符都事先包含在词典中，每个编码步骤开始时都使用一字符前缀(one-character prefix)，因此在词典中搜索的第1个缀-符串有两个字符。 |
(一) 编码算法
LZW编码是围绕称为词典的转换表来完成的。这张转换表用来存放称为前缀(Prefix)的字符序列，并且为每个表项分配一个码字(Code word)，或者叫做序号，如表03-05-7所示。这张转换表实际上是把8位ASCII字符集进行扩充，增加的符号用来表示在文本或图像中出现的可变长度ASCII字符串。扩充后的代码可用9位、10位、11位、12位甚至更多的位来表示。Welch的论文中用了12位，12位可以有4096个不同的12位代码，这就是说，转换表有4096个表项，其中256个表项用来存放已定义的字符，剩下3840个表项用来存放前缀(Prefix)。
表03-05-7 词典
|
码字(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是否在词典中 |
|
|
步骤4：判断码字流中是否还有码字要译 |
LZW编码算法可用伪码表示。开始时假设编码词典包含若干个已经定义的单个码字，例如256个字符的码字，用伪码可以表示成：
-------------------------------------------------------------
Dictionary[j]← all n single-character，j＝1， 2，…，n
--------------------------------------------------------------
(二) 译码算法
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译码算法的具体执行步骤如下：
|
|
步骤1：在开始译码时词典包含所有可能的前缀根(Root)； |
|
|
步骤2：cW：=码字流中的第一个码字； |
|
|
步骤3：输出当前缀-符串string.cW到码字流； |
|
|
步骤4：先前码字pW：= 当前码字cW； |
|
|
步骤5：当前码字cW：= 码字流中的下一个码字； |
|
|
步骤6：判断先前缀-符串string.pW是否在词典中 |
|
|
步骤7：判断码字流中是否还有码字要译 |
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)
----------------------------------------------------------------
例：编码字符串如表03-05-9所示，编码过程如表03-05-10所示。现说明如下：
|
|
“步骤”栏表示编码步骤； |
|
|
“位置”栏表示在输入数据中的当前位置； |
|
|
“词典”栏表示添加到词典中的缀-符串，它的索引在括号中； |
|
|
“输出”栏表示码字输出。 |
表03-05-9 被编码的字符串
|
位置 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
字符 |
A |
B |
B |
A |
B |
A |
B |
A |
C |
表03-05-10 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) |
表03-05-11解释了译码过程。每个译码步骤译码器读一个码字，输出相应的缀-符串，并把它添加到词典中。例如，在步骤4中，先前码字(2)存储在先前码字(pW)中，当前码字(cW)是(4)，当前缀-符串string.cW是输出(“A B”)，先前缀-符串string.pW ("B")是用当前缀-符串string.cW ("A")的第一个字符，其结果("B A") 添加到词典中，它的索引号是(6) 。
表03-05-11 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算法。
喜欢
0
赠金笔