我有以下情况: 我有一大堆平均长度可能为 30 的字符串(比方说 250.000+)。 我要做的是在这些中进行多次搜索.. 大多数搜索都是 StartsWith 和 Contains 类型的。
该集合在运行时是静态的。这意味着选择集合的初始读取和填充只进行一次..因此构建数据结构的性能绝对不重要。内存也不是问题:这也意味着如果需要的话，我不介意在每个集合中有两个包含相同数据的集合(比如一个用于 startswith，另一个用于包含)。 唯一重要的是搜索的性能，它应该返回与搜索条件匹配的所有元素。
首先，我遇到了 Trie 或 Radix 树 .. 但也许还有更好的选择？
对于包含 .. 我还没有什么好主意(除了在列表上运行 linq 查询之外，对于那么多的数据来说速度不会很快)。
先谢谢大家了!
更新:我忘记了一个重要的部分:包含我的意思是集合中没有完全匹配..但我想找到集合中包含给定搜索字符串的所有字符串
最佳答案
构建 suffix tree将允许您在 O(1) 中并行对所有字符串进行子字符串搜索。我的迂腐不禁注意到它真的是 O(n + m) 其中 n 是与您的子字符串和 m< 匹配的字符串的数量 是被查询子串的大小。
那么你问什么是后缀树？在其最基本的实现中，它是一个带有更高级插入方法的 trie:除了添加一个字符串之外，它还将该字符串的每个可能的后缀添加到 trie。在这个数据结构上，子串搜索变成了所有可能后缀的前缀搜索。由于您还想进行前缀搜索，因此您需要在每个插入的字符串和查询子字符串前添加一个特殊字符。特殊字符可让您区分后缀和完整字符串。
虽然后缀树的这种实现非常简单，但它的效率也非常低(O(n^2) 空间和构建时间)。幸运的是，还有其他更有效的实现可以大大减少空间和时间限制。其中之一，Ukkonen 的算法，在 this SO answer 中得到了很好的解释。并将空间限制降低到 O(n)。您可能还想查看 suffix arrays这是后缀树的等效但更有效的表示。
虽然我知道还有更多的后缀树实现(其中一个可能会满足您的用例)，但我只是不了解它们。我建议您在确定实现之前对该主题进行一些研究。
关于c# - 什么是 startswith 和/或包含搜索的最快的字符串集合结构/算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15191885/