浅谈LZW算法的改进研究

【摘　要】在分析lzw算法的基础上，对lzw算法的缺陷进行了探讨。并对lzw算法进行了改进，大幅度减少了编码的长度，降低了匹配长度取值变化的影响，完全兼容lzw算法，在平均压缩率方面有较大的提高，而且对改进的算法进行了分析论证。
【关键词】数据压缩lzw算法缓冲区

lzw算法的实质是无损压缩技术[1-3]，lzw算法通过对输入流进行分析，自适应地生成一个包含输入流中不重复子串的串表，将每一子串映射为一独立的码字输出。这样，它就充分利用了相邻输入之间的相关性，可以取得超过信源一阶熵的编码效率。然而，受缓存容量、计算复杂度和计算速度等因素的限制，串表的长度受到一定限制，且一般信源所具有的局部平稳性随缓存容量加大，编码效率提高不大。即：它自身固有一定的缺陷与不足，难以满足人们的需要，对它进行改进一直成为人们的研究目标之一[4-6]。为了解决这一问题，本文对lzw算法进行了改进，命名为lzwc编码算法。它兼有lzw算法的优点，还具有自身的优越性。首先对lzw算法进行一些必要的介绍和分析。
算法
lzw算法[1]由韦尔奇（）于1984年通过对lz算法的改进。Www.lw881.com开发出的一种更优算法。它是一种基于字典的编码方法。并且它是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对上式的c满足的条件:对每一个i有且只有一对(i,li)，使li(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.2lzw算法的原理
lzw算法通过编码表来组织输人字符串，并把它们转换成一定长度的编码。lzw算法有一个重要的特性称作前缀性，即如果一个字符串在编码表上，那它的前缀串也在编码表上。例如:a、b为两个不同的字符串，ab组成一新的字符串，a为b的前缀串，如果b在编码表中，则一定在编码表中。
lzw通过编码表识别源输人字符序列，通过向编码表中增加新的字符串，从而识别更多、更长的字符序列。但由于前缀性的约束，这种识别一般每次只在原来的基础上增加一个字符，依次进行。同时，由于编码算法没有很强的分析功能，使它不知道哪些字符序列将来出现的概率较大，所以它具有一定的盲目性。例如，有一个长度为n的字符序列，lzw编码表要完全识别它，则至少需要该序列部分或全部重复出现n次。但是，当一个较长的字符串重复出现两次，我们就能够容易识别它，而且这样的字符串再次出现的概率是非常大的。基于这样一种认识，本文在lzw算法的基础上，构造了一种新的编码算法，我们把新算法称为lzwc编码算法，一般情况下它对数据的压缩率比lzw算法有大幅度提高。新算法在最差的情况下可退化成标准的lzw算法。下面对lzwc算法的原理进行详细的介绍。
2lzwc算法
lzwc算法的基本原理是针对源输人数据中不同特点的数据序列，采用不同的编码器分别编码。数据序列的分类则是根据它的特点，通过对原始数据序列的分析来完成。
lzwc算法共有两个编码器，它们是：
(1）重复编码器（repeatcorder），简称rc。
(2）lzw编码器。
rc对输入流中重复的数据进行编码，剩下的数据由则由lzw编码器进行编码。rc编码器和lzw编码器的编码通过lzw编码器的编码表统一起来。
2.1lzwc算法的编码及原理
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.2lzwc算法的解码原理
lzwc压缩算法的解码过程是编码过程的逆过程，以下是lzwc算法的解码过程：
(1）读一个编码（按lzw方式确定的码长）；
(2）如果是结束码，则结束解码过程；
(3）如果是rc标志的编码，则按照rc编码规则解码，输出原始数据；
(4）否则，按lzw方式解码；
(5）译码过程结束。
2.3lzwc编码的算例
下面，我们用一个例子来说明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)}。

3lzwc算法与lzw算法性能的比较
压缩算法性能的比较一般有两个重要因素，就是平均数据压缩率和压缩时间。我们从下面例子入手，来讨论他们的压缩性能：
例1：设输入流为：ababcbabccc
先建立初始化字典，将信源符号a，b，c预置为字典的前3项，编码位点分别为1，2，3。编码就从这个初始字典开始。
3.1lzw编码过程
(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.2lzwc编码过程
(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].合肥: 本文链接：http://www.qk112.com/lwfw/jsjlw/jisuanjiyingyong/245545.html