中财网白化病帅哥:LZW算法详解
来源：百度文库 编辑：中财网 时间：2024/05/04 17:04:20
LZW压缩算法的基本概念：LZW压缩有三个重要的对象：数据流(CharStream)、编码流(CodeStream)和编译表(String Table)。在编码时，数据流是输入对象（文本文件的据序列），编码流就是输出对象（经过压缩运算的编码数据）；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都须要用借助的对象。字符(Character)：最基础的数据元素，在文本文件中就是一个字节，在光栅数据中就是一个像素的颜色在指定的颜色列表中的索引值；字符串(String)：由几个连续的字符组成； 前缀(Prefix)：也是一个字符串，不过通常用在另一个字符的前面，而且它的长度可以为0；根(Root)：一个长度的字符串；编码(Code)：一个数字，按照固定长度（编码长度）从编码流中取出，编译表的映射值；图案：一个字符串，按不定长度从数据流中读出,映射到编译表条目.
LZW压缩算法的基本原理：提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大小。看起来和调色板图象的实现原理差不多，但是应该注意到的是，我们这里的编译表不是事先创建好的，而是根据原始文件数据动态创建的，解码时还要从已编码的数据中还原出原来的编译表.
根据上面所述的LZW压缩算法的基本原理，我们可以在大体上把编码和译码的主体部分做成两个单独的编码器和译码器.
编码器(Compressor)：
编码数据，第一步，初始化一个编译表，假设这个编译表的大小是12位的，也就是最多有4096个单位，另外假设我们有32个不同的字符（小写字母“a,b,……z“，标点符号“，。；：“和换行符以及回车），表示为a，b，c，d，e...，初始化编译表：第0项为a，第1项为b，第2项为c.……一直到第31项，我们把这32项就称为根。开始编译，先定义一个前缀对象Current Prefix，记为[.c.]，现在它是空的，然后定义一个当前字符串Current String，标记为[.c.]k，[.c.]就为Current Prefix，k就为当前读取字符。在来读取数据流的第一个字符，假如为p，那么Current String就等于[.c.]p（由于[.c.]空，实际上值就等于p），现在在编译表中查找有没有Current String的值，由于p就是一个根字符，我们已经初始了32个根索引，当然可以找到，把p设为Current Prefix的值，不做任何事继续读取下一个字符，假设为q，Current String就等于[.c.]q（也就是pq），看看在编译表中有没有该值，当然。没有，这时我们要做下面的事情：将Current String的值（也就是pq）添加到编译表的第32项，把Current Prefix的值（也就是p）在编译表中的索引输出到编码流，修改Current Prefix为当前读取的字符（也就是q）。继续往下读，如果在编译表中可以查找到Current String的值([.c.]k)，则把Current String的值([.c.]k)赋予Current Prefix；如果查找不到，则添加CurrentString的值([.c.]k)到编译表，把Current Prefix的值([.c.])在编译表中所对应的索引输出到编码流，同时修改Current Prefix为k ，这样一直循环下去直到数据流结束。伪代码看起来就像下面这样：
Initialize String Table;
[.c.] = Empty;
[.c.]k = First Character in CharStream;
while ([.c.]k != EOF )
{
if ( [.c.]k is in the StringTable)
{
[.c.] = [.c.]k;
}
else
{
add [.c.]k to the StringTable;
Output the Index of [.c.] in the StringTable to the CodeStream;
[.c.] = k;
}
[.c.]k = Next Character in CharStream;
}
Output the Index of [.c.] in the StringTable to the CodeStream;
解码器(Decompressor)
好了，现在来看看解码数据。数据的解码，其实就是数据编码的逆向过程，要从
已经编译的数据（编码流）中找出编译表，然后对照编译表还原图象的光栅数据。
首先，还是要初始化编译表。GIF文件的图象数据的第一个字节存储的就是LZW编
码的编码大小（一般等于图象的位数），根据编码大小，初始化编译表的根条目（从
0到2的编码大小次方），然后定义一个当前编码Current Code，记作[code]，定义一
个Old Code，记作[old]。读取第一个编码到[code]，这是一个根编码，在编译表中可
以找到，把该编码所对应的字符输出到数据流，[old]=[code]；读取下一个编码到
[code]，这就有两种情况：在编译表中有或没有该编码，我们先来看第一种情况：先
输出当前编码[code]所对应的字符串到数据流，然后把[old]所对应的字符（串）当成
前缀prefix [...]，当前编码[code]所对应的字符串的第一个字符当成k，组合起来当
前字符串Current String就为[...]k，把[...]k添加到编译表，修改[old]=[code]，
读下一个编码；我们来看看在编译表中找不到该编码的情况，回想一下编码情况：如
果数据流中有一个p[...]p[...]pq这样的字符串，p[...]在编译表中而p[...]p不在，
编译器将输出p[...]的索引而添加p[...]p到编译表，下一个字符串p[...]p就可以在
编译表中找到了，而p[...]pq不在编译表中，同样将输出p[...]p的索引值而添加
p[...]pq到编译表，这样看来，解码器总比编码器『慢一步』，当我们遇到p[...]p所
对应的索引时，我们不知到该索引对应的字符串（在解码器的编译表中还没有该索引，
事实上，这个索引将在下一步添加），这时需要用猜测法：现在假设上面的p[...]所
对应的索引值是#58，那么上面的字符串经过编译之后是#58#59，我们在解码器中读
到#59时，编译表的最大索引只有#58，#59所对应的字符串就等于#58所对应的字符串
(也就是p[...])加上这个字符串的第一个字符(也就是p)，也就是p[...]p。事实上，
这种猜测法是很准确（有点不好理解，仔细想一想吧）。
红字的地方一开始看得有点糊涂，为什么p[...]后一定是p呢，我们用反证法吧：假设p[...]后接x[...], x != p, 那么在编码时，输出p[...]编码的同时，也把p[...]x加入编译表，而后以x为前缀，之后要么输出x的编码，要么输出x[...]的编码，这些编码都应在编码p[...]前就有的，这和p[...]后的编码不在现有的编译表中矛盾，所以p[...]一定接p上面的解码过程用伪代码表
示就像下面这样：
解码器伪代码
Initialize String Table;
[code] = First Code in the CodeStream;
Output the String for [code] to the CharStream;
[old] = [code];
[code] = Next Code in the CodeStream;
while ([code] != EOF )
{
if ( [code] is in the StringTable)
{
Output the String for [code] to the CharStream; // 输出[code]所对应的字符串
[...] = translation for [old]; // [old]所对应的字符串
k = first character of translation for [code]; // [code]所对应的字符串的第一个字符
add [...]k to the StringTable;
[old] = [code];
}
else
{
[...] = translation for [old];
k = first character of [...];
Output [...]k to CharStream;
add [...]k to the StringTable;
[old] = [code];
}
[code] = Next Code in the CodeStream;
}
详细编码译码例子
ababcbababa 1
b 2
c 3
ab 4
ba 5
abc 6
cb 7
bab 8
1 2 4 3 5 8a 1
b 2
c 3
ab 4
ba 5
abc 6
cb 7ababcbababababcbabaca 1
b 2
c 3
ab 4
ba 5
abc 6
cb 7
bab 8
bac 9
1 2 4 3 5 5 3a 1
b 2
c 3
ab 4
ba 5
abc 6
cb 7
bab 8
bac 9
ababcbabac
LZW压缩算法的基本原理：提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大小。看起来和调色板图象的实现原理差不多，但是应该注意到的是，我们这里的编译表不是事先创建好的，而是根据原始文件数据动态创建的，解码时还要从已编码的数据中还原出原来的编译表.
根据上面所述的LZW压缩算法的基本原理，我们可以在大体上把编码和译码的主体部分做成两个单独的编码器和译码器.
编码器(Compressor)：
编码数据，第一步，初始化一个编译表，假设这个编译表的大小是12位的，也就是最多有4096个单位，另外假设我们有32个不同的字符（小写字母“a,b,……z“，标点符号“，。；：“和换行符以及回车），表示为a，b，c，d，e...，初始化编译表：第0项为a，第1项为b，第2项为c.……一直到第31项，我们把这32项就称为根。开始编译，先定义一个前缀对象Current Prefix，记为[.c.]，现在它是空的，然后定义一个当前字符串Current String，标记为[.c.]k，[.c.]就为Current Prefix，k就为当前读取字符。在来读取数据流的第一个字符，假如为p，那么Current String就等于[.c.]p（由于[.c.]空，实际上值就等于p），现在在编译表中查找有没有Current String的值，由于p就是一个根字符，我们已经初始了32个根索引，当然可以找到，把p设为Current Prefix的值，不做任何事继续读取下一个字符，假设为q，Current String就等于[.c.]q（也就是pq），看看在编译表中有没有该值，当然。没有，这时我们要做下面的事情：将Current String的值（也就是pq）添加到编译表的第32项，把Current Prefix的值（也就是p）在编译表中的索引输出到编码流，修改Current Prefix为当前读取的字符（也就是q）。继续往下读，如果在编译表中可以查找到Current String的值([.c.]k)，则把Current String的值([.c.]k)赋予Current Prefix；如果查找不到，则添加CurrentString的值([.c.]k)到编译表，把Current Prefix的值([.c.])在编译表中所对应的索引输出到编码流，同时修改Current Prefix为k ，这样一直循环下去直到数据流结束。伪代码看起来就像下面这样：
Initialize String Table;
[.c.] = Empty;
[.c.]k = First Character in CharStream;
while ([.c.]k != EOF )
{
if ( [.c.]k is in the StringTable)
{
[.c.] = [.c.]k;
}
else
{
add [.c.]k to the StringTable;
Output the Index of [.c.] in the StringTable to the CodeStream;
[.c.] = k;
}
[.c.]k = Next Character in CharStream;
}
Output the Index of [.c.] in the StringTable to the CodeStream;
解码器(Decompressor)
好了，现在来看看解码数据。数据的解码，其实就是数据编码的逆向过程，要从
已经编译的数据（编码流）中找出编译表，然后对照编译表还原图象的光栅数据。
首先，还是要初始化编译表。GIF文件的图象数据的第一个字节存储的就是LZW编
码的编码大小（一般等于图象的位数），根据编码大小，初始化编译表的根条目（从
0到2的编码大小次方），然后定义一个当前编码Current Code，记作[code]，定义一
个Old Code，记作[old]。读取第一个编码到[code]，这是一个根编码，在编译表中可
以找到，把该编码所对应的字符输出到数据流，[old]=[code]；读取下一个编码到
[code]，这就有两种情况：在编译表中有或没有该编码，我们先来看第一种情况：先
输出当前编码[code]所对应的字符串到数据流，然后把[old]所对应的字符（串）当成
前缀prefix [...]，当前编码[code]所对应的字符串的第一个字符当成k，组合起来当
前字符串Current String就为[...]k，把[...]k添加到编译表，修改[old]=[code]，
读下一个编码；我们来看看在编译表中找不到该编码的情况，回想一下编码情况：如
果数据流中有一个p[...]p[...]pq这样的字符串，p[...]在编译表中而p[...]p不在，
编译器将输出p[...]的索引而添加p[...]p到编译表，下一个字符串p[...]p就可以在
编译表中找到了，而p[...]pq不在编译表中，同样将输出p[...]p的索引值而添加
p[...]pq到编译表，这样看来，解码器总比编码器『慢一步』，当我们遇到p[...]p所
对应的索引时，我们不知到该索引对应的字符串（在解码器的编译表中还没有该索引，
事实上，这个索引将在下一步添加），这时需要用猜测法：现在假设上面的p[...]所
对应的索引值是#58，那么上面的字符串经过编译之后是#58#59，我们在解码器中读
到#59时，编译表的最大索引只有#58，#59所对应的字符串就等于#58所对应的字符串
(也就是p[...])加上这个字符串的第一个字符(也就是p)，也就是p[...]p。事实上，
这种猜测法是很准确（有点不好理解，仔细想一想吧）。
红字的地方一开始看得有点糊涂，为什么p[...]后一定是p呢，我们用反证法吧：假设p[...]后接x[...], x != p, 那么在编码时，输出p[...]编码的同时，也把p[...]x加入编译表，而后以x为前缀，之后要么输出x的编码，要么输出x[...]的编码，这些编码都应在编码p[...]前就有的，这和p[...]后的编码不在现有的编译表中矛盾，所以p[...]一定接p上面的解码过程用伪代码表
示就像下面这样：
解码器伪代码
Initialize String Table;
[code] = First Code in the CodeStream;
Output the String for [code] to the CharStream;
[old] = [code];
[code] = Next Code in the CodeStream;
while ([code] != EOF )
{
if ( [code] is in the StringTable)
{
Output the String for [code] to the CharStream; // 输出[code]所对应的字符串
[...] = translation for [old]; // [old]所对应的字符串
k = first character of translation for [code]; // [code]所对应的字符串的第一个字符
add [...]k to the StringTable;
[old] = [code];
}
else
{
[...] = translation for [old];
k = first character of [...];
Output [...]k to CharStream;
add [...]k to the StringTable;
[old] = [code];
}
[code] = Next Code in the CodeStream;
}
详细编码译码例子
ababcbababa 1
b 2
c 3
ab 4
ba 5
abc 6
cb 7
bab 8
1 2 4 3 5 8a 1
b 2
c 3
ab 4
ba 5
abc 6
cb 7ababcbababababcbabaca 1
b 2
c 3
ab 4
ba 5
abc 6
cb 7
bab 8
bac 9
1 2 4 3 5 5 3a 1
b 2
c 3
ab 4
ba 5
abc 6
cb 7
bab 8
bac 9
ababcbabac