关于LZW算法的改进研究
【摘 要】 在分析LZW算法的基础上，对LZW算法的缺陷进行了探讨。并对LZW算法进行了改进，大幅度减少了编码的长度，降低了匹配长度取值变化的影响，完全兼容LZW算法，在平均压缩率方面有较大的提高，而且对改进的算法进行了分析论证。
【关键词】 数据压缩 LZW算法 缓冲区
LZW算法的实质是无损压缩技术[1-3]，LZW算法通过对输入流进行分析，自适应地生成一个包含输入流中不重复子串的串表，将每一子串映射为一独立的码字输出。这样，它就充分利用了相邻输入之间的相关性，可以取得超过信源一阶熵的编码效率。然而，受缓存容量、计算复杂度和计算速度等因素的限制，串表的长度受到一定限制，且一般信源所具有的局部平稳性随缓存容量加大，编码效率提高不大。即：它自身固有一定的缺陷与不足，难以满足人们的需要，对它进行改进一直成为人们的研究目标之一[4-6]。为了解决这一问题，本文对LZW算法进行了改进，命名为LZWC编码算法。它兼有LZW算法的优点，还具有自身的优越性。首先对LZW算法进行一些必要的介绍和分析。
1. LZW算法
LZW算法[1]由韦尔奇（T.A.Welch）于1984年通过对LZ算法的改进。开发出的一种更优算法。它是一种基于字典的编码方法。并且它是LZ系列码中应用最广，变形最多的一种算法。LZW压缩有3个重要的对象：数据流、编码流和编译表。在编码时，数据流是输入对象，编码流就是输出对象；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都需要借助的对象。
1.1LZW算法的编码原理
LZW算法的编码原理为：对消息序列xn=x1x2x3…xn从左到右进行阅读，并以此进行LZW编码：
(1)对x1显然是第一次出现，它的前面也没有字符，那么他的编号是1，它的码元为(1,0, x1)。
(2)对于x2它可能有两种情况发生，即x1=x2或x1≠x2。对此，有
①如果x1=x2，那么对于x2不作编码，而对x3的编码位点取2，连接位点则为1，这表示对x3作第二次编码，它与第一次编码的x1相连接。
②如果x1≠x2，那么x2的编码位点取为2，连接位点则为0，这表示对x2作第二次编码，它的前面没有出现过相同的字符。
(3)依照上述步骤递推，如果对向量xn=x1x2x3…xn，n﹤m，我们已经得到它的编码：C={(i,li, xji),i=1,2, …, k }.
对上式的C满足的条件:对每一个i有且只有一对(i,li)，使li﹤i﹤ji成立。那么C构成一LZW树。由树的构造可知，对每个点i，它的枝li是唯一的。因此，树C的全部枝为li，i=0，1，…,k 确定，而且每个li与xn中的子向量xαi对应。
(4)如向量xn中的编码C及相应的树确定，那么我们就可读xn+1,xn+2,…, xn+k,并对它们继续进行编码，如果有一个i≦k使xαi=(xn+1,xn+2,…, xn+k)成立，而且对任何i≦k都有：xαi≠( xn+1,xn+2,…, xn+k，xn+k+1)成立。那么：
①不对字符xn+1,xn+2,…, xn+k进行编码。
②对xn+k+1作它的编码为（K+1,i, xn+k+1）。
以此类推，就可以完成对xn的编码C。
2.2 LZW算法的原理
LZW算法通过编码表来组织输人字符串，并把它们转换成一定长度的编码。LZW算法有一个重要的特性称作前缀性，即如果一个字符串在编码表上，那它的前缀串也在编码表上。例如:A、B为两个不同的字符串，AB组成一新的字符串，A为B的前缀串，如果B在编码表中，则一定在编码表中。
LZW通过编码表识别源输人字符序列，通过向编码表中增加新的字符串，从而识别更多、更长的字符序列。但由于前缀性的约束，这种识别一般每次只在原来的基础上增加一个字符，依次进行。同时，由于编码算法没有很强的分析功能，使它不知道哪些字符序列将来出现的概率较大，所以它具有一定的盲目性。例如，有一个长度为n的字符序列，LZW编码表要完全识别它，则至少需要该序列部分或全部重复出现n次。但是，当一个较长的字符串重复出现两次，我们就能够容易识别它，而且这样的字符串再次出现的概率是非常大的。基于这样一种认识，本文在LZW算法的基础上，构造了一种新的编码算法，我们把新算法称为LZWC编码算法，一般情况下它对数据的压缩率比LZW算法有大幅度提高。新算法在最差的情况下可退化成标准的LZW算法。下面对LZWC算法的原理进行详细的介绍。
2 LZWC算法
LZWC算法的基本原理是针对源输人数据中不同特点的数据序列，采用不同的编码器分别编码。数据序列的分类则是根据它的特点，通过对原始数据序列的分析来完成。
LZWC算法共有两个编码器，它们是：
(1） 重复编码器（RepeatCorder），简称RC。
(2） LZW编码器。
RC对输入流中重复的数据进行编码，剩下的数据由则由LZW编码器进行编码。RC编码器和LZW编码器的编码通过LZW编码器的编码表统一起来。
2.1 LZWC算法的编码及原理
LZWC的算法过程如下：
对消息序列xn=x1x2x3…xn从左到右进行阅读，并以此进行LZWC编码：
(1） 输入流中的数据x1，x2，…，xn依次经过前缓冲区。
(4） 假如还有数据进入缓冲区，则转1），继续此过程。
(5） 否则，结束编码过程。
LZWC算法和LZW算法一样采用编码表来组织输入数据，显然LZW的编码表中包含RC和LZW两个编码器编码的编码表。我们分别称其为编码表中的RC项和LZW项。这两项虽然对两个编码器来说是通用的，但实现时为了提高编码表的搜索速度，可以把两者分开处理。
RC的编码识别很简单，只在缓冲区中进行，对于较长的重复字符，这种编码方式简便易行，效率较高。
LZW编码器编码不连续的字符，当然是有效的，从而获得较高的压缩率。从LZWC编码过程可以看出，如果RC编码器在输入流中找不到满足条件的字符，则LZW编码器将独自编码输入数据。这时LZWC算法退化为LZW算法。
2.2 LZWC算法的解码原理
LZWC压缩算法的解码过程是编码过程的逆过程，以下是LZWC算法的解码过程：
(1）读一个编码（按LZW方式确定的码长）；
(2）如果是结束码，则结束解码过程；
(3）如果是RC标志的编码，则按照RC编码规则解码，输出原始数据；
(4）否则，按LZW方式解码；
(5）译码过程结束。
2.3 LZWC编码的算例
下面，我们用一个例子来说明LZWC编码算的过程。例如：假设信源发出的序列为：00110000111011100011001解：依题意，有：信源序列的数据依次经过前缓冲区，则
(1）RC编码器对进入前缓冲区的数据进行检测，x1=x2，x2≠x3，即：0重复出现2次，符合RC编码的条件，则00的LZWC编码为（1，2，0）。
(2）RC编码器继续对进入前缓冲区的数据进行检测，x3=x4，x4≠x5，1重复出现2次，符合RC编码的条件，则11的LZWC编码为（2，2，1）。
(3）RC编码器继续对进入前缓冲区的数据进行检测，x5=x6，x6=x7，x7=x8，x8≠x9，0重复出现4次，符合RC编码的条件，则0000的LZWC编码为（3，4，0）。
(4）RC编码器继续对进入前缓冲区的数据进行检测，x9=x10，x10=x11，x11≠x12，1重复出现3次，符合RC编码的条件，则111的LZWC编码为（4，3，1）。
(5）RC编码器继续对进入前缓冲区的数据进行检测，x12≠x13，0仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则0的LZWC编码为（5，1，0）。
(6）RC编码器继续对进入前缓冲区的数据进行检测，x13=x14，x14=x15，x15≠x16，1重复出现3次，符合RC编码的条件，则111的LZWC编码为（6，3，1）。
(7）RC编码器继续对进入前缓冲区的数据进行检测，x16=x17，x17=x18，x18≠x19，0重复出现3次，符合RC编码的条件，则000的LZWC编码为（7，3，0）。
(8）RC编码器继续对进入前缓冲区的数据进行检测，x19=x20，x20≠x21，次，符合RC编码的条件，则11的LZWC编码为（8，2，1），1重复出现2次，符合RC编码的条件，则11的LZWC编码为（8，2，1）。
(9）RC编码器继续对进入前缓冲区的数据进行检测，x21=x22，x22≠x23，次，符合RC编码的条件，则00的LZWC编码为（9，2，0）。
(10）RC编码器继续对进入前缓冲区的数据进行检测，x23是最后一个数据，1仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则1的LZWC编码为（10，1，1）。
(11）前缓冲区没有数据通过了，编码到此结束。
所以，信源序列的LZWC编码为：C′={(1，2，0)，(2，2，1)，(3，4，0)，(4，3，1)，(5，1，0)，(6，3，1)，(7，3，0)，(8，2，1)，(9，2，0)，(10，1，1)}。
3 LZWC算法与LZW算法性能的比较
压缩算法性能的比较一般有两个重要因素，就是平均数据压缩率和压缩时间。我们从下面例子入手，来讨论他们的压缩性能：
例1：设输入流为：ababcbabccc
先建立初始化字典，将信源符号a，b，c预置为字典的前3项，编码位点分别为1，2，3。编码就从这个初始字典开始。
3.1 LZW编码过程
(1） 由于"a"已经在字典中了，而"ab"不在，输出"a"的编码，同时把"ab"添加到字典中，所以字典的第4个条目为"ab"令其编码位点为4，当前位置前移一位，变为1，当前字符变为"b"。它的LZW编码为（4，1，1）。
(2） 从输入流的第1个位置开始，"b"已在字典中了，
而"ba"不在。同理，输出"b"的编码，同时把"ba"添加到字典中，编码位点为5，当前位置变为2，当前字符为"a"它的LZW编码为（5，1，2）。
(3） 从输入流的第2个位置开始，"ab"已在字典中了，而"abc"不在。同理，输出"ab"的编码，同时把"abc"添加到字典中，编码位点为6，当前位置变为3，当前字符为"c"。它的LZW编码为（6，1，4）。
(4） 从输入流的第3个位置开始，"c"已在字典中了，而"cb"不在。同理，输出"c"的编码，同时把"cb"添加到字典中，编码位点为7，当前位置变为4，当前字符为"c"。它的LZW编码为（7，1，3）。
(5） 从输入流的第4个位置开始，"ba"已在字典中了，而"bab"不在。同理，输出"ba"的编码，同时把"bab"添加到字典中，编码位点为8，当前位置变为5，当前字符为"b"。它的LZW编码为（8，1，5）。
(6） 从输入流的第5个位置开始，"b"已在字典中了，而"bc"不在。同理，输出"b"的编码，同时把"bc"添加到字典中，编码位点为9，当前位置变为6，当前字符为"c"。它的LZW编码为（9，1，2）。
(7） 从输入流的第6个位置开始，"c"已在字典中了，而"cc"不在。同理，输出"c"的编码，同时把"cc"添加到字典中，编码位点为10，当前位置变为7，当前字符为"c"。它的LZW编码为（10，1，3）。
(8） 从输入流的第10个位置开始，"cc"已在字典中了，并且没有别的字符需要编码了。即，编码过程到此结束。
所以，它的LZW编码为：
C’={(1，0，1)，(2，0，2)，(3，0，3)，(4，1，1)，(5，1，2)，(6，1，4)，(7，1，3)，(8，1，5)，(9，1，2)，(10，1，3)}。
3.2 LZWC编码过程
(1）由于x1≠x2，a仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则a的LZWC编码为（1，1，1）。
(2）由于x2≠x3，b仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则b的LZWC编码为（2，1，2）。
(3）由于x3≠x4，a仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则a的LZWC编码为（3，1，1）。
(4）由于x4≠x5，b仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则b的LZWC编码为（4，1，2）。
(5）由于x5≠x6，c仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则c的LZWC编码为（5，1，3）。
(6）由于x6≠x7，b仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则b的LZWC编码为（6，1，2）。
(7）由于x7≠x8，a仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则a的LZWC编码为（7，1，1）。
(8）由于x8≠x9，b仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则b的LZWC编码为（8，1，2）。
(9）由于x9=x10，x10=x11，c重复出现3次，符合RC编码的条件，则ccc的LZWC编码为（9，3，3）。
(10）由于x11是最后一个数据，前缓冲区没有数据通过了，编码过程到此结束。
C’={(1，1，1)，(2，1，2)，(3，1，1)，(4，1，2)，(5，1，3)，(6，1，2)，(7，1，1)，(8，1，2)，(9，3，3)}。
所以，LZWC算法的平均字符压缩率较高，压缩时间较短，较LZW算法有一定的优势。
4 结 论
本文在LZW算法的基础上，提出了一种改进的算法。命名为LZWC算法，LZWCS算法在压缩方面比LZW算法有了较大的提高，它适合对文本、字符、数据等类型的文件进行压缩。对于重复字符很少的输入流，新算法和LZW算法的压缩效果差别不大。但是，对于重复字符较多的输入流，新算法压缩效果的优势十分明显。但由于新算法兼容LZW算法，所以，它在应用中比单纯的LZW算法具有更好的性能。
参考文献
[1] 姜 丹.信息论与编码[M].合肥:中国科学技术大学出版社,2001.
[2] 张凤林,刘思峰. LZW*:一个改进的LZW数据压缩算法[J]. 小型微型计算机系统.2006,27（10）1897-1899
[3] 吴宇新,余松煌.对 LZW 算法的改进及其在图像无损压缩中的应用[J].上海交通大学学报, 1998,3 (29): 110-113
[4] 卓 越, 杨长生, 宋广华.一种基于自适应字典的通用无损压缩算法[J]. 计算机工程, 2001, 27(2): 149-151
[5] David Salomon. Data Compression: The Complete Reference [M].Springer-Verlag New York Inc.,200
