侧边栏壁纸
博主头像
孔子说JAVA博主等级

成功只是一只沦落在鸡窝里的鹰,成功永远属于自信且有毅力的人!

  • 累计撰写 352 篇文章
  • 累计创建 135 个标签
  • 累计收到 10 条评论

目 录CONTENT

文章目录

ES教程15-ElasticSearch倒排索引原理及示例

孔子说JAVA
2022-10-20 / 0 评论 / 0 点赞 / 56 阅读 / 5,442 字 / 正在检测是否收录...
广告 广告

倒排索引(Inverted Index)也叫反向索引,通俗来讲正向索引是通过key找value,反向索引则是通过value找key。传统的检索方式是通过文章,逐个遍历找到对应关键词的位置。倒排索引则是通过分词策略,形成了词和文章的映射关系表,也称倒排表,这种词典 + 映射表即为倒排索引。其中词典中存储词元,倒排表中存储该词元在哪些文中出现的位置。有了倒排索引,就能实现 O(1) 时间复杂度的效率检索文章了,极大的提高了检索效率。

  • 倒排索引的底层实现是基于:FST(Finite State Transducer)有限状态转移器 数据结构。

1、正排索引与倒排索引概念

正排索引:文档ID到文档内容和单词的关联
倒排索引:单词到文档ID的关系

  • 备注:ES对文档每个字段都有自己的倒排索引,可以指定某些字段不做索引,这样可以节省存储空间,缺点是这个字段无法被搜索。

1.1 正排索引

在搜索引擎中每个文件都会分配一个对应的文件ID,文件内容被表示为一系列关键词的集合(实际上在搜索引擎库中,关键词也已经转换为关键词ID)。例如:文档1 经过分词,提取出了十个关键词,每个关键词都会记录他在文档中出现的次数以及出现的位置,这样就得到了正向索引:

  • 文档1 的ID —> 关键词1(出现的次数、位置);关键词2(出现的次数、位置);…
  • 文档2 的ID —> 关键词1(出现的次数、位置);关键词2(出现的次数、位置);…

123124

查找的时候一般都是通过key去找value。如用户在网页上搜索关键词“小米手机”时,假设只存在正向索引(forward index),那么就需要扫描索引库中的所有文档,从中找出包含关键词“小米手机”的所有文档,再通过打分模型进行打分排名,并最终呈现给用户。因为互联网上收录在搜索引擎中的文档数量是个天文数字,这样的索引结构性能太低,根本无法满足实时返回排名结果的要求。

1.2 倒排索引

为了解决海量数据条件下正排索引性能低下的问题,搜索引擎会将正排索引重新构建为倒排索引,即把文件ID对应到关键词的映射转换为关键词到文件ID的映射,这样每个关键词会都对应着一系列的文件,这些文件中都出现了这个关键词。倒排索引即将正排索引的key/value进行了互换。倒排索引的结构如下:

  • 关键词1:文档1 的ID,文档2 的ID,…………
  • 关键词2:带有此关键词的文档ID列表

123125

这样搜索引擎在查找某个关键词时,可以根据倒排索引快速定位到相关文档。

倒排索引不可变性:倒排索引采用Immutable Design,一旦生成,不可更改。

1.3 倒排索引优缺点

倒排索引优点

  • 无需考虑并发写文件的问题,避免了锁机制带来的性能问题。
  • 一旦读入内核的文件系统缓存,便留在那里。只要文件系统存有足够大的空间。大部分请求就会直接请求内存,不会命中磁盘,极大提升了查询性能。

倒排索引缺点

倒排索引的不可变性也带来了另一个挑战,如果需要让一个新的文档可以被索引,需要重建整个索引。

1.4 单词文档矩阵

单词-文档矩阵是表达两者之间的一种互相包含关系的概念模型,每列代表一个文档,每行代表一个单词,打对勾的位置代表包含关系。

image-1666056239901

从纵向(即文档)维度看,每列代表该文档包含了哪些关键词,如图所示:文档1包含了词汇1和词汇4,而不包含其它单词。从横向(即单词)维度来看,每行代表了某个单词被哪些文档包含,如图所示:对于词汇1来说,在文档1和文档4中出现过,而在其它文档中不包含。

搜索引擎的索引就是实现了“单词-文档矩阵”的具体数据结构。实现上述概念模型可以有不同的方式,比如“倒排索引”、“签名文件”、“后缀树”等方式,但是通过各项实验数据表明,“倒排索引”是实现单词到文档映射关系的最佳实现方式。

2、基本概念

image-1666056649651

文档(Document):搜索引擎一般的处理对象是互联网网页,而文档概念更宽泛些,代表以文本形式存在的存储对象,相比网页来说,涵盖更多形式,如Word, PDF, JSON, HTML,XML等不同格式的文件都可以称之为文档。再比如一条短信,一封邮件,一条微博也可以称之为文档。很多情况下我们会使用文档来表征文本信息。

文档集合(Document Collection):由若干文档构成的集合称为文档集合。比如海量的互联网网页或者说大量的电子邮件都是文档集合的具体例子。

文档编号(Document ID):在搜索引擎内部,会将文档集合内每个文档均赋予一个唯一的内部编号,称之为“文档编号”。此编号作为这个文档的唯一标识,以方便内部处理,后文有时会用 DocID 来便捷地代表文档编号。

单词编号(Word ID):与文档编号类似,搜索引擎内部以唯一的编号来表征某个单词。

倒排索引(Inverted Index):倒排索引是实现“单词-文档矩阵”的一种具体数据结构,通过倒排索引,可以根据单词快速获取包含这个单词的文档列表。倒排索引主要包括两个部分:“单词词典”和“倒排文件”。

单词词典(Lexicon):搜索引擎的索引单位通常是单词,单词词典是由文档集合中出现过的所有单词构成的字符串集合,单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。

倒排列表(Posting List):倒排列表记录了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息,每条记录称为一个倒排项(Posting)。根据倒排列表,即可获知哪些文档包含某个单词。

倒排文件(Inverted File):所有单词的倒排列表往往顺序地存储在磁盘的某个文件里,这个文件即被称之为倒排文件,倒排文件是存储倒排索引的物理文件。

term:在 ES 中,关键词被称为term。

Term Dictionary:Elasticsearch为了能快速找到某个term,将所有的term排个序,二分法查找term,logN的查找效率,就像通过字典查找一样,这就是Term Dictionary。和传统数据库通过B-Tree的方式类似,但比B-Tree的查询快。

Term Index:B-Tree通过减少磁盘寻道次数来提高查询性能,Elasticsearch也是采用同样的思路,直接通过内存查找term,不读磁盘,但是如果term太多,term dictionary也会很大,放内存不现实,于是有了Term Index,就像字典里的索引页一样,A开头的有哪些term,分别在哪页,可以理解term index是一颗树。

image-1666057594928

这棵树不会包含所有的term,它包含的是term的一些前缀。通过term index可以快速地定位到term dictionary的某个offset,然后从这个位置再往后顺序查找。

image-1666057621233

所以term index不需要存下所有的term,而仅仅是他们的一些前缀与Term Dictionary的block之间的映射关系,再结合FST(Finite State Transducers)的压缩技术,可以使term index缓存到内存中。从term index查到对应的term dictionary的block位置之后,再去磁盘上找term,大大减少了磁盘随机读的次数。

3、数据结构

3.1 单词词典

单词词典是倒排索引中非常重要的组成部分,主要用来维护在文档集合中出现过的所有单词的相关信息,同时用来记录某个单词对应的倒排列表在倒排文件中的位置信息。在进行搜索时,根据用户的查询词,去单词词典里查询,就能够获得相应的倒排列表,并以此作为后续排序的基础。

对于一个规模庞大的文档集合来说,可能包含几十万甚至上百万的不同单词,能否快速定位到某个单词,将直接影响搜索时的响应速度。我们需要高效的数据结构对单词词典进行构建和查找,常用的数据结构包括 哈希+链表结构树形词典结构

3.2 哈希 + 链表

image-1666060904195

上图是哈希+链表这种词典结构的示意图,主要由两个部分构成:

  • 主体部分是哈希表,每个哈希表项会保存一个指针,该指针指向冲突链表。
  • 在冲突链表里,具有相同哈希值的单词形成链表结构。之所以会有冲突链表,是因为两个不同单词经过计算获得了相同的哈希值,即发生了哈希冲突,解决办法就是将相同哈希值的单词存储在链表里,以供后续查找。

建立索引的过程

在建立索引的过程中,词典结构也会相应地被构建出来。比如在解析一个新文档的时候,对于某个在文档中出现的单词T,首先利用哈希函数获得其哈希值,然后根据哈希值对应的哈希表项读取其中保存的指针,从而找到对应的冲突链表。如果冲突链表里已经存在这个单词,说明单词在之前解析的文档里已经出现过。如果在冲突链表里没有发现这个单词,说明该单词是首次碰到,则将其加入冲突链表里。通过这种方式,当文档集合内所有文档解析完毕时,相应的词典结构也就建立起来了。

使用索引的过程

在响应用户查询请求时,其过程与建立词典类似,不同点在于即使词典里没出现过某个单词,也不会添加到词典内。假设用户输入的查询请求为单词3,对这个单词进行哈希,定位到哈希表内的2号槽,从其保留的指针可以获得冲突链表,依次将单词3和冲突链表内的单词比较,发现单词3在冲突链表内,于是找到这个单词,之后可以读出这个单词对应的倒排列表来进行后续的工作,如果没有找到这个单词,说明文档集合内没有任何文档包含单词,则搜索结果为空。

3.3 树形词典结构

B树(或者B+树)是另外一种高效查找结构,下图是一个 B树结构示意图。B树与哈希方式查找不同,需要字典项能够按照大小排序(数字或者字符序),而哈希方式则无须数据满足此项要求。

B树形成了层级查找结构,中间节点用于指出一定顺序范围的词典项目存储在哪个子树中,起到根据词典项比较大小进行导航的作用,最底层的叶子节点存储单词的地址信息,根据这个地址就可以提取出单词字符串。

image-1666061384564

4、倒排索引实例讲解

倒排索引从逻辑结构和基本思路上来讲非常简单。下面通过具体实例来进行说明:假设文档集合包含五个文档,每个文档内容如下图所示,在图中最左端一栏是每个文档对应的文档编号。现在的任务就是对这个文档集合建立倒排索引。

image-1666059655816

在实例讲解过程中会出现的相关名词:

  • 单词ID:记录每个单词的单词编号;
  • 单词:对应的单词;
  • 文档频率:代表文档集合中有多少个文档包含某个单词
  • 倒排列表:包含单词ID及其他必要信息
  • DocId:单词出现的文档id
  • TF:单词在某个文档中出现的次数
  • POS:单词在文档中出现的位置

4.1 最简单的倒排索引

中文和英文等语言不同,单词之间没有明确分隔符,所以首先要用分词系统将文档自动切分为单词序列,这样每个文档就转换为由单词序列构成的数据流,为了系统后续处理方便,需要对每个不同的单词赋予唯一的单词编号,同时记录下哪些文档包含这个单词,在如此处理结束后,我们可以得到最简单的倒排索引,如下图。

image-1666059772021

在上图中,“单词ID”一栏记录了每个单词的编号,第二栏是单词编号对应的单词,第三栏是每个单词对应的倒排列表。如单词“谷歌”的单词编号为1,倒排列表为{1,2,3,4,5},说明文档集合中每个文档都包含了这个单词。单词“跳槽”的单词编号为4,倒排列表为{1,4},说明文档集合中1、4文档包含了这个单词。

4.2 增加了词频的倒排索引

前述倒排索引是最简单的,在这个索引系统中只记载了某个单词被哪些文档所包含,实际上,索引系统还可以记录更多信息。下图就是一个相对复杂些的倒排索引,与上图的基本索引系统比,在单词对应的倒排列表中不仅记录了文档编号,还记载了单词频率信息(TF),即这个单词在某个文档中的出现次数,之所以要记录这个信息,是因为词频信息在搜索结果排序时,计算查询和文档相似度是很重要的一个计算因子,所以将其记录在倒排列表中,以方便后续排序时进行分值计算。

image-1666060152944

在上图中,单词“创始人”的单词编号为7,对应的倒排列表内容为:(3;1),其中的3代表文档编号为3的文档包含这个单词,数字1代表词频信息,即这个单词在3号文档中只出现过1次。其它单词对应的倒排列表所代表含义与此相同。

4.3 更丰富的倒排索引

实用的倒排索引还可以记载更多的信息,下图所示索引系统除了记录文档编号和单词频率信息外,还额外记载了两类信息,即每个单词对应的“文档频率信息”,在倒排列表中记录单词在某个文档出现的位置信息。

image-1666060299152

  • “文档频率”代表了在文档集合中有多少个文档包含某个单词,记录这个信息的原因与单词频率是一样的,这个信息在搜索结果排序计算中也是非常重要的一个因子。
  • “单词在某个文档中出现的位置信息”并非是索引系统一定要记录的,在实际的索引系统里可以包含,也可以不包含,因为这个信息对于搜索系统来说并非必需的,位置信息只有在支持“短语查询”的时候才能够派上用场。

以单词“拉斯”为例,其单词编号为8,文档频率为2,代表了整个文档集合中有两个文档包含了这个单词,对应的倒排列表为:{(3;1;<4>),(5;1;<4>)},其表示在文档3和文档5中出现过这个单词,单词频率都为1,单词“拉斯”在两个文档中的出现位置都是4,即文档中第四个单词是“拉斯”。

上图的倒排索引已经是一个非常完备的索引系统,实际搜索系统的索引结构基本如此,区别无非是采取哪些具体的数据结构来实现上述逻辑结构。

有了这个索引系统,搜索引擎可以很方便地响应用户的查询,比如用户输入查询词“Facebook”,搜索系统查找倒排索引,从中可以读出包含这个单词的文档,这些文档就是提供给用户的搜索结果,而利用单词频率信息、文档频率信息即可以对这些候选搜索结果进行排序,计算文档和查询的相似性,按照相似性得分由高到低排序输出,此即为搜索系统的部分内部流程。

0

评论区