首页 > 其他 > 详细

从ElasticSearch和倒排索引所想到的

时间:2020-12-19 18:13:06      阅读:33      评论:0      收藏:0      [点我收藏+]

 

搜索引擎

分为

全文搜索,如百度谷歌

和垂直搜索,如易车,电商,OA

搜索引擎要求

快,要求:1.高校的压缩算法   2.快速的编码和解码能力

准(相关度),ES在7.0版本前默认相关度算法是TF-IDF,之后是BM25算法

召回率

查询与检索的区别

查询结果有就返回,没有就返回没有

检索,没有就返回接近的结果

倒排索引

分为倒排表postingList,存储int型不重复数据,使用HOR压缩算法,和RBM算法

term dic

term index

算法原理

一个int类型占4字节,100万数据量就占400万字节。按照二进制来存储,1字节32位,可存储[0,2的31次方-1)的数据。

根据这100万数据,会生成一个detailList,最高压缩32倍

这里举例:

比如一个很多数据的postingList,6个数字为4字节*6为24字节

对此生成一个detailList,每个数字大小占用采用8bit,即2的8次方

对detalList进行拆分,如一个数组每个数字用8bit来存储(2个数字为1byte*2为2字节+数组索引大小1字节),另一个数组每个数字用5bit来存储(4个数字为20bit为3字节+数字索引大小1字节)

但是这里数组有局限性,如果数据比较稀疏,即deltasList仍然是比较大的数字,这时可以用RBM算法

RBM算法(Roaring BitMap)

先把数换成二进制数,把这个数的前16位(高16位)和低16位进行拆分,再分别转化为十进制数.

如196658,高位十进制数3,低位十进制数50

对原始数组的每个元素,除以65536,把原数组每一个比较大的数字,分为高位和低位两个小数字

bitMap是如何存数据的

比如7 6 5 4 3 2 1 0,对应1字节,对应二进制位上有这个数字就标为1,也就是1字节可以存8个数字。

依次,65536个bit,对应6535  65534 .。。。。。0

从ElasticSearch和倒排索引所想到的

原文:https://www.cnblogs.com/powerZhangFly/p/14160160.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!