浅谈LZW算法的改进研究

《浅谈LZW算法的改进研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浅谈LZW算法的改进研究【摘　要】在分析LZW算法的基础上，对LZW算法的缺陷进行了探讨。并对LZW算法进行了改进，大幅度减少了编码的长度，降低了匹配长度取值变化的影响，完全兼容LZW算法，在平均压缩率方面有较大的提高，而且对改进的算法进行了分析论证。【关键词】数据压缩LZW算法缓冲区LZW算法的实质是无损压缩技术[1-3]，LZW算法通过对输入流进行分析，自适应地生成一个包含输入流中不重复子串的串表，将每一子串映射为一独立的码字输出。这样，它就充分利用了相邻输入之间的相关性，可以取得超过信源一阶熵的编码效率。然而，受缓存容

2、量、计算复杂度和计算速度等因素的限制，串表的长度受到一定限制，且一般信源所具有的局部平稳性随缓存容量加大，编码效率提高不大。即：它自身固有一定的缺陷与不足，难以满足人们的需要，对它进行改进一直成为人们的研究目标之一[4-6]。为了解决这一问题，本文对LZW算法进行了改进，命名为LZWC编码算法。它兼有LZW算法的优点，还具有自身的优越性。首先对LZW算法进行一些必要的介绍和分析。1.LZW算法LZW算法[1]由韦尔奇于1984年通过对LZ算法的改进。开发出的一种更优算法。它是一种基于字典的编码方法。并且它是LZ系列码中应用最

3、广，变形最多的一种算法。LZW压缩有3个重要的对象：数据流、编码流和编译表。在编码时，数据流是输入对象，编码流就是输出对象；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都需要借助的对象。算法的编码原理LZW算法的编码原理为：对消息序列xn=x1x2x3…xn从左到右进行阅读，并以此进行LZW编码：(1)对x1显然是第一次出现，它的前面也没有字符，那么他的编号是1，它的码元为(1,0,x1)。(2)对于x2它可能有两种情况发生，即x1=x2或x1≠x2。对此，有①如果x1=x2，那么对于x2不作编码

4、，而对x3的编码位点取2，连接位点则为1，这表示对x3作第二次编码，它与第一次编码的x1相连接。②如果x1≠x2，那么x2的编码位点取为2，连接位点则为0，这表示对x2作第二次编码，它的前面没有出现过相同的字符。(3)依照上述步骤递推，如果对向量xn=x1x2x3…xn，n3LZWC算法与LZW算法性能的比较压缩算法性能的比较一般有两个重要因素，就是平均数据压缩率和压缩时间。我们从下面例子入手，来讨论他们的压缩性能：例1：设输入流为：ababcbabccc先建立初始化字典，将信源符号a，b，c预置为字典的前3项，编码位点分别

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

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

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

8、，1)，(5，1，2)，(6，1，4)，(7，1，3)，(8，1，5)，(9，1，2)，(10，1，3)}。.2LZWC编码过程(1）由于x1≠x2，a仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则a的LZWC编码为。