且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

为什么倒排索引不采用zlib这样的字典压缩算法——因为没法直接使用啊

更新时间:2022-09-16 21:48:30

看了下压缩算法的发展历史,根据倒排索引的数据结构特点,个人认为zstd不适合做倒排索引压缩,举例说明下:

假设有一份文档倒排列表为:[300, 302, 303, 332],对于这组倒排数据,是没法***直接***采用zstd这类字典压缩算法的,因为里面没有重复数据(字典压缩通常重复数据较多,例如一个重复单词较多的txt文档适合zstd字典压缩)。

但是,如果对他们做差值运算后变为[300, 2, 1, 29],实际上你会发现2,1,29这些数字比原始数据小得多而可以用更少的位数来存储。这就是目前倒排索引使用的压缩算法原理。

 

综上所述,es里原始数据其实比较适合zstd算法,但是由于其内置了Lz4,替换的价值不大。

补充:

 

(1)压缩算法的发展历史(见:http://blog.csdn.net/kimylrong/article/details/39405981 ),压缩算法的分类如下:

Lossless

 

Entropy type

 

 

Dictionary type

 

Other types

 

其中,熵编码方法是倒排索引压缩普遍采用的算法,例如上面标红的golomb或者Shannon–Fano–Elias算法,而字典压缩是一般性数据的压缩。

 

(2)倒排索引压缩的算法历史(见:http://www.cnblogs.com/bonelee/p/6879663.html )















本文转自张昺华-sky博客园博客,原文链接:http://www.cnblogs.com/bonelee/p/6904052.html,如需转载请自行联系原作者