开始搜索和/或包含搜索的最快字符串集合结构/算法是什么

Question

我有以下情况:我有一个大的字符串集合(比方说250.000+)，平均长度可能是30。我要做的就是在这些中做很多搜索..大多数情况下，它们将是StartsWith类型的，并且包含种类。

该集合在运行时是静态的。这意味着对所选集合的初始读取和填充只进行一次。因此，构建数据结构的性能绝对不重要。内存也不是问题:这也意味着如果需要的话，我不介意在每个集合中有两个具有相同数据的集合(比如一个用于开头，另一个用于包含)。唯一重要的是搜索的性能，它应该返回匹配搜索条件的所有元素。

首先，我遇到了一棵Trie或Radix-tree。但也许还有更好的选择呢？

For包含..我还没有好的想法(除了在list上运行linq查询，这对于这么多的数据来说不会很快)。

提前感谢大家！

更新:我忘记了一个重要的部分:对于包含，我的意思是集合中没有完全匹配的内容。但是我希望在集合中找到包含给定搜索字符串的所有字符串

Answer 1

构建suffix tree将允许您在O(1)中并行地对所有字符串执行子字符串搜索。我的书呆子情不自禁地注意到，它实际上是O(n + m)，其中n是匹配您的子字符串的字符串数，m是正在查询的子字符串的大小。

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

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

虽然我知道有很多后缀树的实现(其中一个可能最适合您的用例)，但我并不了解它们。我建议你在决定实现之前对这个主题做一些研究。