改进的LZSS压缩算法

改进的LZSS压缩算法

王娟1  刘教民2 檀柏红2

(1中国人民武装警察部队学院，河北廊坊065000；2河北省教育厅，河北石家庄 050000)

摘  要：本文提出了LZSS压缩算法在进行文本压缩时存在的问题，并给出了解决方法。改进后的算法具有较高的压缩率，实验结果令人满意。

关键词：LZSS；数据压缩

1 引言

随着计算机技术的高速发展，各种系统数据量越来越大，给信息存储特别是网络传输带来诸多的困难，并己成为有效获取和使用信息的瓶颈。为了节省信息的存储空间和提高信息的传输效率，必须对大量的实际数据进行压缩。实践中采用数据压缩技术，通常可以节省80％以上的费用，并且使得一些困难问题转而在技术上能够实现。

目前常用的压缩编码方法分为两大类：一类是无损压缩法，也叫熵编码；另一类是有损压缩法，也叫熵压缩法。熵压缩法压缩了熵，会减少信息量，因而不能完全恢复，对于图像、动画、和音频等多媒体信息是有效的，但对于程序文件、数据库文件等就行不通了。

2 LZSS压缩算法

LZSS是词典编码无损压缩技术的一种[1]。词典编码无损压缩技术主要有LZ77、LZSS、LZ78、LZW等几种基本算法,它们一起垄断了当今的通用数据压缩领域。LZ78和LZW两种算法的编译码方法较为复杂,实现起来较为困难,而LZ77的压缩率又相对较低,比较而言LZSS算法在单片机上实现起来较为理想,其压缩率较高,编译码算法也较为简单。LZSS压缩算法的字典模型使用了自适应的方式,也就是说,将已经编码过的信息作为字典,如果要编码的字符串曾经出现过,就输出该字符串的出现位置及长度,否则输出新的字符串。实际使用时,由于被压缩的文件往往较大,一般使用“滑动窗口压缩”方式,就是将一个虚拟的,可以跟随压缩进程滑动的窗口作为术语字典。

3改进的LZSS压缩算法

3.1 LZSS算法存在的问题

LZSS算法是一种很好的算法，但是在实现的过程中发现该算法仍有不少可改进之处。改进算法的思路有两条，一是从过程出发，即提高编码程序的效率，在压缩率保持不变的前提下尽量减少算法复杂度；二是从结果出发，分析压缩代码对，尽量精简压缩代码对每个分量的表示方法，并尽量减少压缩代码所占用的空间，以达到较好的压缩效果。下面分别从这两个方面出发，提出几个改进方案，并给出部分代码实现。

在匹配字符串长度编码时，必须考虑到它在大多数情况下不会太大，少数情况下才会发生大字符串的匹配，因此，无论匹配长度为多长，代码对(1，匹配位置，匹配长度)的长度都是固定的，对于较小的匹配长度来说，仍可能存在一定的冗余。例如，当偏移量的位数为12（文本窗口大小为4096字节）、匹配长度的位数为 4（匹配长度最大为16）时，加上1位前缀，输出固定为17位。若匹配长度为2或3，此时只用2位即可表示这个匹配长度，加上12位的偏移量和1位的前缀，只要输出15位，原理上输出代码可减少2位，从而实现了更高效的压缩。但这样一来，匹配长度不固定，在译码时无法正确识别匹配长度，也就无法正确译码。因此需要寻找一种能正确识别变长的匹配长度的机制。

3.2 改进LZSS算法之一——前缀编码

在使用可变长的编码方式来表示匹配长度值时，必须设计出一种编码方式，使得译码程序可以方便地分离每个字符的编码部分。于是有了一种叫“前缀编码”的技术，其主导思想是：任何一个字符的编码，都不是另一个字符编码的前缀。即任何一个字符的编码，都不是由另一个字符的编码加上若干位0或1组成。表1为前缀编码的一个最简单的例子。

表1 前缀编码举例

_____________________________________________

符号     A      B      C      D      E

_____________________________________________

编码     0      10     110    1110    11110

_____________________________________________

有了上面的码表，就可以轻松地从下面这串二进制数据流中分辨出真正的信息内容：

     1110010101110110111100010→十六进制的DABBDCEAAB。

适用于此处的好的编码方案很多，在这里介绍其中一种应用非常广泛的 Golomb编码。

假设对正整数x进行Golomb编码，选择参数 m，令 

式中  b、m、q、r为在编码时取的经验值，则 x 可以被编码为两部分，第一部分是由q个1加1个0组成，第二部分为m比特二进制数，其值为r。m = 0, 1, 2, 3时的Golomb编码表如表2所示。 从表2中可见，Golomb编码不但符合前缀编码的规律，而且可以用较少的位表示较小的x值，而用较长的位表示较大的x值。

表2  Golomb码表

9     111111110     11110 0      110 00        1 000

    这样，如果 x 的取值倾向于比较小的数值时，Golomb 编码就可以有效地节省空间。当然，根据 x 的分布规律不同，我们可以选取不同的 m 值以达到最好的压缩效果。参数 m 的选择，一般经验是取 3 或 4 即可。

3.3改进LZSS算法之二——可变窗口

一般来讲，编码的设计要根据待编码的数值的分布情况而定。对于压缩代码对的第二个分量匹配位置，即窗口内的偏移，通常的经验是，偏移接近窗口尾部的情况要多于接近窗口头部的情况，这是因为字符串在与其接近的位置较容易找到匹配串。对于普通的窗口大小（例如 4096 字节）来说，偏移值基本上是均匀分布的，可以用固定的位数来表示它。编码 off 需要的比特数为 

Bitnum=Upper-Bound (log2(TEXT-SIZE))

Upper-Bound(log2(n))函数取log2(n)的上限，代码实现如下：

Int LZARI: UpperLog2 (int n){

  Int I=0;

  If  (n>0){

             Int m=1;

             While (1) {

                       If (m>=n) return I;

                       M