关于LZW算法的改进研究

1、文章来源 毕业论文网 关于lzw算法的改进研究文章来源 毕业论文网 【摘要】 在分析lzw算法的基础上，对lzw算法的缺陷进行了探讨。并对lzw算法进行了改进，大幅度减少了编码的长度，降低了匹配长度取值变化的影响，完全兼容lzw算法，在平均压缩率方面有较大的提高，而且对改进的算法进行了分析论证。 【关键词】  数据压缩   lzw算法   缓冲区        lzw算法的实质是无损压缩技术1-3，lzw算法通过对输入流进行分析，自适应地生成一个包含输入流中不重复子串的串表，

2、将每一子串映射为一独立的码字输出。这样，它就充分利用了相邻输入之间的相关性，可以取得超过信源一阶熵的编码效率。然而，受缓存容量、计算复杂度和计算速度等因素的限制，串表的长度受到一定限制，且一般信源所具有的局部平稳性随缓存容量加大，编码效率提高不大。即：它自身固有一定的缺陷与不足，难以满足人们的需要，对它进行改进一直成为人们的研究目标之一4-6。为了解决这一问题，本文对lzw算法进行了改进，命名为lzwc编码算法。它兼有lzw算法的优点，还具有自身的优越性。首先对lzw算法进行一些必要的介绍和分析。         1. lz

3、w算法         lzw算法1由韦尔奇（t.a.welch）于1984年通过对lz算法的改进。开发出的一种更优算法。它是一种基于字典的编码方法。并且它是lz系列码中应用最广，变形最多的一种算法。lzw压缩有3个重要的对象：数据流、编码流和编译表。在编码时，数据流是输入对象，编码流就是输出对象；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都需要借助的对象。          1.1lzw算法的编码原理  

4、       lzw算法的编码原理为：对消息序列xn=x1x2x3…xn从左到右进行阅读，并以此进行lzw编码：          (1)对x1显然是第一次出现，它的前面也没有字符，那么他的编号是1，它的码元为(1,0, x1)。          (2)对于x2它可能有两种情况发生，即x1=x2或x1≠x2。对此，有    &

5、nbsp;    如果x1=x2，那么对于x2不作编码，而对x3的编码位点取2，连接位点则为1，这表示对x3作第二次编码，它与第一次编码的x1相连接。          如果x1≠x2，那么x2的编码位点取为2，连接位点则为0，这表示对x2作第二次编码，它的前面没有出现过相同的字符。          (3)依照上述步骤递推，如果对向量xn=x1x2x3…xn，n<m，我们已经得到

6、它的编码：c=(i,li, xji),i=1,2, …, k .         对上式的c满足的条件:对每一个i有且只有一对(i,li)，使li<i<ji成立。那么c构成一lzw树。由树的构造可知，对每个点i，它的枝li是唯一的。因此，树c的全部枝为li，i=0，1，…,k 确定，而且每个li与xn中的子向量xαi对应。          (4)如向量xn中的编码c及相应的树确定，那么我们就可

7、读xn+1,xn+2,…, xn+k,并对它们继续进行编码，如果有一个ik使xαi=(xn+1,xn+2,…, xn+k)成立，而且对任何ik都有：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）。 &n

8、bsp;       以此类推，就可以完成对xn的编码c。         2.2 lzw算法的原理         lzw算法通过编码表来组织输人字符串，并把它们转换成一定长度的编码。lzw算法有一个重要的特性称作前缀性，即如果一个字符串在编码表上，那它的前缀串也在编码表上。例如:a、b为两个不同的字符串，ab组成一新的字符串，a为b的前缀串，如果b在编码表中，则一定在编码表中。  &

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

10、种新的编码算法，我们把新算法称为lzwc编码算法，一般情况下它对数据的压缩率比lzw算法有大幅度提高。新算法在最差的情况下可退化成标准的lzw算法。下面对lzwc算法的原理进行详细的介绍。         2  lzwc算法         lzwc算法的基本原理是针对源输人数据中不同特点的数据序列，采用不同的编码器分别编码。数据序列的分类则是根据它的特点，通过对原始数据序列的分析来完成。     &nbs

11、p;   lzwc算法共有两个编码器，它们是：         (1） 重复编码器（repeatcorder），简称rc。         (2） lzw编码器。         rc对输入流中重复的数据进行编码，剩下的数据由则由lzw编码器进行编码。rc编码器和lzw编码器的编码通过lzw编码器的编码表统一起来。         2.1  lzwc算法的编码及原理         lzwc的算法过程如下：         对消息序列xn=x1x2x3…xn从左到右进行阅读，并以此进行lzwc编码：