数据结构索引整个文档和算法进行快速搜索任何规模大小子

Question

我试图找到一个数据结构（和算法），让我来索引整个文本文档，并搜索它的子，也不管子字符串的大小。在索引过程中或结束时，数据结构应存储在磁盘中。

例如，给定下面的句子：

The book is on the table 

算法应该迅速（O(log(n))）找到的出现的任何文本子集。

例如，如果输入是book它应该找到它的所有实例，但这也应该是book is和The book is。

不幸的是，大多数解决方案通过令牌化的文本，并使用单独的标记使搜索工作。普通的数据库也可以索引任何文本，而不用担心子集搜索（这就是为什么SELECT '%foo%'用线性搜索完成并需要很多？）。

我可以尝试从头开发的东西（可能是反向指标的变化？），但我很想发现有人这样做。

最类似的事情，我发现是SQLite3 Full-text search。

谢谢！

Answer 1

一种方法是指数在一个suffix tree您的文档，然后 - 一些后缀的每个前缀 - 在文档中的子字符串。

使用这种方法，您只需构建后缀树，并在查询子字符串s时，遵循树中的节点，并且如果您可以按照整个查询字符串执行操作，则表示有后缀，它的前缀是查询字符串 - 因此它也是一个子字符串。

---

如果您只查询完整单词，则inverted index可能就够了。倒排索引通常映射某个术语（单词）到它出现在文档列表。相反，你会映射到文档中的位置。

经查询，你需要找到在查询词i每一次出现，它的位置（让它成为p），如果你的查询期限i+1，出现以及在p+1位置。

这可以非常有效地进行，类似于传统是如何倒排索引做和查询，而是进行搜索相同的文档，在增加职位搜索项中的所有条款。