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

简介:

看了下压缩算法的发展历史,根据倒排索引的数据结构特点,个人认为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,如需转载请自行联系原作者


相关文章
|
2月前
|
算法 JavaScript Java
【状态压缩】【动态规划】【C++算法】1125.最小的必要团队
【状态压缩】【动态规划】【C++算法】1125.最小的必要团队
|
2月前
|
算法 测试技术 C++
【动态规划】【状态压缩】【C++算法】1815 得到新鲜甜甜圈的最多组数
【动态规划】【状态压缩】【C++算法】1815 得到新鲜甜甜圈的最多组数
|
3月前
|
算法 测试技术 C#
【状态压缩】【动态规划】【C++算法】691贴纸拼词
【状态压缩】【动态规划】【C++算法】691贴纸拼词
|
5月前
|
存储 算法 NoSQL
Zstandard (zstd)压缩算法在JAVA上的使用
Zstandard (zstd)压缩算法在JAVA上的使用
264 0
|
6月前
|
算法
【每日挠头算法题(2)】压缩字符串|仅执行一次字符串交换能否使两个字符串相等
【每日挠头算法题(2)】压缩字符串|仅执行一次字符串交换能否使两个字符串相等
|
2月前
|
算法 测试技术 C++
【状态压缩】【动态规划】【C++算法】691贴纸拼词
【状态压缩】【动态规划】【C++算法】691贴纸拼词
|
3月前
|
SQL 存储 编解码
Hive中的压缩技术是如何实现的?请解释其原理和常用压缩算法。
Hive中的压缩技术是如何实现的?请解释其原理和常用压缩算法。
28 0
|
4月前
|
存储 设计模式 算法
【数据结构和算法】压缩字符串
给你一个字符数组chars,请使用下述算法压缩: 从一个空字符串s开始。对于chars中的每组连续重复字符: 如果这一组长度为1,则将字符追加到s中。 否则,需要向s追加字符,后跟这一组的长度。 压缩后得到的字符串s不应该直接返回,需要转储到字符数组chars中。需要注意的是,如果组长度为10或10以上,则在chars数组中会被拆分为多个字符。 请在修改完输入数组后,返回该数组的新长度。
65 1
|
4月前
|
存储 分布式计算 算法
MapReduce计数器,Tash的运行机制,shuffle过程,压缩算法
MapReduce计数器,Tash的运行机制,shuffle过程,压缩算法
21 0
|
4月前
|
消息中间件 存储 算法
【云计算与大数据技术】数据编码LZSS算法、Snappy压缩库及分布式通信系统的讲解(图文解释 超详细)
【云计算与大数据技术】数据编码LZSS算法、Snappy压缩库及分布式通信系统的讲解(图文解释 超详细)
78 0