我有以下情况：
我有一个大的字符串集合（比如说 250.000+），平均长度可能是 30。
我要做的就是在这些搜索中进行许多搜索..大多数搜索都是 StartsWith 和 Contains 类型的。
该集合在运行时是静态的。这意味着选择的集合的初始读取和填充仅完成一次..因此构建数据结构的性能绝对不重要。内存也不是问题：这也意味着我不介意在需要时拥有两个具有相同数据的集合（例如一个用于startswith，另一个用于contains）。
唯一重要的是搜索的性能，它应该返回与搜索条件匹配的所有元素。
首先，我遇到了 Trie 或 Radix-tree ..但也许还有更好的选择？
对于 contains .. 我还没有什么好主意（除了在列表上运行 linq 查询之外，对于这么多数据量来说，这不会很快）。
预先感谢大家！
更新：我忘记了一个重要的部分：使用 Contains 我的意思是集合中没有完全匹配的内容..但我想找到集合中包含给定搜索字符串的所有字符串
建设一个后缀树 http://en.wikipedia.org/wiki/Suffix_tree将允许您并行地对所有字符串进行子字符串搜索O(1)。我的迂腐情不自禁地注意到，这确实是O(n + m) where n是与您的子字符串匹配的字符串数量，m是正在查询的子字符串的大小。
那么你问的后缀树是什么？在其最基本的实现中，它是一个具有更奇特的插入方法的特里树：除了添加字符串之外，它还将该字符串的每个可能的后缀添加到特里树中。在这个数据结构上，子字符串搜索变成了所有可能的后缀的前缀搜索。由于您还想进行前缀搜索，因此您需要在每个插入的字符串和查询子字符串前面添加一个特殊字符。特殊字符将允许您区分后缀和完整字符串。
虽然后缀树的这种实现非常简单，但效率也非常低（O(n^2)空间和构建时间）。幸运的是，还有其他更有效的实现可以大大减少空间和时间限制。其中之一，Ukkonen 算法，在 中得到了很好的解释这个答案 https://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english/9513423#9513423并将空间限制为O(n)。您可能还想了解一下后缀数组 http://en.wikipedia.org/wiki/Suffix_array这是后缀树的等效但更有效的表示。
虽然我知道还有更多后缀树的实现（其中之一可能会满足您的用例），但我只是不了解它们。我建议您在决定实施之前对该主题进行一些研究。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
