检索技术

合理地组织数据的存储可以提高检索效率。检索的核心思路,其实就是通过合理组织数据,尽可能地快速减少查询范围

线性结构检索

链表与数组就是线性结构检索的代表

非线性结构检索

树与跳表是这种结构的代表

哈希检索

状态检索

倒排索引

全文检索:

DocIdDoc
1谷歌地图之父跳槽 Facebook
2谷歌地图之父加盟 Facebook
3谷歌地图创始人拉斯离开谷歌加盟 Facebook
4谷歌地图之父跳槽 Facebook 与 Wave 项目取消有关
5谷歌地图之父拉斯加盟社交网站 Facebook

对这些doc进行分词之后,以词为主键,记录哪些doc出现了这些词

WordIdWordDocIds
1谷歌1,2,3,4,5
2地图1,2,3,4,5
3之父1,2,4,5
4跳槽1,4
5Facebook1,2,3,4,5
6加盟2,3,5
7创始人3
8拉斯3,5
9离开3
104
......

跳表法加速倒排索引:使用跳表存储文档列表,主要对搜索结果集合运算时进行加速

跳表加速

哈希表法加速倒排索引:当两个集合要求交集时,如果一个集合特别大,另一个集合相对比较小,那我们就可以用哈希表来存储大集合。这样,我们就可以拿着小集合中的每一个元素去哈希表中对比

位图法加速倒排索引:

2022112220367

升级版位图:Roaring Bitmap:为了解决传统位图的空间消耗问题:

Roaring Bitmap

要确认一个元素是否在 Roaring Bitmap 中存在,通过两次查找就能确认了。第一步是以高 16 位在有序数组中二分查找,看对应的桶是否存在。如果存在,第二步就是将桶中的位图取出,拿着低 16 位在位图中查找,判断相应位置是否为 1

对联合查询加速:

1. 对表达式进行变换减少运算次数

  1. 使用多路归并,利用跳表的性质,快速跳过多个元素,加快多路归并的效率
  2. 预先组合法:提前计算好某些查询的结果,需要时直接返回
  3. 缓存

中间件

目前开源可用的全文检索中间件只有ElasticSearch与Solr 二者都是基于Lucene

Lucene

ES在许多方面都超过了Solr 所以目前只能选择ES

数据库检索

索引和数据分离:能将索引的数组大小保持在一个较小的范围内,让它能加载在内存中,这样就能减少对磁盘的访问

NoSQL检索

大规模索引构建

索引创建

20221123171130

2022112317120

索引查询

对于能加载到内存中的文档列表,这没什么问题

但如果某些热词对应的文档列表过大,则需要利用磁盘索引数据结构,进行分层加载

索引更新

Double Buffer

为了避免读写竞争问题,可以在内存中同时保存两份一样的索引,一个是索引 A,一个是索引 B。我们会使用一个指针 p 指向索引 A,表示索引 A 是当前可访问的索引。那么用户在访问时就会通过指针 p 去访问索引 A。这个时候,如果我们要更新,只更新索引 B,当两份数据进行切换时,可以通过简单的原子操作修改引用即可

全量索引结合增量索引

系统会周期性地处理全部的数据,生成一份完整的索引,也就是全量索引。这个索引不可以被实时修改,对于要更新的索引,在内存构建一份增量索引,当查询发生的时候,会同时查询全量索引和增量索引,将合并的结果作为总的结果输出

将增量索引合并到全量索引中的常见方法有 3 种:

  1. 完全重建法:在增量索引写满内存空间之前,完全重建一次全量索引,然后将系统查询切换到新的全量索引上
  2. 再合并法:对增量索引与全量索引进行归并
  3. 滚动合并法:当内存中的增量索引增长到一定体量时,先合并到天级索引,天级索引量够了,再合并到月级索引,以此类推

滚动合并

索引拆分

基本原理跟分库分表是一样的

文档搜索排序

TF-IDF 算法

相关性 = TF*IDF

TF 是词频(Term Frequency),IDF 是逆文档频率(Inverse Document Frequency)

BM25 算法

它认为词频和相关性的关系并不是线性的。也就是说,随着词频的增加,相关性的增加会越来越不明显,并且还会有一个阈值上限

PageRank

将所有的网页视作节点(node),而将超链接视作边(edge)。每个节点的权重值表示对应的页面的重要度。通向该网页的超链接称做“对该网页的投票(a vote of support)”。每个网页的权重值大小被递归地定义,依托于所有链接该页面的页面的权重值

逻辑回归模型

把不同的打分因子进行加权求和

Score = w1 * x1 + w2 * x2 + w3 * x3 + …… + wn * xn

非精准TOPK检索

  1. 根据静态质量得分排序截断:需要将每个词对应的文档列表按分数排序,在查询时进行归并并返回前K个
  2. 根据词频得分排序截断:文档列表按词频排序
    1. 一个问题就是词频相同如何排序,一个解决办法就是胜者表:根据某种权重将文档列表中的元素进行排序,并提前截取 r 个最优结果,但这种方式有可能造成没法取得足够的K个文档,造成检索结果的丢失
  3. 分层索引:先离线给所有文档完成打分,然后将得分最高的 m 个文档作为高分文档,单独建立一个高质量索引,其他的文档则作为低质量索引
    1. 查询时,如果高质量索引中的检索结果不足 k 个,那我们再去低质量索引中查询,补全到 k 个结果

空间检索

模糊查询TOPK

先将经纬度转换为一个固定的区域,查询时只对这个区域内的数据进行距离计算

这种非精准检索的方案,会带来一定的误差,找到的只是这个区域内距离最近的,而非实际距离最近的

精确查询TOPK

区域粒度过粗,就会有上面的那个问题,如果是较细粒度的区域划分,则可以对当前区域周边的8个方位都发起查询,这样就精确了

Geohash 编码

2022112417926

使用 GeoHash 编码后,相当于把整个地理空间划分成了一个个方格,每个方格对应了 GeoHash 中的一个分区

字符长度和覆盖区域对照表:

Geohash编码长度宽度高度
15009.4km4992.6km
21252.3km624.1km
3156.5km156km
439.1km19.5km
54.9km4.9km
61.2km609.4m
7152.9m152.4m
838.2m19m
94.8m4.8m
101.2m59.5cm
1114.9cm14.9cm
123.7cm1.9cm

最近精确查询

先获得当前位置的 GeoHash 编码,然后根据需求不停扩大查询范围进行多次查询,最后合并查询结果

在检索完 wx4g6yc8 这个区域编码以后,如果结果数量不够,还要检索 wx4g6yc 这个更大范围的区域编码,我们只要将查询改写为“查找区域编码在 wx4g6yc0 至 wx4g6ycz 之间的元素”,就可以利用同一个索引,来完成更高一个层级的区域查询了

20221124173335

这个时候需要引入四叉树,就可以逐层地往外找

20221124173654

另外一种查询方式是前缀树:

2022112417406

当我们查询 wx4g6yc8 这个区域时,我们会沿着 w-x-4-g-6-y-c-8 的路径,检索到对应的叶子节点,然后取出这个叶子节点上存储的数据。如果这个区域的数据不足 k 个,就返回到父节点上,检索对应的区域,直到返回结果达到 k 个为止

近似最近邻检索

局部敏感哈希

20221125162855

如果连续做了 n 次这样的随机划分,这两个点每次都在同一边,那就可以认为它们在很大概率上是相近的

实际上,在利用局部敏感哈希值来判断文章相似性的时候,会以表示比特位差异数的海明距离(Hamming Distance)为标准,即比特位数的差异数

SimHash

  1. 选择一个能将关键词映射到 64 位正整数的普通哈希函数
  2. 使用该哈希函数给文档中的每个关键词生成一个 64 位的哈希值,并将该哈希值中的 0 修改为 -1。比如说,关键词 A 的哈希值编码为 <1,0,1,1,0>,那我们做完转换以后,编码就变成了 <1,-1,1,1,-1>
  3. 将关键词的编码乘上关键词自己的权重。如果关键词编码为 <1,-1,1,1,-1>,关键词的权重为 2,最后我们得到的关键词编码就变成了 <2,-2,2,2,-2>
  4. 将所有关键词的编码按位相加,合成一个编码如果两个关键词的编码分别为 <2,-2,2,2,-2> 和 <3,3,-3,3,3>,那它们相加以后就会得到 <5,1,-1,5,1>
  5. 将最终得到的编码中大于 0 的值变为 1,小于等于 0 的变为 0。这样,编码 <5,1,-1,5, 1> 就会被转换为 <1,1,0,1,1>

相似检索

将所有的文档根据自己每个比特位的值,加入到对应的倒排索引的 posting list 中,当需要查询与该文档相似的其他文档时:

  1. 计算出待查询文档的 SimHash 值
  2. 以该 SimHash 值中每个比特位的值作为 Key,去倒排索引中查询,将相同位置具有相同值的文档都召回
  3. 合并这些文档,并一一判断它们和要查询的文档之间的海明距离是否在 3 之内,留下满足条件的

只要有一个比特位的值相同,文档就会被召回。也就是说,这个方案和遍历所有文档相比,其实只能排除掉“比特位完全不同的文档”,一种优化是Google 的抽屉原理:

如果海明距离小于3,那么4段中至少有一段完全相同

将每一个文档都根据比特位划分为 4 段,以每一段的 16 个比特位的值作为 Key,建立 4 个倒排索引。检索的时候,我们会把要查询文档的 SimHash 值也分为 4 段,然后分别去对应的倒排索引中,查询和自己这一段比特位完全相同的文档。最后,将返回的四个 posting list 合并,并一一判断它们的的海明距离是否在 3 之内

乘积量化

量化指的就是将一个空间划分为多个区域,然后为每个区域编码标识,乘积指的是高维空间可以看作是由多个低维空间相乘得到的

乘积量化其实就是将向量的高维空间看成是多个子空间的乘积,然后针对每个子空间,再用聚类技术分成多个区域。最后,给每个区域生成一个唯一编码,也就是聚类 ID

获得全部查询子向量和样本子向量近似距离的过程

对乘积量化进行倒排索引:

一个样本向量加入倒排索引的过程

查询向量查询倒排索引的过程