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。
做梦的燕子
