编程之法:面试和算法心得

 主页   资讯   文章   代码   电子书 

倒排索引(Inverted index)

方法介绍

倒排索引是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射,常被应用于搜索引擎和关键字查询的问题中。

以英文为例,下面是要被索引的文本:

T0 = "it is what it is"  
T1 = "what is it"  
T2 = "it is a banana"  

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

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

检索的条件"what","is"和"it"将对应集合的交集。

正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中,文档占据了中心的位置,每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词,而反向索引则是单词指向了包含它的文档,很容易看到这个反向的关系。

问题实例

1、文档检索系统,查询那些文件包含了某单词,比如常见的学术论文的关键字搜索

提示:建倒排索引。