LZMA和LZ4相关压缩原理

LZ77LZ78是Abraham Lempel与Jacob Ziv在1977年以及1978年发表的论文中的两个无损数据压缩算法。这两个算法是大多数LZ算法变体如LZW、LZSS以及其它一些压缩算法的基础。与最小冗余编码器或者进程长度编码器不同,这两个都是基于字典的编码器。LZ77是“滑动窗”压缩算法,这个算法后来被证明等同于LZ78中首次出现的显式字典编码技术。

LZ77算法针对过去的数据进行处理,而LZ78算法却是针对后来的数据进行处理。LZ78通过对输入缓存数据进行预先扫描与它维护的字典中的数据进行匹配来实现这个功能,在找到字典中不能匹配的数据之前它扫描进所有的数据,这时它将输出数据在字典中的位置、匹配的长度以及找不到匹配的数据,并且将结果数据添加到字典中。

尽管在最初得到流行,但是后来LZ78的普及逐渐衰减,这可能是由于在刚LZ78出现的一些年份,一部分LZ78算法获得了美国专利保护。最流行的LZ78压缩形式是LZW算法,这个算法是Terry Welch所开发的一个LZ78变体。

LZMA(Lempel-Ziv-Markov chain-Algorithm的缩写)是2001年以来得到发展的一个数据压缩算法,它用于7-Zip归档工具中的7z格式和 Unix-like 下的 xz 格式。它使用类似于LZ77的字典编码机制,在一般的情况下压缩率比bzip2为高,用于压缩的字典文件大小可达4GB。

C++语言写成的LZMA开放源码压缩库使用了区间编码支持的LZ77改进压缩算法以及特殊的用于二进制的预处理程序。LZMA 对数据流、重复序列大小以及重续序列位置单独进行了压缩。LZMA支持几种散列链变体、二叉树以及基数树作为它的字典查找算法基础。

LZ4是一种无损数据压缩算法,着重于压缩和解压缩速度。它属于面向字节的LZ77压缩方案家族。

LZ77压缩算法通过“滑动窗口”来实现数据压缩。滑动窗口由搜索缓冲区(Search Buffer)前向查找缓冲区(Look ahead Buffer)组成。通过对字体串的滑动搜索压缩输出一系列<x,y,z>三元组,其中x代表数据在前面的偏移,y代表匹配的字符串长度,z代表下一个字符串。以字符串“abracadabrarray”的压缩过程为例:

压缩过程

  1. 搜索缓冲区大小设为8,初始化为空。前向查找缓冲区大小设为6,初始化为abraca。
  2. 对于当前的前向查找缓冲区第一个字符a,向前查找是否有匹配的a,由于搜索缓冲区此时为空所以没有匹配,因此输出<0,0,a>,窗口向前移动一位,搜索缓冲区变为a,前向查找缓冲区变为bracad。
  3. 对于当前的前向查找缓冲区第一个字符b,与前面的字符a类似,输出<0,0,b>,意为没有匹配、长度为0,下一个字符为b
    ,窗口向前移动一位,搜索缓冲区变为ab,前向查找缓冲区变为racada。
  4. 对于当前的前向查找缓冲区第一个字符r,与前面的字符b类似,输出<0,0,r>,意为没有匹配、长度为0,下一个字符为b
    ,窗口向前移动一位,搜索缓冲区变为abr,前向查找缓冲区变为acadab。
  5. 对于当前的前向查找缓冲区第一个字符a,我们终于在搜索缓冲区里能找到一个匹配了,这个a和它的相对距离是3,并且最长匹配长度为1(abr和acadab匹配),此时下一个字符为c。所以最后的输出是<3,1,c>。窗口向前移动到字符c为止,搜索缓冲区变abrac,前向查找缓冲区变为adabra。
  6. 对于当前的前向查找缓冲区第一个字符a,和上一条类似,最后输出<2,1,d>。窗口向前移动到字符d为止,搜索缓冲区变abracad,前向查找缓冲区变为abrarr。
  7. 此时前向查找缓冲区第一个字符a在前面的搜索缓冲区中有两个a可以匹配,分别是偏移3位置和偏移7位置,但偏移3位置只能匹配一个字符a,而偏移7位置可以匹配长度为4的字符串abra。所以按最估策略,此时的输出是<7,4,r>。窗口向前移动到字符r为止,搜索缓冲区变cadabrar,前向查找缓冲区变为ray。
  8. 同第5条类似,最后输出<3,2,y>。


    至此,我们完成了LZ77算法的压缩过程。可以看出,在窗口滑动过程中,通过向前在搜索缓冲区中查找相同的模式,实现了数据的压缩。这样的算法非常高效,但是在解压时必须是按顺序解压,前面的数据如果还没有还原,那么后续的数据也没有办法解压缩。

    解压过程

LZ77的解压缩过程相对更简单。还是以上面的字符串为例:

  1. <0,0,a> 直接输出a,当前解压结果为a。
  2. <0,0,b> 直接输出b,当前解压结果为ab。
  3. <0,0,r> 直接输出r, 当前解压结果为abr。
  4. <3,1,c> 意为对当前结果abc,向前偏移3位开始,有一个长度为1的匹配,并且之后的字符为c,所有最后解压结果为abr + a + c = abrac。
  5. <2,1,d> 意为对当前结果abrac,向前偏移2位开始,有一个长度为1的匹配,并且之后的字符为d,所有最后解压结果为abrac + a + d = abracad。
  6. <7,4,r> 意为对当前结果abracad,向前偏移7位开始,有一个长度为4的匹配,并且之后的字符为r,所有最后解压结果为abracad + abra + r = abracadabrar。
  7. <3,2,y> 意为对当前结果abracadabrar,向前偏移3位开始,有一个长度为2的匹配,并且之后的字符为d,所有最后解压结果为abracadabrar + ra + y = abracadabrarray。