LZ4压缩算法分析

原创
2018/11/23 19:49
阅读数 4.8K

LZ4压缩算法是LZ算法系列中的一种,而且网上也号称是目前最快的压缩算法之一,现没时间亲测也不对LZ系列算法展开讨论只分析LZ4。LZ4算法有两种压缩方法,一种侧重于压缩速度,另一种侧重于压缩比,现讨论的是侧重于压缩速度的方法。

现给定字符串dfabcdefghijklmnabcdkkkkkk,后面出现的“abcd”可以用前面的“abcd”通过偏移量offset与匹配长度matchLength进行代替,实际上这就是LZ4算法的主要思想。LZ4算法的最小匹配长度是4,最后5个字符按照字面量存储,也就是说当字节数<=9时是不压缩的(最后会给出解释)。

详细的LZ4编码数据涉及到的变量如下:

1、字面量值literalValue,即dfabcdefghijklmn

2、字面量值长度literalLength=16

3、匹配长度matchLength=4

4、偏移量offset=16-2=14

编码格式如下:

token_literalLength(可选)_literalValue_offset_matchLength(可选)

token占用1个字节,前4位代表字面量值长度,如果长度值>=15与255(1个字节的无符号数)进行比较,如果比255大则减去255并写入1个字节,将剩余的值如此循环比较,反之直接写入1个字节。如字面量长度值为512,token前4位等于15,  literalLength等于512-15=255+242占用两个字节。后四位表示匹配的长度,原理和前面一样,在实现的时候可以优化一下,因为默认最小匹配长度为4,所以可以将值减4。如匹配长度为512,token后4位等于15,matchLength等于512-4-15=255+238占用两个字节。literalLength与matchLength为什么要加入可选,就是这个原因,因为值小于15的时候,4个比特位已经足够表示了。offset占用2个字节,即最大值为65535。

上面的字符串压缩后的字节序列是(0b11110000)_(1)_(dfabcdefghijklmn)_(14)------(0b01100000)_(kkkkkk)

问题一:为什么最小匹配值为4?

我个人的理解是因为token占1个字节、offset占2个字节,只有匹配值大于3的时候才有可能起到压缩效果。注:为什么是“有可能”呢,因为压缩算法是基于概率的,比如上面的例子并没有起到压缩效果,反而多占一个字节。

问题二:为什么最后的5个字节按照字面量直接存储?

我个人的理解是假设给定9个字节的字符串abcdabcde,按照正常流程压缩时格式如下:(0b01000000)_(abcd)_(4)------(0b00010000)_(e),同样占了9个字节,没有起到压缩效果。注意(4)是占2个字节的。

有兴趣的可以对着lucene的LZ4源码,照着上面的例子验证一下,本人已经测试过了。

 

展开阅读全文
LZ4
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部