一种快速解压的无损压缩算法*

王 松，房利国，韩炼冰，刘鸿博

（中国电子科技集团公司第三十研究所，四川 成都 610041）

0 引 言

在当前的无损压缩算法领域中，主要存在两种技术思路。一种是基于数学统计的编码压缩方法，另一种是基于数据查找及匹配的词典编码压缩方法。早期的压缩方法大都采用基于数学统计的编码方法，该编码方法最早由Shannon 和Fano 在1949 年提出[1]。在此基础上，1952 年Fano 的学生Huffman 提出了著名的霍夫曼编码[2]，是一种极为有效的二进制编码压缩方法，一直沿用至今。基于词典编码的压缩方法是1977 年在以色列人Jacob Ziv 和Abraham Lempel 发 表 的 论 文“A Universal Algorithm for Sequential Data Compression”中被首次描述，并提出了基于该方法的LZ77 压缩算法[3]。在该算法中，待处理数据会与前文进行字符串匹配，如果匹配成功，则被压缩成一个压缩块放入压缩文件。1978 年，他们又提出了改进后的LZ78 算法[4]。LZ77 的特点是将已处理的原始数据流作为词典的输入参与压缩运算。LZ78 的特点是将已处理的数据编入一个词典，通过不断扩充及维护词典来进行压缩运算。无论是LZ77 还是LZ78 算法，均可实现比基于统计编码更快的压缩和解压速度。在后来的研究过程中，LZ77 和LZ78 算法又产生了新的算法，主要发展路径如图1 所示。

图1 词典编码方法

1 LZO 压缩算法

LZO 算法由以色列数学家A.Lempel、J.Ziv 和B.Oberhumer 共同提出[5]。该算法在压缩匹配策略及存储格式上做了许多优化，以达到快速解压的目的，是目前公开算法中解压速度最快的压缩算法[6]。LZO 存在许多版本，目前最常用的版本是LZO1X_1。该版本的LZO 算法广泛应用于Linux 内核、嵌入式设备以及网络数据传输。本文使用的正是该版本。

1.1 LZO 算法搜索匹配策略

LZO 算法在进行数据压缩时采用一个哈希表来进行数据匹配。哈希表以当前待处理数据的杂凑值为索引，读取上一次该字符串出现的可能位置并进行匹配。当本次匹配失败时，算法通过二次杂凑的方式跳转到下一位置继续进行匹配操作。如果匹配成功，则根据匹配的距离和长度信息生成相应的压缩编码。如果两次匹配均未成功，则认为当前数据无法压缩。哈希表随着压缩的进行被不断更新。该匹配过程如图2 所示[7]。

字符串的搜索匹配一直是词典编码压缩算法的瓶颈。LZO 算法与LZ77、LZSS 等压缩算法相比，大大降低了字符串搜索匹配的运算量。虽然匹配结果并不是最优的，但快速的搜索匹配使得该算法更加实用。

图2 LZO 算法的两次匹配过程

1.2 LZO 算法的压缩格式

LZO 算法以字节为单位设计压缩格式。它的压缩格式根据匹配字符串的长度分两大类。当匹配长度大于等于4 Bytes 且小于等于8 Bytes 时，按照第一类压缩格式进行数据压缩。该类压缩格式的详细定义如图3 所示[8]。

图3 匹配长度小于等于8 Bytes 时压缩格式

图3 中格式一用于存储匹配距离小于等于2 kB时的压缩信息，格式二用于存储匹配距离大于2 kB且小于等于16 kB 时的压缩信息，格式三用于存储匹配距离大于16 kB 且小于48 kB 时的压缩信息。

当匹配长度大于8 Bytes 时，LZO 算法设计了两种压缩格式，如图4 所示。

图4 匹配长度大于8 Bytes 时压缩格式

图4中格式一用于存储匹配距离小于等于16 kB 时的压缩信息，格式二用于编码匹配距离大于16 kB 字节且小于48 kB 时的压缩信息。

1.3 LZO 算法的解压过程

由于LZO 算法在压缩格式上的巧妙设计，使得在解压过程中压缩编码可以很快被解析。从图3和图4 中可以分析得出，不同的编码类型可以从编码首字节的取值直接得出。如果首字节的值大于等于64，则按照图3 中格式一进行解析。如果首字节的值大于等于32 且小于64，则按照图3 第二种或图4 第一种压缩格式进行解析。如果首字节的值大于等于16 且小于32，则按照图3 第三种或图4 第二种压缩格式进行解析。如果首字节的值小于16，则说明后续数据是未进行压缩的数据。整个解压程序可以很简洁地完成，达到快速解压的目的。

2 快速解压的新无损压缩算法

从对LZO 算法的分析中可以看出，LZO 算法解压时的主要开销是对压缩格式的解析。它的最大匹配距离是48 kB，最短匹配长度是4 Bytes。实际测试中发现，对较短数据的压缩处理会大大增加解压程序的开销，却不会带来压缩率的较大提升。同时，在48 kB 匹配空间之外，经常会出现较多的匹配数据无法被压缩。针对这一问题，本文提出了一种新的压缩方法。该方法在放弃部分较短匹配数据的同时，在更大的匹配空间进行匹配搜索，在保证压缩率的同时降低了压缩文件中压缩块的数量，进一步提高了解压速度。新算法与LZO 算法的匹配长度与匹配距离对比关系如图5 所示。

图5 新算法与LZO 算法匹配策略对比

从图5 可以看出，新设计的压缩算法在匹配距离大于2 kB 时，放弃了匹配长度小于9 Bytes 的匹配数据，匹配距离由48 kB 增加到了256 kB。放弃对小于9 Bytes 匹配长度的数据压缩必然会导致压缩率的降低，然而由于新算法的匹配距离大大增加，更多匹配长度较长的数据将被压缩，可以弥补压缩率的损失。

2.1 新算法的搜索匹配策略

新算法匹配距离的大大增加，使得类似LZO 的二次杂凑的匹配策略不再适用。新算法采用了一种可扩展的多页匹配策略进行匹配，匹配策略如图6所示。

图6 新算法的匹配过程

新算法采用可配置的多页词典查找方式进行字符串匹配。这种匹配方法与LZO 算法的匹配方法相比，在词典空间的配置上更加灵活。压缩程序以当前待处理数据的杂凑值为索引，分别在匹配词典的每一页读取上一次该字符串出现的可能位置，并进行匹配。所有的匹配完成后，选取最佳的匹配结果进行处理。

2.2 新算法的存储格式

新算法同样以整字节为单位设计压缩格式，方便解压程序的处理。与LZO 算法不同，新算法的压缩格式是按照匹配距离是否小于2 kB 来进行分类的。当匹配距离小于2 kB 时，新算法的压缩格式的详细定义如图7 所示。

图7 匹配距离小于2 kB 时的压缩格式

图7 中格式一用于存储匹配长度小于等于17 Bytes 时的压缩信息，格式二用于存储匹配长度大于 17 Bytes 时的压缩信息。

当匹配距离大于等于2 kB 时，新算法的压缩格式的详细定义如图8 所示。

图8中格式一用于存储匹配长度小于等于18 Bytes 时的压缩信息，格式二用于存储匹配长度大于 18 Bytes 时的压缩信息。

新算法的存储格式与LZO 算法相比，降低了压缩块格式的数量，使得解压程序对压缩格式的判断更加简单，有利于提高解压速度。

3 对比测试

在新算法实现完成并验证正确性后，本文将其与LZO 算法做了测试对比。

新算法的匹配词典大小灵活可配，测试时匹配词典设置为两个匹配页面。此时，新算法的压缩率与LZO 算法几乎一致，更利于比较两个压缩算法的解压性能。为了降低操作系统对测试结果的影响，本次测试在无操作系统的DSP 芯片上进行，DSP 芯片型号为TMS320C6748[9]。测试时，待解压的数据及解压后数据均存放在与DSP 连接的片外存 储器中。

图8 匹配距离大于等于2 kB 时的压缩格式

测试样本选择了PPT 幻灯片、PDF 文件、WORD 文档、图片、网页以及EXCEL 表格等各种常见的文件类型。压缩算法对测试样本文件的压缩率如表1 所示。

从表1 中可以看出，当匹配词典设置为两个页面时，两个压缩算法的压缩率比较接近。但是，在几乎相同压缩率的情况下，新算法可降低压缩文件中20%～50%的压缩块数量，非常有利于提升解压速度。测试表1 中压缩后文件的解压速度，结果如表2 所示。

表2 的测试结果表明，在几乎同等压缩率情况下，新算法的解压速度与LZO 算法相比得到了较大提升。这种差别是由二者的匹配策略和存储格式不同造成的。新算法在更大空间上进行了匹配操作，提升了匹配成功概率，同时放弃了对大量较短匹配字符串的压缩处理，使得解压程序需要解析的压缩编码大大减少，从而提高了解压速度得。

表1 新算法与LZO 算法压缩率比较

表2 新算法与LZO 解压速度比较

4 结 语

本文在研究LZO 压缩算法的基础上，设计了一个新的压缩算法。新算法在放弃对一些小块数据压缩处理的同时，在更大的空间上进行搜索匹配，可以有效降低压缩文件中的压缩块数量。测试结果表明，提出的压缩算法的解压速度与目前公开算法中解压最快的LZO 算法相比具有一定优势，具备较高的实用价值。