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

Question

我正在尝试找到一种数据结构（和算法），它允许我索引整个文本文档并搜索它的子字符串，无论子字符串的大小如何。 数据结构应在索引过程期间或结束时存储在磁盘中。

例如，给出以下句子：

The book is on the table

算法应该快速 (

O(log(n))

) 找到文本中任何子集的出现。

例如，如果输入是

book

，它应该找到它的所有出现，但对于

book is

和

The book is

也应该如此。

不幸的是，大多数解决方案都是通过对文本进行标记并使用单个标记进行搜索来工作的。 普通数据库也可以索引任何文本，而不用担心子集搜索（这就是为什么

SELECT '%foo%'

是用线性搜索完成的并且需要很多？）。

我可以尝试从头开始开发一些东西（也许是反向索引的变体？），但我很想发现有人这样做了。

我发现的最相似的是SQLite3全文搜索。

谢谢！

Answer 1

一种方法是在后缀树中对文档进行索引，然后 - 某些后缀的每个前缀 - 都是文档中的子字符串。

使用这种方法，您所要做的就是构建后缀树，并在查询子字符串

s

时，跟踪树中的节点，如果您可以跟踪整个查询字符串 - 这意味着存在后缀，它的前缀是查询字符串 - 因此它也是一个子字符串。

---

如果您只查询完整的单词，倒排索引就足够了。倒排索引通常将一个术语（单词）映射到它出现的文档列表。相反，对于您来说，它将映射到文档中的位置。

查询时，您需要查找查询中每次出现的单词

i

及其位置（让它为

p

），并且如果查询中的术语

i+1

也出现在位置

p+1

中。

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

Answer 2

如果您想在大文本中快速搜索子字符串，请使用后缀数组或后缀树。后缀树是给定文本的所有后缀的压缩特里树。它允许快速子字符串搜索，通常需要 O(m) 时间，其中 m 是正在搜索的子字符串的长度。在后缀数组中，文本所有后缀的排序数组，对于 O(m+log n) 时间的子字符串搜索非常有效，并且可以存储在磁盘上，使其可扩展用于大型文本。后缀数组是一个整数数组，给出字符串后缀的起始位置，按字典顺序排序。它比后缀树更节省空间。在后缀树中，所有后缀的压缩 trie 结构，允许 O(m) 子字符串搜索，并且更占用内存，但比后缀数组更快。