• 欢迎使用千万蜘蛛池,网站外链优化,蜘蛛池引蜘蛛快速提高网站收录,收藏快捷键 CTRL + D

百度检索数量在哪看啊(百度一下)


使用百度文心一格生成的图

在正式介绍倒排索引之前,先看一个问题吧!请列出一句或多句包含 的古诗词

正常情况下,没有经过特别训练,一下就能想出有点难度。

那么我给点提示呢, 王维的《使至塞上》 苏轼的《水调歌头》 ,或许你稍微想一下,就能知道答案了!



这种通过作者和题目就能想到古诗句,这种我们称之为正向索引。正向索引应用广泛,能在海量的数据中精确定位到你想要的数据。

那么通过指定关键字来搜寻古诗词句,如果用正向索引,他的效率就会很低下,那么有没有一种有效的方案策略呢?我们使用的百度搜索,他们是怎么做到的呢?答案就是今天要展开的 倒排索引

还是借用上面的问题,我们将古诗词句进行关键字拆分并存储

大漠孤烟直,长河落日圆 ,我可以拆分成几个关键字 圆、直

人有悲欢离合,月有阴晴圆缺,此事古难全 可以拆成几个关键字, 圆、月



那么回到问题的开始,请列出一句或多句包含 的古诗词,那么你是不是可以使用关键字圆进行检索,然后检索到了对应的古诗词编号1和2,然后使用正向索引,一下就能找到对应的古诗词句。

这个就是倒排索引的妙用。倒排索引创建的过程大致包含四个步骤。

第一,切词 ,顾名思义就是将一整句话拆分成几个关键词,怎么拆你可以不用管,因为已经有很多成熟的分词器了,使用不同的分词器效果有所不同

第二,规范化 ,规范化就是去掉一些语气词,统一大小写、去分词。比如CAR、car这两个是同一个词,会统一规范,还比如中文中 的地得 等词,没有特殊含义,会直接去掉,比如have、had、having,这三个词本身也是同一个词,会统一规范

第三,去重 ,也就是这个关键字不会重复

第四,字典化 ,这个也很简单,就是格式化存储。


那么倒排索引有什么问题吗?我认为最主要的问题就是切词后数据量倍增增加,比如 大漠孤烟直,长河落日圆 ,实际情况下,我可能需要拆分成 圆、直、大漠、烟、落日 等,相当于这一条数据,我需要创建的字典就有5条明细。

这个对于存储来说是一件不可控的事情!那么,官方有没有解决方案呢?

既然倒排索引使用广泛,那肯定是有方案解决的,答案就是 数据压缩。

倒排索引分为三部分,倒排表(Posting List)、词项字典(term dictionary)、词项索引(term index),上图中的关键字就是词项字典,对应的古诗词编号就是倒排表,这里我们只讨论倒排表的数据压缩。

倒排表的数据压缩算法有两种,FOR(Frame Of Reference)算法和RBM算法(RoaringBitMap),因为篇幅原因,这里先介绍FOR压缩算法。

词项字典中的数据是一个int数组,并且是已经排序好的。我们都知道int是占用4个字节来存储数据的,1Byte=8bit,也就是一个int数字需要占4*8=32个bit,也就是32个二进制位,去掉首位表示符号位,int最大值是2^31

从网上扒来一张图,来很好的说明这个压缩算法

原始数组是[73,300,302,332,343,372],不使用压缩算法,就是6*4Byte=24Byte

使用FOR算法的步骤如下

第一步,将数组的每一项减去前一项,得到一个新数组[73,227,2,30,11,29],用这个新数组也能很快的复原原始数组

第二步,将数据分组,这里将73,227,2前三个数据分为一组,后三个30,11,29数据分为一组

第三步,压缩。可以看到前三个数据中最大的是227,小于2的8次幂256,说明可以定义一种新的数据类型,这个类型用8个bit来表示一个数字,累计就是8*3=24bit为3Byte,再加上定义这个新的数据类型需要一个Byte,也就是前三个数据需要4Byte,同理后面三个数字需要用3Byte,压缩后整个数组就是需要7Byte,相比不压缩的24Byte,存储空间下降了70.83%

可以看到,使用这个压缩算法,在数据分布比较均匀的情况下,压缩比率是惊人的。但假如数据分布不均匀,前后的数字相差依然很大,这种数据分布使用FOR压缩算法效果就不明显了,这种情况下,就需要使用RBM了。

RBM算法的介绍,将放在下一篇,未完待续!

本文链接:https://www.24zzc.com/news/169493305335626.html

相关文章推荐

    无相关信息