倒排列表压缩算法汇总——分区Elias

  • 时间:
  • 浏览:1
  • 来源:彩神幸运飞艇_神彩幸运飞艇官方

要花费307年开始,并就有名为PForDelta的索引压缩算法开始引起更多人的重视,这是并就有压缩率更高否则解压波特率快一点 的算法。有研究表明,索引压缩的过程中相邻文档ID差值为1的情况汇报要花费占10%,而PForDelta算法对小差值的情况汇报,有点儿有优势。假定另另一十个 索引块为8个值(原因分析做过差分),30%的情况汇报下值小于32,小于32的值均可不都还能能 用另另一十个 b = 5bit的数来表示。建立那么 另另一十个 形态:8*b-bit的常规次要,看作是另另一十个 位数组,每个元素占b-bit定长空间,余下的为异常次要,看作是另另一十个 整形数组,每个元素占4字节定长空间。假定有那么 另另一十个 序列:23, 41, 8, 12, 30, 68, 18, 45,通过PForDelta辦法 的构造得到如下压缩形态:

来看看倒排索引压缩。压缩是拿CPU换IO的最重要手段之一,不论索引是插进硬盘还是内存中。索引压缩的算法有几十种,跟文本压缩不同,索引压缩算法不仅仅时要考虑压缩率,更要考虑压缩和解压性能,否则会解压太慢而起那么CPU换IO的作用。早期的索引设计里,在尝试了几十种编码过后,基本都挑选 性采用差分编码+可变长字节编码。差分的目的在于让索引的文档ID尽原因分析小,原因分析压缩小的整数经常比大整数更有效。在索引构建算法中,有一类工作叫做“文档重排”,目的只是通过对文档索引顺序的重新排列,使得索引posting list中的文档ID之差最小,那么 就可不都还能能 让压缩算法更有效的工作,从而使得索引总体积最小。当然那么 的工作在实际中价值有限,原因分析索引的构建波特率以及增量构建同样非常重要,耗费血块时间在文档重排上,对于静态数据集合才更加有效。可变长字节编码共否则我最早的索引压缩编码,思路简单到无以复加的地步——每个字节的第一位为flag,表示与非 继续使用下另另一十个 byte,剩下7位为有效位,所有的有效位组成数字的2进制表示。否则它却非常有效,原因分析解压波特率非常快。采用差分和可变长组合手段,假定文档ID采用32位整数,那么索引体积基本上可不都还能能 压缩到过后的1/2到1/4之间。这俩 压缩手段指在了主流,几乎所有的开源搜索(Lucene,Sphinx),商业搜索都采用这俩 辦法 进行,Google则引入了Group可变长字节编码,以另另一十个 整数为一组进行压缩,那么 压缩率更高。大伙儿可不都还能能 找到阿里实现的Group可变长字节编码的实现,否则很原因分析淘宝商品搜索也采用了这俩 辦法 。

Quasi-succinct索引在MG4J的开源搜索引擎中得到了应用,MG4J是本人认为的Java版本的开源搜索引擎中最具备研究和学习价值的,不仅仅在于高于Lucene的代码质量,更在于对于数据形态与算法孜孜不倦的创新。当然,原因分析不善宣传,出研究会校而并那么吸引更多的开发人员加入社区,

知晓并愿意改进MG4J的人寥寥无几,这跟Lucene形成了鲜明的对比。否则,即便在技术领域,先进性也往往让步于宣传。

Elias-Fano编码过程如下:把一组整数的最低l位连接在并肩,并肩把高位以严格单调增的排序划分为桶。用0表示桶的指在,用1表示桶里的元素,有有哪几个元素就有有哪几个个1。

转自:http://chuansong.me/n/2035211

创新依然在继续,自从SSE加速指令引入到PForDelta的实现过后,针对SIMD指令怎样设计良好的压缩算法也成为工程和学术的研究重点。亚马逊旗下搜索引擎A9.com就那么 提出了针对SIMD加速的可变长字节编码实现,而在2013年底,加拿大LICEF研究中心的Lemire提出了基于SIMD bitpacking的压缩编码SIMD-BP128,其解压波特率是迄今为止最快的,超过OptPFor的2倍(一秒钟可不都还能能 解压10亿整数),当然在压缩率上并那么达到高指标。

图中的序列为2,3,5,7,11,13,24,原因分析期望定位大于6的位置,那么根据6/2^2就可不都还能能 定位到大于6的桶,否则在桶内线性扫描即可。可不都还能能 看了,低l位的指在,只是起到了桶定位的用途,从而防止完整性解压,这可不都还能能 类比于常规索引中的跳跃表,跳跃间隔为2^l。

PForDelta及其系列改进从07年发明的故事家 以来原因分析逐渐心智心智性性早熟的句子的句子图片 图片 是什么是什么 图片 图片 图片 ,后边的工程实践中引入了SSE指令加速,使得解压波特率可不都还能能 快一点 。某些主流商业搜索引擎原因分析广泛采用,也含晒 后边提到的淘宝商品搜索。然而,技术革新的步伐并那么停止。PForDelta这俩 族算法,压缩是按照区块来进行的,这原因分析原因分析希望仅仅访问其中某另另一十个 元素,那么时要把整个区块进行解压。有过后大伙儿何必 希望经常完整性解压,从而可不都还能能 做到对压缩数字的随机读取。在2012年的过后,再次出现 了Quasi-succinct索引。它可不都还能能 提供元素的随机访问而不时要完整性解压。注意这里又再次出现 了succinct字样,原因分析该索引对于压缩接近信息熵的下界,这符合succinct的定义。Quasi-succinct索引的性能跟最好的区块压缩算法压缩解压性能基本一致,采用的是Elias-Fano编码,否则压缩率缺却何必 高,否则会原因索引体积膨胀——尽管那么,索引所占的体积仍然少于常规的可变长字节编码。Elias-Fano编码针对随机元素的解压非常快速,否则原因分析时要解压完整性元素,它的波特率还是那么最先进的批量解压算法例如于NewPFor和OptPFor快。

压缩可不都还能能 说是索引设计中的第一考虑次要,盘点后边的列表,NewPFor,OptPFor,Quasi-succinct(Elias-Fano),Partitioned Elias-Fano,SIMD-BP128,就有业界最先进的挑选 ,设计时时要根据本人的要求做出挑选 。

Partitioned(分区块) Elias-Fano编码,这篇文章获得了2014年SIGIR会议最佳论文,它是针对Elias-Fano编码进行的改进。仍然由Quasi-succinct的作者提出,主要防止Quasi-succinct索引的压缩率问题图片——回归区块压缩手段,把数字序列划分区块,每个区块内单独用Elias-Fano编码,并肩,为了确保仍然具备随机访问的形态,把区块的边界数字再次单独拿Elias-Fano编码压缩,否则形成了另另一十个 二级形态。根据作者的试验,分区Elias-Fano编码比最快的PForDelta编码OptPFor波特率和压缩率上均有超越,但压缩率大大超过后者(2倍以上)。否则,在随机访问,压缩率,解压性能上达到了很强的综合性能,荣膺最佳论文实至名归。

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

椭圆框所示的次要为常规次要,常规次要的第另另一十个 值1,表示从该地址开始,跳过另另一十个 地址,就可不都还能能 找到下另另一十个 异常值的位置,同理第另另一十个 值3表示,跳过十个 地址,只是下另另一十个 异常值的位置。常规值那么 到后存储,异常值从后向前存储。PForDelta压缩是基于块来进行,目前常用的挑选 是128。把防止异常值的辦法 做改进,采用可变长字节原因分析某些算法(目前最先进的是S9原因分析S16)压缩,只是改进型的NewPFor和OptPFor压缩算法。