查看“︁倒排索引”︁的源代码

{{noteTA
|G1=IT
}}
'''倒排索引'''（英语：Inverted index），也常被称为'''反向索引'''、'''置入档案'''或'''反向档案'''，是一种[[索引]]方法，被用来[[存储]]在[[全文搜索]]下某个单词在一个文档或者一组文档中的[[存储位置]]的[[映射]]。它是[[文档检索系统]]中最常用的[[数据结构]]。

有两种不同的反向索引形式：
*一条记录的水平反向索引（或者反向档案索引）包含每个引用单词的文档的[[列表]]。
*一个单词的水平反向索引（或者完全反向索引）又包含每个单词在一个文档中的位置。<ref name="isbn0-201-39829-X-p192">{{cite book |author=Ribeiro, Berthier de Araújo Neto; Baeza-Yates, R. |title=Modern information retrieval |url=https://archive.org/details/moderninformatio0000baez |publisher=Addison-Wesley Longman |location=Reading, Mass |year=1999 |pages=[https://archive.org/details/moderninformatio0000baez/page/192 192] |isbn=0-201-39829-X |oclc= |doi=}}</ref>
后者的形式提供了更多的[[兼容性]]（比如[[短语搜索]]），但是需要更多的时间和空间来创建。

==例子==
以[[英文]]为例，下面是要被索引的文本：
*<math>T_0=</math><code>0. "it is what it is"</code>
*<math>T_1=</math><code>1. "what is it"</code>
*<math>T_2=</math><code>2. "it is a banana"</code>

我们就能得到下面的反向文件索引：
  "a":      {2}
  "banana": {2}
  "is":     {0, 1, 2}
  "it":     {0, 1, 2}
  "what":   {0, 1}

检索的条件<code>"what"</code>, <code>"is"</code> 和 <code>"it"</code> 将对应这个[[集合 (计算机科学)|集合]]：<math>\{0,1\} \cap \{0,1,2\} \cap \{0,1,2\} = \{0,1\}</math>。

对相同的文字，我们得到后面这些完全反向索引，由[[文档]]数量和当前查询的单词结果组成的的成对[[数据]]。 
同样，文档数量和当前查询的单词结果都从零开始。所以，<code>"banana": {(2, 3)}</code> 就是说 "banana"在第三个文档里 (<math>T_2</math>)，而且在第三个文档的位置是第四个单词(地址为 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)'''}

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

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

==参考书目==
{{reflist}}
{{refbegin}}
*[[高德纳]]，《[[计算机程序设计艺术]]》, Volume 3: "排序与索引"''排序与索引Sorting and Searching'', Third Edition. Addison-Wesley, 1997. ISBN 978-0-201-89685-5. 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.
{{refend}}

==相关==
*[[向量空間模型]]

==外部链接==
*反向索引[http://www.nist.gov/dads/HTML/invertedIndex.html NIST's Dictionary of Algorithms and Data Structures: inverted index] {{Wayback|url=http://www.nist.gov/dads/HTML/invertedIndex.html |date=20081216041026 }}

[[Category:数据管理]]
[[Category:搜尋演算法]]
[[Category:数据库索引技术]]
[[Category:子字符串索引]]