公号:码农充电站pro

主页:https://codeshellme.github.io

1,倒排索引

倒排索引是一种数据结构,经常用在搜索引擎的实现中,用于快速找到某个单词所在的文档。

倒排索引会记录一个单词词典(Term Dictionary)和一个倒排列表

  • 单词词典:包含了所有文档包含的所有 Term。
  • 倒排列表:由一系列的倒排索引项组成,每个倒排索引项包含 4 项内容,分别是:
    • 文档 ID
    • 词频 TF:Term 在文档中出现的次数,用于相关性评分。
    • 位置 Position:Term 在文档中出现的位置,用于语句搜索。
    • 偏移 Offset:记录单词的开始结束位置,用于实现高亮显示。

假设我们有 3 篇文档:

文档 ID 文档内容
1 hello world
2 hello Java
3 hello elasticsearch

上面表格记录的是一种正向关系,叫做正排索引

倒排索引记录的是一种反向关系,如下:

Term 文档 ID 词频 TF Position Offset
hello 1 1 0 <0, 5>
hello 2 1 0 <0, 5>
hello 3 1 0 <0, 5>
world 1 1 1 <6, 5>
Java 2 1 1 <6, 4>
elasticsearch 3 1 1 <6, 19>

ES 默认会对所有文档的所有字段建立倒排索引;也可以通过设置不对某些字段建立倒排索引,优点是节省空间,缺点是这些字段的内容无法被搜索。

2,搜索相关性

搜索相关性用于描述文档搜索字符串的匹配程度(ES 会计算出一个评分),目的是为文档进行排序,从而将最符合用户需求的文档排在前面。

搜索相关性算法有 TF-IDF 算法和 BM25 算法。

文章 《朴素贝叶斯分类-实战篇》中介绍到了 TF-IDF 算法,可作为参考。

BM25TF-IDF 的比较:

在这里插入图片描述

当 TF 无限增加的时候,BM25 算分会趋向于一个数值,而不是(像 TF-IDF 一样)无限增长。

ES 5 之前,默认使用的是 TF-IDF 算法;在 ES 5 之后,默认使用的是 BM 25 算法。

3,一个搜索过程

下图展示了一个搜索过程:

在这里插入图片描述

当用户向搜索引擎发送一个搜索请求的时候,搜索引擎经过了以下步骤:

  1. 分词器对搜索字符串进行分词处理。
  2. 在倒排索引表中查到匹配的文档。
  3. 对每个匹配的文档进行相关性评分。
  4. 根据相关性评分对文档进行排序。
  5. 将排好序的文档返回给用户。