关于lzw算法的改进研究

1/7关于LZW算法的改进研究【摘要】在分析LZW算法的基础上，对LZW算法的缺陷进行了探讨。并对LZW算法进行了改进，大幅度减少了编码的长度，降低了匹配长度取值变化的影响，完全兼容LZW算法，在平均压缩率方面有较大的提高，而且对改进的算法进行了分析论证。【关键词】数据压缩LZW算法缓冲区LZW算法的实质是无损压缩技术13，LZW算法通过对输入流进行分析，自适应地生成一个包含输入流中不重复子串的串表，将每一子串映射为一独立的码字输出。这样，它就充分利用了相邻输入之间的相关性，可以取得超过信源一阶熵的编码效率。然而，受缓存容量、计算复杂度和计算速度等因素的限制，串表的长度受到一定限制，且一般信源所具有的局部平稳性随缓存容量加大，编码效率提高不大。即它自身固有一定的缺陷与不足，难以满足人们的需要，对它进行改进一直成为人们的研究目标之一46。为了解决这一问题，本文对LZW算法进行了改进，命名为LZWC编码算法。它兼有LZW算法的优点，还具有自身的优越性。首先对LZW算法进行一些必要的介绍和分析。1LZW算法2/7LZW算法1由韦尔奇于1984年通过对LZ算法的改进。开发出的一种更优算法。它是一种基于字典的编码方法。并且它是LZ系列码中应用最广，变形最多的一种算法。LZW压缩有3个重要的对象数据流、编码流和编译表。在编码时，数据流是输入对象，编码流就是输出对象；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都需要借助的对象。LOCALHOST算法的编码原理LZW算法的编码原理为对消息序列XNX1X2X3XN从左到右进行阅读，并以此进行LZW编码1对X1显然是第一次出现，它的前面也没有字符，那么他的编号是1，它的码元为1,0,X1。2对于X2它可能有两种情况发生，即X1X2或X1X2。对此，有如果X1X2，那么对于X2不作编码，而对X3的编码位点取2，连接位点则为1，这表示对X3作第二次编码，它与第一次编码的X1相连接。如果X1X2，那么X2的编码位点取为2，连接位点则为0，这表示对X2作第二次编码，它的前面没有出现过相同的字符。3依照上述步骤递推，如果对向量XNX1X2X3XN，N，同时把“ABC“添加到字典中，编码位点3/7为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“已在字典中了，而“BC“不在。同理，输出“B“的编码，同时把“BC“添加到字典中，编码位点为9，当前位置变为6，当前字符为“C“。它的LZW编码为。7）从输入流的第6个位置开始，“C“已在字典中了，而“CC“不在。同理，输出“C“的编码，同时把“CC“添加到字典中，编码位点为10，当前位置变为7，当前字符为“C“。它的LZW编码为。8）从输入流的第10个位置开始，“CC“已在字典中了，并且没有别的字符需要编码了。即，编码过程到此结束。所以，它的LZW编码为4/7C1，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。LZWC编码过程1）由于X1X2，A仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则A的LZWC编码为。2）由于X2X3，B仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则B的LZWC编码为。3）由于X3X4，A仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则A的LZWC编码为。4）由于X4X5，B仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则B的LZWC编码为。5）由于X5X6，C仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，5/7它符合LZW编码的条件，由LZW编码器，则C的LZWC编码为。6）由于X6X7，B仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则B的LZWC编码为。7）由于X7X8，A仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则A的LZWC编码为。8）由于X8X9，B仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则B的LZWC编码为。9）由于X9X10，X10X11，C重复出现3次，符合RC编码的条件，则CCC的LZWC编码为。10）由于X11是最后一个数据，前缓冲区没有数据通过了，编码过程到此结束。C1，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算法的平均字符压缩率较高，压缩时6/7间较短，较LZW算法有一定的优势。结论本文在LZW算法的基础上，提出了一种改进的算法。命名为LZWC算法，LZWCS算法在压缩方面比LZW算法有了较大的提高，它适合对文本、字符、数据等类型的文件进行压缩。对于重复字符很少的输入流，新算法和LZW算法的压缩效果差别不大。但是，对于重复字符较多的输入流，新算法压缩效果的优势十分明显。但由于新算法兼容LZW算法，所以，它在应用中比单纯的LZW算法具有更好的性能。参考文献1姜丹信息论与编码M合肥中国科学技术大学出版社,20012张凤林,刘思峰LZW一个改进的LZW数据压缩算法J小型微型计算机系统XX,2718971893吴宇新,余松煌对LZW算法的改进及其在图像无损压缩中的应用J上海交通大学学报,199