反向索引-Inverted Index

以下来自维基百科：

倒排索引（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"在第三个文档里 (T2)，而且在第三个文档的位置是第四个单词(地址为 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得到。

-------------------------------------------------------

为什么要提出这样一种索引方式呢？

举个例子，如果有两个文档，doc1 & doc2 内容分别如下：
Doc1: it is what it is.
Doc2: what is it.

正向索引建立：
文档名 关键字 次数
Doc1 it 2
Doc1 is 2
Doc1 what 1
Doc2 what 1
Doc2 is 1
Doc2 it 1

不难发现，对于单文档内部检索，正向索引的建立，可以保证快速的进行检索。但对于全文检索，却很难有很好的性能，甚至由于实际资源的限制，而不可行。

“正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。”

题外话：
在设计某个问题的解决方案时，可能自身由于一直深入于整个工作，对问题的理解越来越深，不断有新的思路出来，继续不断有些方案出来，从来最终形成了整个解决方案。但或许，在整个过程中的某个时刻，跳出来，可能会有更高效的方法。比方说，可以参照算法方法论，如动态规划、贪心算法等来进行具体方案的求解。

Keywords: Inverted index; full-text search