论文发表网征稿LZW算法研究

　　LZW算法的实质是无损压缩技术[1-3]，LZW算法通过对输入流进行分析，自适应地生成一个包含输入流中不重复子串的串表，将每一子串映射为一独立的码字输出。发表的一篇电子论文，办的非常成功，极具口碑。在这里，你可以找到最具时事性的文章和最具代表性的各类文章。当然，因为免费和开源，大家都可以学习、借鉴和共同使用，如果你需要专属于个人的原创文章，请点击链接获得专业文秘写作服务。

　　【摘　要】 在分析LZW算法的基础上，对LZW算法的缺陷进行了探讨。并对LZW算法进行了改进，大幅度减少了编码的长度，降低了匹配长度取值变化的影响，完全兼容LZW算法，在平均压缩率方面有较大的提高，而且对改进的算法进行了分析论证。

　　【关键词】 数据压缩 LZW算法 缓冲区

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

　　1. LZW算法

　　LZW算法[1]由韦尔奇(T.A.Welch)于1984年通过对LZ算法的改进。开发出的一种更优算法。它是一种基于字典的编码方法。并且它是LZ系列码中应用最广，变形最多的一种算法。LZW压缩有3个重要的对象：数据流、编码流和编译表。在编码时，数据流是输入对象，编码流就是输出对象;在解码时，编码流则是输入对象，数据流是输出对象;而编译表是在编码和解码时都需要借助的对象。

　　1.1LZW算法的编码原理

　　LZW算法的编码原理为：对消息序列xn=x1x2x3…xn从左到右进行阅读，并以此进行LZW编码：

　　(1)对x1显然是第一次出现，它的前面也没有字符，那么他的编号是1，它的码元为(1,0, x1)。

　　(2)对于x2它可能有两种情况发生，即x1=x2或x1≠x2。对此，有

　　①如果x1=x2，那么对于x2不作编码，而对x3的编码位点取2，连接位点则为1，这表示对x3作第二次编码，它与第一次编码的x1相连接。

　　②如果x1≠x2，那么x2的编码位点取为2，连接位点则为0，这表示对x2作第二次编码，它的前面没有出现过相同的字符。

　　(3)依照上述步骤递推，如果对向量xn=x1x2x3…xn，n

　　对上式的C满足的条件:对每一个i有且只有一对(i,li)，使li

　　(4)如向量xn中的编码C及相应的树确定，那么我们就可读xn+1,xn+2,…, xn+k,并对它们继续进行编码，如果有一个i≦k使xαi=(xn+1,xn+2,…, xn+k)成立，而且对任何i≦k都有：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)。

　　以此类推，就可以完成对xn的编码C。

　　2.2 LZW算法的原理

　　LZW算法通过编码表来组织输人字符串，并把它们转换成一定长度的编码。LZW算法有一个重要的特性称作前缀性，即如果一个字符串在编码表上，那它的前缀串也在编码表上。例如:A、B为两个不同的字符串，AB组成一新的字符串，A为B的前缀串，如果B在编码表中，则一定在编码表中。

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

　　2 LZWC算法

　　LZWC算法的基本原理是针对源输人数据中不同特点的数据序列，采用不同的编码器分别编码。数据序列的分类则是根据它的特点，通过对原始数据序列的分析来完成。

　　LZWC算法共有两个编码器，它们是：

　　(1) 重复编码器(RepeatCorder)，简称RC。

　　(2) LZW编码器。

　　RC对输入流中重复的数据进行编码，剩下的数据由则由LZW编码器进行编码。RC编码器和LZW编码器的编码通过LZW编码器的编码表统一起来。

　　2.1 LZWC算法的编码及原理

　　LZWC的算法过程如下：

　　对消息序列xn=x1x2x3…xn从左到右进行阅读，并以此进行LZWC编码：

　　(1) 输入流中的数据x1，x2，…，xn依次经过前缓冲区。

　　(4) 假如还有数据进入缓冲区，则转1)，继续此过程。

　　(5) 否则，结束编码过程。

　　LZWC算法和LZW算法一样采用编码表来组织输入数据，显然LZW的编码表中包含RC和LZW两个编码器编码的编码表。我们分别称其为编码表中的RC项和LZW项。这两项虽然对两个编码器来说是通用的，但实现时为了提高编码表的搜索速度，可以把两者分开处理。

　　RC的编码识别很简单，只在缓冲区中进行，对于较长的重复字符，这种编码方式简便易行，效率较高。

　　LZW编码器编码不连续的字符，当然是有效的，从而获得较高的压缩率。从LZWC编码过程可以看出，如果RC编码器在输入流中找不到满足条件的字符，则LZW编码器将独自编码输入数据。这时LZWC算法退化为LZW算法。

　　2.2 LZWC算法的解码原理

　　LZWC压缩算法的解码过程是编码过程的逆过程，以下是LZWC算法的解码过程：

　　(1)读一个编码(按LZW方式确定的码长);

　　(2)如果是结束码，则结束解码过程;

　　(3)如果是RC标志的编码，则按照RC编码规则解码，输出原始数据;

　　(4)否则，按LZW方式解码;

　　(5)译码过程结束。

　　2.3 LZWC编码的算例

　　下面，我们用一个例子来说明LZWC编码算的过程。例如：假设信源发出的序列为：00110000111011100011001解：依题意，有：信源序列的数据依次经过前缓冲区，则

　　(1)RC编码器对进入前缓冲区的数据进行检测，x1=x2，x2≠x3，即：0重复出现2次，符合RC编码的条件，则00的LZWC编码为(1，2，0)。

　　(2)RC编码器继续对进入前缓冲区的数据进行检测，x3=x4，x4≠x5，1重复出现2次，符合RC编码的条件，则11的LZWC编码为(2，2，1)。

　　(3)RC编码器继续对进入前缓冲区的数据进行检测，x5=x6，x6=x7，x7=x8，x8≠x9，0重复出现4次，符合RC编码的条件，则0000的LZWC编码为(3，4，0)。

　　(4)RC编码器继续对进入前缓冲区的数据进行检测，x9=x10，x10=x11，x11≠x12，1重复出现3次，符合RC编码的条件，则111的LZWC编码为(4，3，1)。

　　(5)RC编码器继续对进入前缓冲区的数据进行检测，x12≠x13，0仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则0的LZWC编码为(5，1，0)。

　　(6)RC编码器继续对进入前缓冲区的数据进行检测，x13=x14，x14=x15，x15≠x16，1重复出现3次，符合RC编码的条件，则111的LZWC编码为(6，3，1)。

　　(7)RC编码器继续对进入前缓冲区的数据进行检测，x16=x17，x17=x18，x18≠x19，0重复出现3次，符合RC编码的条件，则000的LZWC编码为(7，3，0)。

　　(8)RC编码器继续对进入前缓冲区的数据进行检测，x19=x20，x20≠x21，次，符合RC编码的条件，则11的LZWC编码为(8，2，1)，1重复出现2次，符合RC编码的条件，则11的LZWC编码为(8，2，1)。

　　(9)RC编码器继续对进入前缓冲区的数据进行检测，x21=x22，x22≠x23，次，符合RC编码的条件，则00的LZWC编码为(9，2，0)。

　　(10)RC编码器继续对进入前缓冲区的数据进行检测，x23是最后一个数据，1仅出现1次，不符合RC编码的条件，所以，不能用RC编码器对其进行编码。但是，它符合LZW编码的条件，由LZW编码器，则1的LZWC编码为(10，1，1)。

　　(11)前缓冲区没有数据通过了，编码到此结束。

　　所以，信源序列的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)}。

　　阅读范文：计算机论文范文家庭自动化系统

　　本篇文章是由《计算机辅助工程》发表的一篇计算机论文，是上海海事大学主办的学术性刊物，创刊于1992年，是我国计算机界与工程界的重要学术性刊物之一。本刊主要刊登计算机技术及其应用和相关领域的学术论文，如计算机辅助设计与图形学技术及应用、专家系统、知识工程、计算机网络与通信、分布式系统、计算机软件与理论、程序设计语言、操作系统、数据库、计算机辅助教学、制造业信息化、物流工程信息化、交通运输工程信息化、信息管理技术及应用、人工智能技术及应用、电气自动化等领域的文章，以及有价值的研究报告和研究简介。