LZW算法

      之前看到坛子里有人在问LZW算法的事情，这个算法以前也见过，知道是一种压缩算法，但是没有深究过，称着这两天时间比较多，就查阅了相关资料，并且自己初步实现了一个。

      LZW算法全名叫做Lempel-Ziv-Welch Encoding，是一种数据压缩算法，它是有专利的，不过现今大部分专利都己经过期。它可以对文本进行简单的压缩，压缩比对于一般场合还是可以适用的，另外使用的比较多的就是GIF图像了。

      LZW算法中有几个比较重要的概念：字符，字符串，编码表。它把数据流看成一个字符序列，并将字符序列组织成一系列的字符串，并给每个字符串一个编码，最后存储的就是字符串的编码，这样就节省了空间。如将ababba表示为编码1532，而1523用12bit就可以表示出来，比原来5*8bit就节省了不少空间。LZW的编码表是动态创建的，并且通过编码后的数据流可以恢复出与编码时同样的编码表，这样在数据存储与传输的时候就不需要保存原始的编码表，这也是与一些在编码之前就有固定的编码表的算法有着巨大的区别。

1.编码过程

      LZW是一个固长编码的算法的，即对于每一个字符或字符串的编码都是等长的。为了说明的方便，我决定用16bit作为编码，前255作为字符编码，256，257另作它用，这将在3中进行说明。所以字符串的编码将从258开始。

编码的整个过程如下：
1. 初始化编码表，编码起始号，并置当前字符串为空；
2. 读入一个字符，如果为EOF，输出当前字符串，并结束，否则进入3；
3. 将新读入的字符与当前字符串组成新的字符串，如果新的字符串在编码表中出现，则继续进行2，否则进入4；
4. 将新的字符串加入到编码表中，分配编号，设当前字符串的长度为N，输入新字符串的N-1长度前缀的编码，并将当前字符串置为当前字符串的一个长度为1的后缀，再执行2。

 

2.解码过程

      对于解码，我们唯一需要知道的就是编码的长度了，每次从编码流中读取相应bit的长度，就形成一个编码，再通过该编码从编码表中找出相对应的串输出即可。我们知道，由于没有存储编码时对应的编码表，我们在译码时需要同时构造编码表。

译码过程如下：
1. 初始化编码表，并置前一个编码为空；
2. 取一个编码，如果编码为结束，则结束。否则进行3；
3. 输出编码所代表的字符串，如果前一个编码不为空，将前一个编码的字符串与当前字符串的第一个字符作为新的串加入编码表中，置前一个编码为当前编码，并执行2。

3.其它问题

      在编码之前，我们就确定了每个编码的长度，如采用16bit，所以编码表的最大长度就是2^16-1，即65537的长度，那以如果发现编码表超过了这个长度怎么办？我们可以在其中加一个特殊的标志，表示之前清空之前构造的编码表，从现在起我们重新构造一个新的编码表。由于编码表在解码过程中是可以重新构造出来的，所以这对于我们解码并没有任何影响。如我们将256作为CLEAR标志，表示重新构造编码表即可解决这个问题。

      另外我们将257作为结束标志END，当然其实在一些流中是不需要这个标志也能判断结束的，但是为了通用，还是使用一个标志表示结束。

      在解码过程中，我们总是假定读取的编码一定出现在的编码表中，一般情况下是没有问题的。但考虑下面一种情况：AAA

现在看它的编码过程：
1. 读A发现己经存在
2. 读A，现在AA将AA加入编码表，编码为258，输出一个A，当前串为A
3.读A，发现AA在编码表中，继续
4.结束，将AA输出，即258
我们得到的编码是65（A） 258（AA）

译码过程如下：
1.读取65，输出A，前一个串为A
2.读取258，发现编码表中没有这个编码
如果编码表中发现没有这个编码，这个编码为前一个串与前一个串的第一个字符组成的串，这个例子中即为A+A=AA，好了，与结果相同，那么怎么证明这个结果是正确的呢？有兴趣的可以尝试证明一下。

下面是我的参考证明:
p { margin-bottom: 0.21cm; }

      考虑到编码T之前并未出现,设它的前一个字符串为S,S肯定不为空,因为S为空只出现在第一个串的时候,而第一个串根据我们的编码算法肯定为单个字符. 由于T是一个未在编码表中的串,而编码时出现的值一定是之前出现过的值,所以这个值只可能出现在S+T[0]的位置. 因为出现在其它位置编码则会在编码表中出现.现在只需证明T[0] = S[0]即可.设S的长度为L,则T的长度为L+1,且S+T[0] = T,故S[0] = T[0],得证.

      最后一个有趣的现象就是如果一个串S出现在编码表中，那么它的所有前缀都出现在编码表中。这也是为什么我们每次需要使用前一个编码字符串与当前编码的第一个字符来组成新的编码的原因。在我们编码时，每次发现一个新的编码才输出一个编码，这个编码是新编码的前缀，所以新发现的编码并不是立即输出，而是等到下次再发现这个编码时才输出。

4. 总结

      LZW算法并不完美，但它却是很简洁的一种算法。同时选取一个好的编码长度也是相当重要的，不同长度的编码对于各种不同的文件的压缩率也是不相同，推荐值为12bit。LZW对于学习压缩算法的是一种非常好的入门材料。以后有时间将实现LZW算法，并对于不同bit的编码对于不同文件的压缩比作一些实验，并与一些主流的压缩软件比较。