Lucene倒排索引

为什么搜索引擎的查询速度这么快？ 说明白了很简单，核心技术就是 “倒排索引”。 “倒排索引”这个名词很唬人，其实原理很简单。 假设有3篇文章，file1,file2,file3，文件内容如下：  file1 (单词1，单词2，单词3，单词4....) file2 (单词a，单词b，单词c，单词d....) file3 (单词1，单词a，单词3，单词d....) 建立的倒排索引就是这个样子： 单词1 (file1,file3) 单词2 (file1) 单词3 (file1,file3) 单词a (file2, file3) .... 这就是倒排索引，很简单吧。 比如一个文件要建立索引，就先把它抽成纯文本的格式，然后把一个一个的单词切割出来，每个单词在数据库里是一条记录，单词作为关键字，后面跟着文件的标识ID，位置。

 

倒排索引（英语：Inverted index），也常被称为反向索引、置入档案或反向档案，是一种方法，被用来在下某个单词在一个文档或者一组文档中的的。它是中最常用的。

有两种不同的反向索引形式：

• 一条记录的水平反向索引（或者反向档案索引）包含每个引用单词的文档的。
• 一个单词的水平反向索引（或者完全反向索引）又包含每个单词在一个文档中的位置。

后者的形式提供了更多的（比如），但是需要更多的时间和空间来创建。

例子

以为例，下面是要被索引的文本：

• T₀ = "it is what it is"
• T₁ = "what is it"
• T₂ = "it is a banana"

我们就能得到下面的反向文件索引：

 "a":      {2}
 "banana": {2}
 "is":     {0, 1, 2}
 "it":     {0, 1, 2}
 "what":   {0, 1}

检索的条件"what", "is" 和 "it" 将对应这个：。

对相同的文字，我们得到后面这些完全反向索引，有数量和当前查询的单词结果组成的的成对。 同样，文档数量和当前查询的单词结果都从零开始。所以，"banana": {(2, 3)} 就是说 "banana"在第三个文档里 (T₂)，而且在第三个文档的位置是第四个单词(地址为 3)。

"a":      {(2, 2)}
"banana": {(2, 3)}
"is":     {(0, 1), (0, 4), (1, 1), (2, 1)}
"it":     {(0, 0), (0, 3), (1, 2), (2, 0)} 
"what":   {(0, 2), (1, 0)}

如果我们执行短语搜索"what is it" 我们得到这个短语的全部单词各自的结果所在文档为文档0和文档1。但是这个短语检索的连续的条件仅仅在文档1得到。

应用

• 反向索引数据结构是典型的重要的部分。
• 一个的目标就是查询的速度：找到某个单词在文档中出现的地方。以前，开发出来用来存储每个文档的单词的列表，接着掉头来开发了一种反向索引。 正向索引的查询往往满足每个文档有序频繁的和每个单词在中的这样的查询。
• 实际上，时间、、等等资源的限制，技术上正向索引是不能实现的。
• 为了替代正向索引的每个文档的单词列表，能列出每个查询的单词所有所在文档的列表的反向索引数据结构开发了出来。
• 随着反向索引的创建，如今的查询能通过立即的单词标示迅速获取结果（经过）。随机存储也通常被认为快于。

参考书目

1. Ribeiro, Berthier de Araújo Neto; Baeza-Yates, R.（1999年）．Modern information retrieval．Reading, Mass：Addison-Wesley Longman，192．． 

• ，《》, Volume 3: "排序与索引"排序与索引Sorting and Searching, Third Edition. Addison-Wesley, 1997. . Pages 560–563 of section 6.5: Retrieval on Secondary Keys.
• Justin Zobel, Alistair Moffat and Kotagiri Ramamohanarao, Inverted files versus signature files for text indexing. ACM Transactions on Database Systems (TODS), Volume 23, Issue 4 (December 1998), Pages: 453 - 490.