6

我知道倒排索引是索引单词的好方法，但我很困惑的是搜索引擎实际上是如何存储它们的？例如，如果一个单词“google”以不同的频率出现在文档 - 2、4、6、8 中，应该将它们存储在哪里？具有一对多关系的数据库表可以用来存储它们吗？

4

4 回答 4

5

为此目的使用成熟的类 SQL 数据库的可能性很小。首先，它被称为倒排索引，因为它只是一个索引。每个条目只是一个参考。随着非关系数据库和键值存储成为与 Web 技术相关的热门话题。

  • 您只有一种访问数据的方式（通过查询词）。这就是为什么它被称为索引。
  • 每个条目都是对文档的引用的列表/数组/向量，因此该列表的每个元素都非常小。除了存储 documentID 之外，唯一的其他信息是存储每个元素的 tf-idf 分数。

如何使用它：

如果您有一个查询词（“google”），那么您在倒排索引中查找该词出现的文档（在您的示例中为 2,4,6,8）。如果你有 tf-idf 分数，你可以对结果进行排序以首先报告最匹配的文档。然后，您查找文档 ID 2、4、6、8 引用的文档，并报告它们的 URL 以及片段等。URL、片段等可能最好存储在另一个表或键值存储中。

如果您有多个查询词（“google”和“altavista”），则查看两个查询词的 II 并获得两个文档 ID 列表（2、4、6、8 和 3、7、8、11， 19）。您取两个列表的交集，在本例中为 (8)，即出现两个查询词的文档列表。

于 2014-10-06T15:35:45.753 回答
4

传统上，倒排索引直接写入文件并存储在磁盘上的某个位置。如果您想进行布尔检索查询（文件是否包含查询中的所有单词），帖子可能看起来像这样连续存储在文件中。

Term_ID_1:Frequency_N:Doc_ID_1,Doc_ID_2,Doc_ID_N.Term_ID_2:Frequency_N:Doc_ID_1,Doc_ID_2,Doc_ID_N.Term_ID_N:Frequency_N:Doc_ID_1,Doc_ID_2,Doc_ID_N

术语 id 是术语的 id，频率是术语出现在文档中的数量（换句话说，帖子列表有多长），文档 ID 是包含该术语的文档。

除了索引之外，您还需要知道文件中所有内容的位置，因此映射也必须存储在另一个文件的某个位置。例如，给定一个 term_id，地图需要返回包含该索引的文件位置，然后才能找到该位置。由于frequency_id 记录在帖子中，因此您知道要从文件中读取多少个doc_id。此外，还需要从 ID 映射到实际的术语/文档名称。

如果您有一个小用例，您可以使用 SQL 来解决这个问题，方法是使用 blob 作为发布列表并在查询时自己处理交集。

对于非常小的用例，另一种策略是使用术语文档矩阵。

于 2015-04-19T22:54:39.010 回答
4

可以肯定的是，每个主要搜索引擎都有自己的倒排索引处理技术。它们不基于标准的关系数据库技术也是一个不错的选择。

在 Google 的具体案例中，合理的猜测是，当前使用的技术源自Fay Chang 等人在 2006 年在Bigtable: A Distributed Storage System for Structured Data中描述的BigTable技术。不过，毫无疑问，该系统自那时以来已经发展了。

于 2014-09-29T03:58:57.793 回答
3

可能的解决方案

一种可能的解决方案是使用位置索引。它基本上是一个倒排索引，但我们通过添加更多信息来扩充它。你可以在斯坦福 NLP阅读更多关于它的信息。

例子

说一个单词“你好”出现在文档 1 和 3 中，分别位于 (3,5,6,200) 和 (9,10) 位置。

  • 基本倒排索引（注意没有办法找到单词频率也没有位置）

"hello" => [1,3]

  • 位置索引（请注意，我们不仅有每个文档的频率，而且我们还确切地知道该术语在文档中出现的位置）

"hello" => [1:<3,5,6,200> , 3:<9,10>]

小心

你的索引现在会占用更多的大小吗？你打赌！

这就是为什么压缩索引是个好主意。有多个选项可以使用间隙编码压缩帖子列表，还有更多选项可以使用通用字符串压缩算法压缩字典。

相关读物

索引压缩

发帖文件压缩

字典压缩

于 2017-09-07T18:37:29.853 回答