子串搜索算法(大草堆,小针)

您正在查找名为 Trie 或“前缀树”。简而言之,这个数据结构对语料库中所有可能的字符串前缀进行编码。

Here is a paper

如果您知道输入搜索字符串的长度有一个明确的限制,那么可以限制Trie的增长,以便它不会存储任何超过此最大长度的前缀。这样,您就可以将表示所有10G的Trie放入少于10G的内存中。特别是对于高度重复的数据,任何类型的Trie都是一种压缩数据表示(或者 应该

考虑到KnuthMorrisPratt或BoyerMoore,您不会做得更好,您应该考虑的是搜索过程的并行化。

值得一看 suffix arrays 和 trees O(m) (后缀树)和 O(m + log n)

很多 在你手上的时间,你可以看看 compressed suffix arrays 以及简洁的csa,它们是数据的压缩版本,也是自索引的(即数据也是索引,没有外部索引)。这真的是世界上最好的,因为你不仅有一个压缩版本的数据(你可以扔掉原始数据),但它也索引!问题是理解研究论文并将其翻译成代码:)

如果您不需要完美的子串匹配,而是需要通用的搜索功能,请查看 Lucene .

前缀/后缀树通常是标准的、最好的和最有用的 谨慎的 我认为这类事情的解决办法。你不能把它们弄错。

Bloom filters . 你可能知道这些是什么,但以防万一(对于阅读这个答案的其他人来说):Bloom过滤器是非常小,非常紧凑的位向量,近似于集合包含。如果您有一个集合S和该集合B(S)的Bloom过滤器,那么

x ∈ S ⇒ x ∈ B(S)

但回报是错误的。这就是结构的概率性:有一个( quantifiable 疯狂地 比在片场测试要快。

( 简单的案例用法 :在许多应用中,布卢姆过滤器被用作 滤波器

Bloom过滤器在字符串搜索中得到了一些成功的应用。下面是这个应用程序的草图(我可能记错了一些细节)。文本文件是由N行组成的序列。您正在寻找一个由M个字母组成的单词(没有单词可以跨两行传播)。预处理阶段通过将每一行的子序列添加到bloomfilter中,为每一行构建一个bloomfilter;例如,对于这条线

 Touching this dreaded sight, twice seene of vs,

相应的Bloom过滤器将被创建为“T”、“To”、“Tou”哦,你,你vs,“,”s“,”s“,”s“,”s“(我可能把这部分搞错了。或者您可能需要优化。)

我相信从这个概念中你可以得出一个适合你的情况的有用的方案。现在,我看到两个明显的适应:

• 或者使用一种二分法,你把集合分成两个子集,每个子集都有一个Bloom过滤器,然后每个子集用它们自己的Bloom过滤器分成两个子集,等等(如果你要按照我描述的方法添加所有的子串,第二个想法会有点禁止——除非你不必添加所有的子串,仅限大小为1到10的子字符串)。

如果你能负担得起空间(很多空间!)为了创建索引,索引小块(例如,四字节块)并将其偏移量存储在干草堆中是值得的—然后搜索10个字节包括搜索词的前四个字节的所有四字节块并检查下六个字节。