欢迎来到学术参考网

关于LZW算法的改进研究

发布时间:2015-07-01 16:33
【摘 要】在分析lzw算法的基础上,对lzw算法的缺陷进行了探讨。并对lzw算法进行了改进,大幅度减少了编码的长度,降低了匹配长度取值变化的影响,完全兼容lzw算法,在平均压缩率方面有较大的提高,而且对改进的算法进行了分析论证。
【关键词】数据压缩lzw算法缓冲区

lzw算法的实质是无损压缩技术[1-3],lzw算法通过对输入流进行分析,自适应地生成一个包含输入流中不重复子串的串表,将每一子串映射为一独立的码字输出。这样,它就充分利用了相邻输入之间的相关性,可以取得超过信源一阶熵的编码效率。然而,受缓存容量、计算复杂度和计算速度等因素的限制,串表的长度受到一定限制,且一般信源所具有的局部平稳性随缓存容量加大,编码效率提高不大。即:它自身固有一定的缺陷与不足,难以满足人们的需要,对它进行改进一直成为人们的研究目标之一[4-6]。为了解决这一问题,本文对lzw算法进行了改进,命名为lzwc编码算法。它兼有lzw算法的优点,还具有自身的优越性。首先对lzw算法进行一些必要的介绍和分析。
算法
lzw算法[1]由韦尔奇()于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<m,我们已经得到它的编码: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及相应的树确定,那么我们就可读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.2lzw算法的原理
lzw算法通过编码表来组织输人字符串,并把它们转换成一定长度的编码。lzw算法有一个重要的特性称作前缀性,即如果一个字符串在编码表上,那它的前缀串也在编码表上。例如:a、b为两个不同的字符串,ab组成一新的字符串,a为b的前缀串,如果b在编码表中,则一定在编码表中。
lzw通过编码表识别源输人字符序列,通过向编码表中增加新的字符串,从而识别更多、更长的字符序列。但由于前缀性的约束,这种识别一般每次只在原来的基础上增加一个字符,依次进行。同时,由于编码算法没有很强的分析功能,使它不知道哪些字符序列将来出现的概率较大,所以它具有一定的盲目性。例如,有一个长度为n的字符序列,lzw编码表要完全识别它,则至少需要该序列部分或全部重复出现n次。但是,当一个较长的字符串重复出现两次,我们就能够容易识别它,而且这样的字符串再次出现的概率是非常大的。基于这样一种认识,本文在lzw算法的基础上,构造了一种新的编码算法,我们把新算法称为lzwc编码算法,一般情况下它对数据的压缩率比lzw算法有大幅度提高。新算法在最差的情况下可退化成标准的lzw算法。下面对lzwc算法的原理进行详细的介绍。
2lzwc算法
lzwc算法的基本原理是针对源输人数据中不同特点的数据序列,采用不同的编码器分别编码。数据序列的分类则是根据它的特点,通过对原始数据序列的分析来完成。
lzwc算法共有两个编码器,它们是:
(1)重复编码器(repeatcorder),简称rc。
(2)lzw编码器。
rc对输入流中重复的数据进行编码,剩下的数据由则由lzw编码器进行编码。rc编码器和lzw编码器的编码通过lzw编码器的编码表统一起来。
2.1lzwc算法的编码及原理
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.2lzwc算法的解码原理
lzwc压缩算法的解码过程是编码过程的逆过程,以下是lzwc算法的解码过程:
(1)读一个编码(按lzw方式确定的码长);
(2)如果是结束码,则结束解码过程;
(3)如果是rc标志的编码,则按照rc编码规则解码,输出原始数据;
(4)否则,按lzw方式解码;
(5)译码过程结束。
2.3lzwc编码的算例
下面,我们用一个例子来说明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)}。

3lzwc算法与lzw算法性能的比较
压缩算法性能的比较一般有两个重要因素,就是平均数据压缩率和压缩时间。我们从下面例子入手,来讨论他们的压缩性能:
例1:设输入流为:ababcbabccc
先建立初始化字典,将信源符号a,b,c预置为字典的前3项,编码位点分别为1,2,3。编码就从这个初始字典开始。
3.1lzw编码过程
(1)由于"a"已经在字典中了,而"ab"不在,输出"a"的编码,同时把"ab"添加到字典中,所以字典的第4个条目为"ab"令其编码位点为4,当前位置前移一位,变为1,当前字符变为"b"。它的lzw编码为(4,1,1)。
(2)从输入流的第1个位置开始,"b"已在字典中了,
而"ba"不在。同理,输出"b"的编码,同时把"ba"添加到字典中,编码位点为5,当前位置变为2,当前字符为"a"它的lzw编码为(5,1,2)。
(3)从输入流的第2个位置开始,"ab"已在字典中了,而"abc"不在。同理,输出"ab"的编码,同时把"abc"添加到字典中,编码位点为6,当前位置变为3,当前字符为"c"。它的lzw编码为(6,1,4)。
(4)从输入流的第3个位置开始,"c"已在字典中了,而"cb"不在。同理,输出"c"的编码,同时把"cb"添加到字典中,编码位点为7,当前位置变为4,当前字符为"c"。它的lzw编码为(7,1,3)。
(5)从输入流的第4个位置开始,"ba"已在字典中了,而"bab"不在。同理,输出"ba"的编码,同时把"bab"添加到字典中,编码位点为8,当前位置变为5,当前字符为"b"。它的lzw编码为(8,1,5)。
(6)从输入流的第5个位置开始,"b"已在字典中了,而"bc"不在。同理,输出"b"的编码,同时把"bc"添加到字典中,编码位点为9,当前位置变为6,当前字符为"c"。它的lzw编码为(9,1,2)。
(7)从输入流的第6个位置开始,"c"已在字典中了,而"cc"不在。同理,输出"c"的编码,同时把"cc"添加到字典中,编码位点为10,当前位置变为7,当前字符为"c"。它的lzw编码为(10,1,3)。
(8)从输入流的第10个位置开始,"cc"已在字典中了,并且没有别的字符需要编码了。即,编码过程到此结束。
所以,它的lzw编码为:
c’={(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.2lzwc编码过程
(1)由于x1≠x2,a仅出现1次,不符合rc编码的条件,所以,不能用rc编码器对其进行编码。但是,它符合lzw编码的条件,由lzw编码器,则a的lzwc编码为(1,1,1)。
(2)由于x2≠x3,b仅出现1次,不符合rc编码的条件,所以,不能用rc编码器对其进行编码。但是,它符合lzw编码的条件,由lzw编码器,则b的lzwc编码为(2,1,2)。
(3)由于x3≠x4,a仅出现1次,不符合rc编码的条件,所以,不能用rc编码器对其进行编码。但是,它符合lzw编码的条件,由lzw编码器,则a的lzwc编码为(3,1,1)。
(4)由于x4≠x5,b仅出现1次,不符合rc编码的条件,所以,不能用rc编码器对其进行编码。但是,它符合lzw编码的条件,由lzw编码器,则b的lzwc编码为(4,1,2)。
(5)由于x5≠x6,c仅出现1次,不符合rc编码的条件,所以,不能用rc编码器对其进行编码。但是,它符合lzw编码的条件,由lzw编码器,则c的lzwc编码为(5,1,3)。
(6)由于x6≠x7,b仅出现1次,不符合rc编码的条件,所以,不能用rc编码器对其进行编码。但是,它符合lzw编码的条件,由lzw编码器,则b的lzwc编码为(6,1,2)。
(7)由于x7≠x8,a仅出现1次,不符合rc编码的条件,所以,不能用rc编码器对其进行编码。但是,它符合lzw编码的条件,由lzw编码器,则a的lzwc编码为(7,1,1)。
(8)由于x8≠x9,b仅出现1次,不符合rc编码的条件,所以,不能用rc编码器对其进行编码。但是,它符合lzw编码的条件,由lzw编码器,则b的lzwc编码为(8,1,2)。
(9)由于x9=x10,x10=x11,c重复出现3次,符合rc编码的条件,则ccc的lzwc编码为(9,3,3)。
(10)由于x11是最后一个数据,前缓冲区没有数据通过了,编码过程到此结束。
c’={(1,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算法的平均字符压缩率较高,压缩时间较短,较lzw算法有一定的优势。
4结论
本文在lzw算法的基础上,提出了一种改进的算法。命名为lzwc算法,lzwcs算法在压缩方面比lzw算法有了较大的提高,它适合对文本、字符、数据等类型的文件进行压缩。对于重复字符很少的输入流,新算法和lzw算法的压缩效果差别不大。但是,对于重复字符较多的输入流,新算法压缩效果的优势十分明显。但由于新算法兼容lzw算法,所以,它在应用中比单纯的lzw算法具有更好的性能。

参考文献
[1]姜丹.信息论与编码[m].合肥:中国科学技术大学出版社,2001.
[2]张凤林,刘思峰.lzw*:一个改进的lzw数据压缩算法[j].小型微型计算机系统.2006,27(10)1897-1899
[3]吴宇新,余松煌.对lzw算法的改进及其在图像无损压缩中的应用[j].上海交通大学学报,1998,3(29):110-113
[4]卓越,杨长生,宋广华.一种基于自适应字典的通用无损压缩算法[j].计算机工程,2001,27(2):149-151
[5]mpression:thecompletereference[m].springer-verlagnewyorkinc.,200

上一篇:浅谈基于视觉感知的船闸监控系统研究与实现

下一篇:浅谈基于Simulink的自动控制系统性能的分析与仿真