Elasticsearch倒排索引原理

Elasticsearch倒排索引原理教程

Elasticsearch 使用一种称为倒排索引的结构,它适用于快速的全文搜索。一个倒排索引由文档中所有不重复词的列表构成,对于其中每个词,有一个包含它的文档列表。

在搜索引擎中每个文件都对应一个文件 ID,文件内容被表示为一系列关键词的集合(文档要除去一些无用的词,比如 ’的’ 这些,剩下的词就是关键词,每个关键词都有自己的 ID)。例如 “文档1” 经过分词,提取了 3 个关键词,每个关键词都会记录它所在在文档中的出现频率及出现位置。

正排索引

正排索引也称为 “前向索引”,它是创建倒排索引的基础。

这种组织方法在建立索引的时候结构比较简单,建立比较方便且易于维护;因为索引是基于文档建立的,若是有新的文档加入,直接为该文档建立一个新的索引块,挂接在原来索引文件的后面。若是有文档删除,则直接找到该文档号文档对应的索引信息,将其直接删除。

他适合根据文档 ID 来查询对应的内容。但是在查询一个 keyword 在哪些文档里包含的时候需对所有的文档进行扫描以确保没有遗漏,这样就使得检索时间大大延长,检索效率低下。

倒排索引详解

组成

倒排索引主要由单词词典(Term Dictionary)和倒排列表(Posting List)及倒排文件(Inverted File)组成。

图解

他们三者的关系如下图:

14_Elasticsearch倒排索引.png

单词词典

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

倒排列表

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

倒排文件

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

倒排索引分析

文档

doc1:I really liked my small dogs, and I think my mom also liked them. doc2:He never liked any dogs, so I hope that my mom will not expect me to liked him.

分词

初步的倒排索引的建立过程如下:

word doc1 doc2
I * *
really *
liked * *
my * *
small *
dogs *
and *
think *
mom * *
also * *
them * *
He *
never *
any *
so *
hope *
that *
will *
not *
expect *
me *
to *
him *

说明

如上是倒排索引最简单的建立的一个过程,如果我们搜索 mother like little dog,不可能有任何结果,这个是不是我们想要的搜索结果,绝对不是。因为在我们看来,mother 和 mom 有区别吗?同义词,都是妈妈的意思。like 和 liked 有区别吗?没有,都是喜欢的意思,只不过一个是现在时,一个是过去时。little 和 small 有区别吗?同义词,都是小小的。dog 和 dogs有区别吗?狗,只不过一个是单数,一个是复数。

normalization

定义

normalization,建立倒排索引的时候,会执行一个操作,也就是说对拆分出的各个单词进行相应的处理,以提升后面搜索的时候能够搜索到相关联的文档的概率。

比如:时态的转换,单复数的转换,同义词的转换,大小写的转换等。

建立索引

word doc1 doc2 normalization
I * *
really *
liked * * liked --> like
my * *
small * small --> little
dogs * dogs --> dog
and *
think *
mom * *
also * *
them * *
He *
never *
any *
so *
hope *
that *
will *
not *
expect *
me *
to *
him *

说明

重新建立倒排索引,加入 normalization,再次用 mother liked little dog 搜索,就可以搜索到了。

Elasticsearch倒排索引原理总结

Elasticsearch 使用一种称为倒排索引的结构,它适用于快速的全文搜索。一个倒排索引由文档中所有不重复词的列表构成,对于其中每个词,有一个包含它的文档列表。

倒排索引主要由单词词典(Term Dictionary)和倒排列表(Posting List)及倒排文件(Inverted File)组成。