string - 用于索引整个文档的数据结构和用于快速搜索任何大小子字符串的算法

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。

这可以非常有效地完成，类似于倒排索引传统上执行 AND 查询的方式，但不是搜索同一文档中的所有术语，而是搜索递增位置的术语。