倒排索引

type

status

date

slug

summary

假设目前有两个 HTML 页面，一个页面内容是 "I like search engines."，而另一个页面内容是 "I search keywords in google."，现在将其按照单词进行划分，形成下表所示的结构：

其中，每一行表示一个页面，每一列表示一个单词，0 表示该单词未出现在该页面中，而 1 则表示该单词出现在该页面中。那么当我们搜索含有关键词 "engine" 的页面时，我们需要遍历上表的每一行，这就是正排索引。

其定义如下：当用户发起查询时（假设查询为一个关键词），搜索引擎会扫描索引库中的所有文档，找出所有包含关键词的文档，这样依次从文档中去查找是否含有关键词的方法叫做正排索引。

现在我们交换上表中的行和列，就会形成如下所示的表格结构：

更进一步的，我们将其转化为如下形式：

那么此时我们搜索含有关键词 "engine" 的页面，可以直接在常数时间复杂度内找到其结果为 P1，这就是倒排索引。并且，我们还可以在建立索引的时候为每个页面加上其他的衡量参数，在建立索引时就可以根据这些参数完成页面排序。

其定义如下：搜索引擎会把正排索引变为倒排索引，即把“文档→单词”的形式变为“单词→文档”的形式。

倒排索引的结构如下图所示：

代码实现

倒排项的定义如下:

倒排列表的定义如下：

倒排索引的定义如下：

创建倒排索引的相关代码如下：

关键词搜索相关的代码如下：