在字符串列表中高效搜索字符串的方法是什么？

Question

我有一个字符串列表，需要找出与给定输入值匹配的字符串。

在存储这个字符串列表并能够搜索它时，最高效的方法（考虑内存和执行速度）是什么？启动和加载字符串列表不重要，但搜索响应时间很重要。

我应该使用List、HashSet、基本的string[]或其他什么东西？

- MakkyNZ

---

字符串列表的“大小”有多大？ - Kris Krause

任何字符串都可以是重复的吗？您需要匹配整个单词/字符串还是可以包含在一个字符串中？ - Jason Down

@KrisKrause StringCollection非常慢。它在内部使用ArrayList。 - vcsjones

@Kris Krause：StringCollection 不够快。 - jason

我希望MakkyNZ能够尝试一些性能测试，利用大多数（如果不是全部）框架类型来亲自体验...特别是在速度至关重要的情况下。 - Kris Krause

Answer 1

这要看字符串的特性和集合的大小。根据集合的特征和预期的搜索字符串，可以通过巧妙地组织来实现快速搜索。但是您没有提供这些信息。

但是这是我会做的。我会设定一个合理的性能要求。然后我会尝试使用n-gram索引（为什么？因为您在评论中说需要考虑部分匹配; HashSet<string> 在这里无法帮助您），并针对我预期的合理输入对此解决方案进行性能分析，以查看它是否符合我的性能要求。如果符合，我会接受该解决方案并继续前进。如果不符合，我会认真思考我的性能要求是否合理。如果合理，我会开始考虑我的输入和集合是否有什么特殊之处，可能可以使用更聪明的解决方案。

- jason

---

一个HashSet无法满足他对部分匹配的需求（如果字符串“可以重复”，这意味着有一些信息可以区分重复项，所以无论如何都应该使用Dictionary而不是HashSet）。 - Random832

@Random832：他的问题并没有提到任何关于部分匹配或重复项的内容！ - jason

一条跟进的评论提到了，在你急于成为FGITW的时候，你没有停下来问需要什么 - 原始措辞根本不暗示HashSet可以解决的问题。仔细阅读“哪些字符串与给定输入值匹配”揭示了复数意味着部分匹配（只有一个字符串可以完全匹配）。 - Random832

@Random832：赶去什么？我不知道这个缩写是什么意思。无论如何，我并没有匆忙去做任何事情。建议我仔细阅读一个甚至没有仔细撰写的问题（如果需要在后面的评论中澄清一些必要的细节），这很傻。请注意标题：“C#高效地搜索字符串列表？”请注意，OP本人问是否适用于HashSet。 - jason

它的意思是“西部最快枪手”。如果问题没有提供必要的细节，那就需要评论。 “请注意，OP本人问了HashSet是否合适”-答案是否定的。对于大多数人来说，“搜索”意味着在文档中进行文本搜索，通常甚至没有“仅匹配整行”的选项，更不用说它是默认设置了。 - Random832

Answer 2

看起来最好的方式是在O(input_len)时间内构建输入的后缀树，然后在O(pattern_length)时间内查询模式。因此，如果您的文本与您的模式相比真的很大，这将很有效。

请参阅Ukkonen算法以构建后缀树。

如果您想进行不精确匹配...请参阅Gonzalo Navarro的工作。

- Cris Stringfellow

---

针对 trie 中的每个节点，只需构建一个字符/字节数组，长度为 256 或更可能是 128。该数组应该是由 256/128 个指向节点的指针所组成，而非字节。 - Random832

或者更准确地说，一个由字符的ASCII（或其他字符集）代码索引的对象引用/指针节点数组Node node* = new Node [128]。感谢Random832的改进。 - Cris Stringfellow

这是最快的吗？还是最节省内存的？我认为后者才是。 - Odnxe

鉴于需要进行部分匹配，前缀树并不能真正帮上忙。 - jason

Answer 3

使用 Dictionary<string>() 或者 HashSet<string> 可能对您有好处。

• 在这里查看 Dictionary
• 以及这里的 HashSet

- Felice Pollano

---

+1：当考虑在字符串列表中优化搜索字符串时，我想到的第一件事也是“索引”，其中字典是最常见的解决方案。 - Stephane Rolland

@StephaneRolland 有时候简单就是最好的，但即使是gotafex的解决方案也值得一加。 - Felice Pollano

Answer 4

字典和哈希表是最快的“搜索”方式，因为它们的速度是O(1)。但是，字典和哈希表也有一些缺点，它们不是排序的。

使用二叉搜索树，您将能够获得O(Log N)的搜索速度。

使用未排序的列表，您将获得O(N)的搜索速度。

使用排序的列表，您将获得O(Log N)的搜索速度，但请记住，列表必须排序，这会增加整体速度。

至于内存使用，只需确保初始化集合的大小即可。

因此，字典或哈希表是检索最快的。

从最好到最差的速度分类如下： O(1) O(log n) O(n) O(n log n) O(n^2) O(2^n)

n是元素的数量。

- Odnxe

---

@FelicePollano 我认为你对O(1)的含义理解不够准确。 - Random832

@Random832，在插入操作中，时间复杂度为O（1）。在搜索操作中，首先定位列表的时间复杂度为O（1），然后执行线性搜索。您认为有什么问题？ - Felice Pollano

事实上，“列表”（即冲突链）需要进行线性搜索的长度通常很短，与字典中所有项目的总数不成比例（如果有适当数量的桶），这意味着它仍然是O(1)摊销，除非插入了大量具有相同哈希码的项目[这种情况不太可能，除非故意构造]。 - Random832