浅谈LZW算法的改进研究

1、浅谈LZW算法的改进研究【摘要】在分析lz算法的根底上，对lz算法的缺陷进展了讨论。并对lz算法进展了改进，大幅度减少了编码的长度，降低了匹配长度取值变化的影响，完全兼容lz算法，在平均压缩率方面有较大的进步，而且对改进的算法进展了分析论证。【关键词】数据压缩lz算法缓冲区lz算法的本质是无损压缩技术1-3，lz算法通过对输入流进展分析，自适应地生成一个包含输入流中不重复子串的串表，将每一子串映射为一独立的码字输出。这样，它就充分利用了相邻输入之间的相关性，可以获得超过信源一阶熵的编码效率。然而，受缓存容量、计算复杂度和计算速度等因素的限制，串表的长度受到一定限制，且一般信源所具有的局部平稳性

2、随缓存容量加大，编码效率进步不大。即：它自身固有一定的缺陷与缺乏，难以满足人们的需要，对它进展改进一直成为人们的研究目的之一4-6。为理解决这一问题，本文对lz算法进展了改进，命名为lz编码算法。它兼有lz算法的优点，还具有自身的优越性。首先对lz算法进展一些必要的介绍和分析。1.lz算法1.1lz算法的编码原理lz算法的编码原理为：对消息序列xn=x1x2x3xn从左到右进展阅读，并以此进展lz编码：(1)对x1显然是第一次出现，它的前面也没有字符，那么他的编号是1，它的码元为(1,0,x1)。(2)对于x2它可能有两种情况发生，即x1=x2或x1x2。对此，有假设x1=x2，那么对于x2不

3、作编码，而对x3的编码位点取2，连接位点那么为1，这表示对x3作第二次编码，它与第一次编码的x1相连接。假设x1x2，那么x2的编码位点取为2，连接位点那么为0，这表示对x2作第二次编码，它的前面没有出现过一样的字符。(3)按照上述步骤递推，假设对向量xn=x1x2x3xn，n，我们已经得到它的编码：=(i,li,xji),i=1,2,k.对上式的满足的条件:对每一个i有且只有一对(i,li)，使liiji成立。那么构成一lz树。由树的构造可知，对每个点i，它的枝li是唯一的。因此，树的全部枝为li，i=0，1，,k确定，而且每个li与xn中的子向量xi对应。(4)如向量xn中的编码及相应的树

4、确定，那么我们就可读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)成立。那么：不对字符xn+1,xn+2,xn+k进展编码。对xn+k+1作它的编码为k+1,i,xn+k+1。以此类推，就可以完成对xn的编码。2.2lz算法的原理lz算法通过编码表来组织输人字符串，并把它们转换成一定长度的编码。lz算法有一个重要的特性称作前缀性，即假设一个字符串在编码表上，那它的前缀串也在编码表上。例如:a、b为两个不同的字符串，ab组成一新的字符串，a为b的前缀串，假设b在

5、编码表中，那么一定在编码表中。lz通过编码表识别源输人字符序列，通过向编码表中增加新的字符串，从而识别更多、更长的字符序列。但由于前缀性的约束，这种识别一般每次只在原来的根底上增加一个字符，依次进展。同时，由于编码算法没有很强的分析功能，使它不知道哪些字符序列将来出现的概率较大，所以它具有一定的盲目性。例如，有一个长度为n的字符序列，lz编码表要完全识别它，那么至少需要该序列局部或全部重复出现n次。但是，当一个较长的字符串重复出现两次，我们就可以容易识别它，而且这样的字符串再次出现的概率是非常大的。基于这样一种认识，本文在lz算法的根底上，构造了一种新的编码算法，我们把新算法称为lz编码算法，

6、一般情况下它对数据的压缩率比lz算法有大幅度进步。新算法在最差的情况下可退化成标准的lz算法。下面对lz算法的原理进展详细的介绍。2lz算法lz算法的根本原理是针对源输人数据中不同特点的数据序列，采用不同的编码器分别编码。数据序列的分类那么是根据它的特点，通过对原始数据序列的分析来完成。lz算法共有两个编码器，它们是：(1重复编码器repeatrder，简称r。(2lz编码器。r对输入流中重复的数据进展编码，剩下的数据由那么由lz编码器进展编码。r编码器和lz编码器的编码通过lz编码器的编码表统一起来。2.1lz算法的编码及原理lz的算法过程如下：对消息序列xn=x1x2x3xn从左到右进展阅

7、读，并以此进展lz编码：(1输入流中的数据x1，x2，xn依次经过前缓冲区。(4假设还有数据进入缓冲区，那么转1，继续此过程。(5否那么，完毕编码过程。lz算法和lz算法一样采用编码表来组织输入数据，显然lz的编码表中包含r和lz两个编码器编码的编码表。我们分别称其为编码表中的r项和lz项。这两项虽然对两个编码器来说是通用的，但实现时为了进步编码表的搜索速度，可以把两者分开处理。r的编码识别很简单，只在缓冲区中进展，对于较长的重复字符，这种编码方式简便易行，效率较高。lz编码器编码不连续的字符，当然是有效的，从而获得较高的压缩率。从lz编码过程可以看出，假设r编码器在输入流中找不到满足条件的字

8、符，那么lz编码器将单独编码输入数据。这时lz算法退化为lz算法。2.2lz算法的解码原理lz压缩算法的解码过程是编码过程的逆过程，以下是lz算法的解码过程：(1读一个编码按lz方式确定的码长；(2假设是完毕码，那么完毕解码过程；(3假设是r标志的编码，那么按照r编码规那么解码，输出原始数据；(4否那么，按lz方式解码；(5译码过程完毕。2.3lz编码的算例(1r编码器对进入前缓冲区的数据进展检测，x1=x2，x2x3，即：0重复出现2次，符合r编码的条件，那么00的lz编码为1，2，0。(2r编码器继续对进入前缓冲区的数据进展检测，x3=x4，x4x5，1重复出现2次，符合r编码的条件，那么

9、11的lz编码为2，2，1。(3r编码器继续对进入前缓冲区的数据进展检测，x5=x6，x6=x7，x7=x8，x8x9，0重复出现4次，符合r编码的条件，那么0000的lz编码为3，4，0。(4r编码器继续对进入前缓冲区的数据进展检测，x9=x10，x10=x11，x11x12，1重复出现3次，符合r编码的条件，那么111的lz编码为4，3，1。(5r编码器继续对进入前缓冲区的数据进展检测，x12x13，0仅出现1次，不符合r编码的条件，所以，不能用r编码器对其进展编码。但是，它符合lz编码的条件，由lz编码器，那么0的lz编码为5，1，0。(6r编码器继续对进入前缓冲区的数据进展检测，x13

10、=x14，x14=x15，x15x16，1重复出现3次，符合r编码的条件，那么111的lz编码为6，3，1。(7r编码器继续对进入前缓冲区的数据进展检测，x16=x17，x17=x18，x18x19，0重复出现3次，符合r编码的条件，那么000的lz编码为7，3，0。(8r编码器继续对进入前缓冲区的数据进展检测，x19=x20，x20 x21，次，符合r编码的条件，那么11的lz编码为8，2，1，1重复出现2次，符合r编码的条件，那么11的lz编码为8，2，1。(9r编码器继续对进入前缓冲区的数据进展检测，x21=x22，x22x23，次，符合r编码的条件，那么00的lz编码为9，2，0。(1

11、0r编码器继续对进入前缓冲区的数据进展检测，x23是最后一个数据，1仅出现1次，不符合r编码的条件，所以，不能用r编码器对其进展编码。但是，它符合lz编码的条件，由lz编码器，那么1的lz编码为10，1，1。(11前缓冲区没有数据通过了，编码到此完毕。所以，信源序列的lz编码为：=(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)。3lz算法与lz算法性能的比较压缩算法性能的比较一般有两个重要因素，就是平均数据压缩率和压缩时间。我们从下面例子入手，来讨论他们的压缩性能：例1：设输入流为

12、：ababbab先建立初始化字典，将信源符号a，b，预置为字典的前3项，编码位点分别为1，2，3。编码就从这个初始字典开始。3.1lz编码过程(1由于a已经在字典中了，而ab不在，输出a的编码，同时把ab添加到字典中，所以字典的第4个条目为ab令其编码位点为4，当前位置前移一位，变为1，当前字符变为b。它的lz编码为4，1，1。(2从输入流的第1个位置开始，b已在字典中了，而ba不在。同理，输出b的编码，同时把ba添加到字典中，编码位点为5，当前位置变为2，当前字符为a它的lz编码为5，1，2。(3从输入流的第2个位置开始，ab已在字典中了，而ab不在。同理，输出ab的编码，同时把ab添加到字

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

14、个位置开始，已在字典中了，而不在。同理，输出的编码，同时把添加到字典中，编码位点为10，当前位置变为7，当前字符为。它的lz编码为10，1，3。(8从输入流的第10个位置开始，已在字典中了，并且没有别的字符需要编码了。即，编码过程到此完毕。所以，它的lz编码为：=(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.2lz编码过程(1由于x1x2，a仅出现1次，不符合r编码的条件，所以，不能用r编码器对其进展编码。但是，它符合lz编码的条件，由lz编码器，那么a的lz编码为1，1，1

15、。(2由于x2x3，b仅出现1次，不符合r编码的条件，所以，不能用r编码器对其进展编码。但是，它符合lz编码的条件，由lz编码器，那么b的lz编码为2，1，2。(3由于x3x4，a仅出现1次，不符合r编码的条件，所以，不能用r编码器对其进展编码。但是，它符合lz编码的条件，由lz编码器，那么a的lz编码为3，1，1。(4由于x4x5，b仅出现1次，不符合r编码的条件，所以，不能用r编码器对其进展编码。但是，它符合lz编码的条件，由lz编码器，那么b的lz编码为4，1，2。(5由于x5x6，仅出现1次，不符合r编码的条件，所以，不能用r编码器对其进展编码。但是，它符合lz编码的条件，由lz编码器

16、，那么的lz编码为5，1，3。(6由于x6x7，b仅出现1次，不符合r编码的条件，所以，不能用r编码器对其进展编码。但是，它符合lz编码的条件，由lz编码器，那么b的lz编码为6，1，2。(7由于x7x8，a仅出现1次，不符合r编码的条件，所以，不能用r编码器对其进展编码。但是，它符合lz编码的条件，由lz编码器，那么a的lz编码为7，1，1。(8由于x8x9，b仅出现1次，不符合r编码的条件，所以，不能用r编码器对其进展编码。但是，它符合lz编码的条件，由lz编码器，那么b的lz编码为8，1，2。(9由于x9=x10，x10=x11，重复出现3次，符合r编码的条件，那么的lz编码为9，3，3。(10由于x11是最后一个数据，前缓冲区没有数据通过了，编码过程到此完毕。=(1，1，1)，(2，1，2)，(3，1，1)，(4，1，2)，(5，1，3)，(6，1，2)，(