关于LZW算法的改进研究

1、关于LZW算法的改进研究         11-01-09 15:32:00     作者：徐巨峰    编辑：studa090420【摘要】 在分析LZW算法的基础上，对LZW算法的缺陷进行了探讨。并对LZW算法进行了改进，大幅度减少了编码的长度，降低了匹配长度取值变化的影响，完全兼容LZW算法，在平均压缩率方面有较大的提高，而且对改进的算法进行了分析论证。 【关键词】  数据压缩  

2、 LZW算法   缓冲区         LZW算法的实质是无损压缩技术1-3，LZW算法通过对输入流进行分析，自适应地生成一个包含输入流中不重复子串的串表，将每一子串映射为一独立的码字输出。这样，它就充分利用了相邻输入之间的相关性，可以取得超过信源一阶熵的编码效率。然而，受缓存容量、计算复杂度和计算速度等因素的限制，串表的长度受到一定限制，且一般信源所具有的局部平稳性随缓存容量加大，编码效率提高不大。即：它自身固有一定的缺陷与不足，难以满足人们的需要，对它进行改进一直成为人

3、们的研究目标之一4-6。为了解决这一问题，本文对LZW算法进行了改进，命名为LZWC编码算法。它兼有LZW算法的优点，还具有自身的优越性。首先对LZW算法进行一些必要的介绍和分析。         1. LZW算法         LZW算法1由韦尔奇（T.A.Welch）于1984年通过对LZ算法的改进。开发出的一种更优算法。它是一种基于字典的编码方法。并且它是LZ系列码中应用最广，变形最多的一种算法。LZW压缩有3个重要的

4、对象：数据流、编码流和编译表。在编码时，数据流是输入对象，编码流就是输出对象；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都需要借助的对象。          1.1LZW算法的编码原理         LZW算法的编码原理为：对消息序列xn=x1x2x3xn从左到右进行阅读，并以此进行LZW编码：         &#

5、160;(1)对x1显然是第一次出现，它的前面也没有字符，那么他的编号是1，它的码元为(1,0, x1)。          (2)对于x2它可能有两种情况发生，即x1=x2或x1x2。对此，有         如果x1=x2，那么对于x2不作编码，而对x3的编码位点取2，连接位点则为1，这表示对x3作第二次编码，它与第一次编码的x1相连接。       &

6、#160;  如果x1x2，那么x2的编码位点取为2，连接位点则为0，这表示对x2作第二次编码，它的前面没有出现过相同的字符。          (3)依照上述步骤递推，如果对向量xn=x1x2x3xn，n<m，我们已经得到它的编码：C=(i,li, xji),i=1,2, , k .         对上式的C满足的条件:对每一个i有且只有一对(i,li)，使

7、li<i<ji成立。那么C构成一LZW树。由树的构造可知，对每个点i，它的枝li是唯一的。因此，树C的全部枝为li，i=0，1，,k 确定，而且每个li与xn中的子向量xi对应。          (4)如向量xn中的编码C及相应的树确定，那么我们就可读xn+1,xn+2, xn+k,并对它们继续进行编码，如果有一个ik使xi=(xn+1,xn+2, xn+k)成立，而且对任何ik都有：xi( xn+1,xn+2, xn+k，xn+k+1)成立

8、。那么：         不对字符xn+1,xn+2, xn+k进行编码。         对xn+k+1作它的编码为（K+1,i, xn+k+1）。         以此类推，就可以完成对xn的编码C。         2.2 LZW算法的原理 &

9、#160;       LZW算法通过编码表来组织输人字符串，并把它们转换成一定长度的编码。LZW算法有一个重要的特性称作前缀性，即如果一个字符串在编码表上，那它的前缀串也在编码表上。例如:A、B为两个不同的字符串，AB组成一新的字符串，A为B的前缀串，如果B在编码表中，则一定在编码表中。         LZW通过编码表识别源输人字符序列，通过向编码表中增加新的字符串，从而识别更多、更长的字符序列。但由于前缀性的约束，这种识别一般每次只在原来的

10、基础上增加一个字符，依次进行。同时，由于编码算法没有很强的分析功能，使它不知道哪些字符序列将来出现的概率较大，所以它具有一定的盲目性。例如，有一个长度为n的字符序列，LZW编码表要完全识别它，则至少需要该序列部分或全部重复出现n次。但是，当一个较长的字符串重复出现两次，我们就能够容易识别它，而且这样的字符串再次出现的概率是非常大的。基于这样一种认识，本文在LZW算法的基础上，构造了一种新的编码算法，我们把新算法称为LZWC编码算法，一般情况下它对数据的压缩率比LZW算法有大幅度提高。新算法在最差的情况下可退化成标准的LZW算法。下面对LZWC算法的原理进行详细的介绍。   

11、      2  LZWC算法         LZWC算法的基本原理是针对源输人数据中不同特点的数据序列，采用不同的编码器分别编码。数据序列的分类则是根据它的特点，通过对原始数据序列的分析来完成。         LZWC算法共有两个编码器，它们是：         (1）&#

12、160;重复编码器（RepeatCorder），简称RC。         (2） LZW编码器。         RC对输入流中重复的数据进行编码，剩下的数据由则由LZW编码器进行编码。RC编码器和LZW编码器的编码通过LZW编码器的编码表统一起来。         2.1  LZWC算法的编码及原理   

13、      LZWC的算法过程如下：         对消息序列xn=x1x2x3xn从左到右进行阅读，并以此进行LZWC编码：         (1） 输入流中的数据x1，x2，xn依次经过前缓冲区。         (4） 假如还有数据进入缓冲区，则转1），继续此过程。 &#

14、160;       (5） 否则，结束编码过程。         LZWC算法和LZW算法一样采用编码表来组织输入数据，显然LZW的编码表中包含RC和LZW两个编码器编码的编码表。我们分别称其为编码表中的RC项和LZW项。这两项虽然对两个编码器来说是通用的，但实现时为了提高编码表的搜索速度，可以把两者分开处理。         RC的编码识别很简单，只在缓

15、冲区中进行，对于较长的重复字符，这种编码方式简便易行，效率较高。         LZW编码器编码不连续的字符，当然是有效的，从而获得较高的压缩率。从LZWC编码过程可以看出，如果RC编码器在输入流中找不到满足条件的字符，则LZW编码器将独自编码输入数据。这时LZWC算法退化为LZW算法。         2.2  LZWC算法的解码原理       

16、60; LZWC压缩算法的解码过程是编码过程的逆过程，以下是LZWC算法的解码过程：         (1）读一个编码（按LZW方式确定的码长）；         (2）如果是结束码，则结束解码过程；         (3）如果是RC标志的编码，则按照RC编码规则解码，输出原始数据；      &#

17、160;  (4）否则，按LZW方式解码；         (5）译码过程结束。         2.3  LZWC编码的算例         下面，我们用一个例子来说明LZWC编码算的过程。例如：假设信源发出的序列为：00110000111011100011001解：依题意，有：信源序列的数据依次经过前缓冲区，则 &

18、#160;       (1）RC编码器对进入前缓冲区的数据进行检测，x1=x2，x2x3，即：0重复出现2次，符合RC编码的条件，则00的LZWC编码为（1，2，0）。         (2）RC编码器继续对进入前缓冲区的数据进行检测，x3=x4，x4x5，1重复出现2次，符合RC编码的条件，则11的LZWC编码为（2，2，1）。         (3）RC编码器继

19、续对进入前缓冲区的数据进行检测，x5=x6，x6=x7，x7=x8，x8x9，0重复出现4次，符合RC编码的条件，则0000的LZWC编码为（3，4，0）。         (4）RC编码器继续对进入前缓冲区的数据进行检测，x9=x10，x10=x11，x11x12，1重复出现3次，符合RC编码的条件，则111的LZWC编码为（4，3，1）。         (5）RC编码器继续对进入前缓冲区的数据进行检测，x12x13，0仅出现1次，

20、不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则0的LZWC编码为（5，1，0）。         (6）RC编码器继续对进入前缓冲区的数据进行检测，x13=x14，x14=x15，x15x16，1重复出现3次，符合RC编码的条件，则111的LZWC编码为（6，3，1）。         (7）RC编码器继续对进入前缓冲区的数据进行检测，x16=x17，x17=x18，x18x1

21、9，0重复出现3次，符合RC编码的条件，则000的LZWC编码为（7，3，0）。         (8）RC编码器继续对进入前缓冲区的数据进行检测，x19=x20，x20x21，次，符合RC编码的条件，则11的LZWC编码为（8，2，1），1重复出现2次，符合RC编码的条件，则11的LZWC编码为（8，2，1）。         (9）RC编码器继续对进入前缓冲区的数据进行检测，x21=x22，x22x23，次，符合RC编码的条件，则0

22、0的LZWC编码为（9，2，0）。         (10）RC编码器继续对进入前缓冲区的数据进行检测，x23是最后一个数据，1仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则1的LZWC编码为（10，1，1）。         (11）前缓冲区没有数据通过了，编码到此结束。        

23、0;所以，信源序列的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)。      11-01-09 15:32:00     作者：徐巨峰    编辑：studa090420       3  LZWC算法与LZW算法性能的比较   &#

24、160;     压缩算法性能的比较一般有两个重要因素，就是平均数据压缩率和压缩时间。我们从下面例子入手，来讨论他们的压缩性能：         例1：设输入流为：ababcbabccc         先建立初始化字典，将信源符号a，b，c预置为字典的前3项，编码位点分别为1，2，3。编码就从这个初始字典开始。       &

25、#160; 3.1  LZW编码过程         (1） 由于"a"已经在字典中了，而"ab"不在，输出"a"的编码，同时把"ab"添加到字典中，所以字典的第4个条目为"ab"令其编码位点为4，当前位置前移一位，变为1，当前字符变为"b"。它的LZW编码为（4，1，1）。        

26、; (2） 从输入流的第1个位置开始，"b"已在字典中了， 而"ba"不在。同理，输出"b"的编码，同时把"ba"添加到字典中，编码位点为5，当前位置变为2，当前字符为"a"它的LZW编码为（5，1，2）。         (3） 从输入流的第2个位置开始，"ab"已在字典中了，而"abc"不在。同理，输出"ab"的编码，同时把

27、"abc"添加到字典中，编码位点为6，当前位置变为3，当前字符为"c"。它的LZW编码为（6，1，4）。         (4） 从输入流的第3个位置开始，"c"已在字典中了，而"cb"不在。同理，输出"c"的编码，同时把"cb"添加到字典中，编码位点为7，当前位置变为4，当前字符为"c"。它的LZW编码为（7，1，3）。    

28、0;    (5） 从输入流的第4个位置开始，"ba"已在字典中了，而"bab"不在。同理，输出"ba"的编码，同时把"bab"添加到字典中，编码位点为8，当前位置变为5，当前字符为"b"。它的LZW编码为（8，1，5）。         (6） 从输入流的第5个位置开始，"b"已在字典中了，而"bc"不在。同理，输出

29、"b"的编码，同时把"bc"添加到字典中，编码位点为9，当前位置变为6，当前字符为"c"。它的LZW编码为（9，1，2）。         (7） 从输入流的第6个位置开始，"c"已在字典中了，而"cc"不在。同理，输出"c"的编码，同时把"cc"添加到字典中，编码位点为10，当前位置变为7，当前字符为"c"。它的LZW编码为（10，1，3）。 &

30、#160;       (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)，

31、(10，1，3)。         3.2  LZWC编码过程         (1）由于x1x2，a仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则a的LZWC编码为（1，1，1）。         (2）由于x2x3，b仅出现1次，不符合RC编码的条件，所以，不能用

32、RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则b的LZWC编码为（2，1，2）。         (3）由于x3x4，a仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则a的LZWC编码为（3，1，1）。         (4）由于x4x5，b仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由

33、LZW编码器，则b的LZWC编码为（4，1，2）。         (5）由于x5x6，c仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则c的LZWC编码为（5，1，3）。         (6）由于x6x7，b仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则b的LZWC编码为（6，1，2）。 &#

34、160;       (7）由于x7x8，a仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则a的LZWC编码为（7，1，1）。         (8）由于x8x9，b仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则b的LZWC编码为（8，1，2）。      

35、   (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)。   &

36、#160;     所以，LZWC算法的平均字符压缩率较高，压缩时间较短，较LZW算法有一定的优势。         4  结 论         本文在LZW算法的基础上，提出了一种改进的算法。命名为LZWC算法，LZWCS算法在压缩方面比LZW算法有了较大的提高，它适合对文本、     11-01-09 15:32

37、:00     作者：徐巨峰    编辑：studa090420       3  LZWC算法与LZW算法性能的比较         压缩算法性能的比较一般有两个重要因素，就是平均数据压缩率和压缩时间。我们从下面例子入手，来讨论他们的压缩性能：         例1：

38、设输入流为：ababcbabccc         先建立初始化字典，将信源符号a，b，c预置为字典的前3项，编码位点分别为1，2，3。编码就从这个初始字典开始。         3.1  LZW编码过程         (1） 由于"a"已经在字典中了，而"ab"不在，输出"a

39、"的编码，同时把"ab"添加到字典中，所以字典的第4个条目为"ab"令其编码位点为4，当前位置前移一位，变为1，当前字符变为"b"。它的LZW编码为（4，1，1）。         (2） 从输入流的第1个位置开始，"b"已在字典中了， 而"ba"不在。同理，输出"b"的编码，同时把"ba"添加到字典中，编码位点为5，当前位置变为2，当前字符为"a

40、"它的LZW编码为（5，1，2）。         (3） 从输入流的第2个位置开始，"ab"已在字典中了，而"abc"不在。同理，输出"ab"的编码，同时把"abc"添加到字典中，编码位点为6，当前位置变为3，当前字符为"c"。它的LZW编码为（6，1，4）。         (4） 从输入流的第3个位置开

41、始，"c"已在字典中了，而"cb"不在。同理，输出"c"的编码，同时把"cb"添加到字典中，编码位点为7，当前位置变为4，当前字符为"c"。它的LZW编码为（7，1，3）。         (5） 从输入流的第4个位置开始，"ba"已在字典中了，而"bab"不在。同理，输出"ba"的编码，同时把"bab"添加到字典中，编码位点为

42、8，当前位置变为5，当前字符为"b"。它的LZW编码为（8，1，5）。         (6） 从输入流的第5个位置开始，"b"已在字典中了，而"bc"不在。同理，输出"b"的编码，同时把"bc"添加到字典中，编码位点为9，当前位置变为6，当前字符为"c"。它的LZW编码为（9，1，2）。         (

43、7） 从输入流的第6个位置开始，"c"已在字典中了，而"cc"不在。同理，输出"c"的编码，同时把"cc"添加到字典中，编码位点为10，当前位置变为7，当前字符为"c"。它的LZW编码为（10，1，3）。         (8） 从输入流的第10个位置开始，"cc"已在字典中了，并且没有别的字符需要编码了。即，编码过程到此结束。     

44、    所以，它的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）由于x1x2，a仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则a的LZWC编码为（1，1，1）。         (2）由于x2x3，b仅出