倒排索引

反向索引是一种索引数据结构，用于存储从内容（如单词或数字）到其在文档或一组文档中的位置的映射。简单地说，它是一种类似hashmap的数据结构，将您从一个单词引导到一个文档或网页。

有两种类型的倒排索引： 创纪录的反向指数 包含每个单词对文档的引用列表。A. 字级倒排索引 另外还包含文档中每个单词的位置。后一种形式提供了更多的功能，但需要创建更多的处理能力和空间。

假设我们想搜索文本“hello everyone”，“本文基于倒排索引”，“这是类似hashmap的数据结构”。如果我们按（文本、文本中的单词）索引，则在文本中具有位置的索引是：

 hello                (1, 1) everyone             (1, 2) this                 (2, 1) article              (2, 2) is                   (2, 3); (3, 2) based                (2, 4) on                   (2, 5) inverted             (2, 6) index                (2, 7) which                (3, 1) hashmap              (3, 3) like                 (3, 4) data                 (3, 5) structure            (3, 6)

“hello”一词出现在文档1（“hello everyone”）中，从单词1开始，因此有一个条目（1，1），而单词“is”分别出现在文档2和文档3中的“第三”和“第二”位置（这里的位置基于单词）。 该指数可能有权重、频率或其他指标。

建立反向索引的步骤：

• 取文件 停止词的删除：停止词是文档中最常见和最无用的词，如“I”、“the”、“we”、“is”、“an”。
• 词根词干 每当我想搜索“cat”时，我都想看到一个包含相关信息的文档。但文件中的单词被称为“猫”或“猫”，而不是“猫”。为了把这两个词联系起来，我会把我读到的每一个词都切掉一部分，这样我就可以得到“词根”。有一些标准的工具可以实现这一点，比如“波特的词干分析器”。
• 记录文档ID 如果word已经存在，则将文档的引用添加到索引中，否则创建新条目。添加其他信息，如单词频率、单词位置等。

例子：

Words                 Documentant                   doc1demo                  doc2world                 doc1, doc2

倒排索引的优点是：

• 反向索引允许快速全文搜索，但在将文档添加到数据库时会增加处理量。
• 它很容易开发。
• 它是文档检索系统中最常用的数据结构，在搜索引擎中被广泛使用。

该指数也有相反的缺点：

• 更新、删除和插入时存储开销大，维护成本高。