哪种字符串集合结构/算法最快适用于startswith和/或contains搜索？

Question

我遇到了以下情况： 我有一个非常大的字符串集合（假设有250,000个+），平均长度可能为30个字符。 我需要在这些字符串中进行许多搜索，大多数情况下会使用StartsWith和Contains类型的搜索。

集合在运行时是静态的。这意味着只需一次读取和填充首选集合即可..因此构建数据结构的性能绝对不重要。内存也不是问题：这也意味着如果需要的话，我不介意有两个具有相同数据的集合（例如一个用于startswith，另一个用于contains）。唯一重要的是搜索的性能，应该返回与搜索条件匹配的所有元素。

对于startswith，我遇到了Trie或Radix-tree，但也许还有更好的选择？

对于contains..我还没有很好的主意（除了在列表上运行linq查询，这在这么多数据的情况下不会非常快）。

提前感谢大家！

更新：我忘记了一个重要部分：对于包含，我的意思是集合中没有确切匹配的字符串..但我想找到包含给定搜索字符串的所有字符串。

- Mikk

---

你的Contains搜索中的子字符串是处理单词还是单个字符？我想知道是否建立索引对此有意义。 - Andrew Arnott

它应该支持字符。尽管出于性能原因，我可以想象在搜索之前给出3个或更多字符的最小长度。（可以将其视为文本框中的自动完成，只有在输入一些字符后才会启动） - Mikk

在网络上搜索“Rabin Karp”。这应该可以帮助您入门，因为它有几个相关的搜索算法链接... http://www.stoimen.com/blog/2012/04/02/computer-algorithms-rabin-karp-string-searching/ 此外，请考虑使用布隆过滤器并在启动时预加载其字符串。 - JimR

谢谢你的提示..特别是布隆过滤器对我来说是新的。我明天会更多地了解它们，现在是睡觉的时间了。 - Mikk

以...开始。将字符串存储在排序数组中并使用二分查找，易于实现、理解和快速。但不影响包含操作。 - rlb

Answer 1

构建一个后缀树将允许您在所有字符串中并行进行子字符串搜索，时间复杂度为O(1)。我想指出的是，它实际上是O(n + m)，其中n是与您的子字符串匹配的字符串数量，m是查询的子字符串的大小。

那么什么是后缀树呢？在其最基本的实现中，它是一棵trie树，具有更高级的插入方法：除了添加字符串外，它还将该字符串的每个可能的后缀添加到trie树中。在这个数据结构上，子字符串搜索变成了所有可能后缀的前缀搜索。由于您还想进行前缀搜索，因此需要在每个插入的字符串和查询子字符串之前添加一个特殊字符。这个特殊字符将允许您区分后缀和完整的字符串。

虽然这个后缀树的实现非常简单，但它也非常低效（O(n^2) 的空间和构建时间）。幸运的是，还有其他更有效率的实现方法，可以大大减少空间和时间的限制。其中之一，Ukkonen 算法，在this SO answer中有很好的解释，并将空间限制降至O(n)。您还可以查看suffix arrays，这是一个等价但更高效的后缀树表示形式。

虽然我知道还有很多后缀树的实现方法（其中一个可能正好符合您的用例），但我不知道它们。我建议您在选择实现方法之前对此进行一些研究。

- Ze Blob

---

你对后缀树的低效性认识是错误的。一个好的实现可以将时间复杂度优化到O(n)或O(n log n)，空间复杂度优化到O(n)。http://en.wikipedia.org/wiki/Suffix_tree - nhahtdh

到目前为止，这听起来非常棒！特别是使用特殊字符来区分后缀和前缀的想法！ - Mikk

@nhahtdh 进行了快速编辑，希望可以澄清一些问题。今晚我有点更多时间时，会再试一次。 - Ze Blob

由于我有一组字符串（而不是一个大字符串/文本），似乎“正常”的后缀树不足以支持。我需要一个广义后缀树 / 数组来支持我的多个字符串。不幸的是，到目前为止我没有找到真正的.NET实现。 但是，http://www.cs.iastate.edu/~cs548/suffix.pdf非常详细地描述了这个理论。这可能是一个非常有趣的难题要解决……我只需要看看在哪里可以找到时间或者是否必须满足更快（实现）的解决方案。 - Mikk

@Uwe 后缀树对于一组字符串来说非常有效。诀窍是为每个叶子节点添加一个值，指示该叶子节点所属的字符串。这和开头的特殊字符应该就是你所需要的全部内容。 - Ze Blob