哪种C#数据结构最有效地允许搜索一对字符串以查找子字符串？

Question

我有一个数据结构，由两个值组成，第一个是整数，第二个是由数字开头的字母数字混合字符串：

+--------+-----------------+
| Number | Name            |
+--------+-----------------+
| 15     | APPLES          |
| 16     | APPLE COMPUTER  |
| 17     | ORANGE          |
| 21     | TWENTY-1        |
| 291    | 156TH ELEMENT   |
+--------+-----------------+

一张表格可能包含多达100,000行。

我想提供一个查找函数，用户可以查找数字（就像字符串一样）或字符串的一部分。理想情况下，当用户输入时，查找将是“实时”的; 每次按键后（或者在短暂的延迟 ~250-500毫秒后），将进行新的搜索以找到最有可能的候选项。因此，例如在以下搜索：

1将返回15 APPLE，16 APPLE COMPUTER，17 ORANGE和291 156TH ELEMENT

15将缩小搜索范围为15 APPLES和291 156TH ELEMENT

AP将返回15 APPLES和16 APPLE COMPUTER

（理想情况下，但不是必需的）ELEM将返回291 156TH ELEMENT。

我考虑使用两个Dictionary，因为最终int作为字符串进行比较——一个将以整数部分为索引，另一个将以字符串部分为索引。

但是，用子串搜索真的不应该使用哈希函数，而且使用我认为应该需要的两倍内存似乎很浪费。

最终的问题是，在同时搜索两个大列表中是否有任何性能良好的文本搜索方式的子字符串？

如果失败，那么 SortedDictionary 呢？可能会提高性能，但仍无法解决哈希问题。

想过即时创建正则表达式，但我认为性能会很差。

我是C＃的新手（来自Java世界），所以还没有研究LINQ; 那是答案吗？

编辑18:21 EST：如果字符串中的“名称”字段不会超过12-15个字符，则影响您的潜在解决方案。

- James Cronen

---

我认为稍加修改的Knuth-Morris-Pratt算法会很有用。 - ChaosPandion

+1 分，如果正确使用“ comprise”（不常见）请仅返回翻译后的文本。 - phoog

@hatchet：这种情况将被包含在我的“可选”案例中。如果性能允许的话当然很好，但如果没有解决方案表现得足够好，我可以牺牲这个搜索条件。 - James Cronen

@EBarr：关于稳定性，字符串在应用程序的整个生命周期内都会相当稳定，但我可能需要在应用程序中进行一些添加/修改/删除。如果我可以搜索一个项目，我会假设我也可以轻松地修改或删除它。 - James Cronen

啊，我明白了。基于业务规则的加权结果。 - Jagd

Answer 1

如果可能的话，我会避免将所有10万个条目加载到内存中。我会使用数据库或Lucene.Net来索引这些值。然后使用适当的查询语法来高效地搜索结果。

- Phil Bolduc

---

我上面概述的只是产品的一小部分，我真的希望能找到最轻量级的解决方案。话虽如此，如果我找不到其他性能良好的解决方案，我肯定会考虑使用Lucene.net内存中的方案。谢谢！ - James Cronen

Answer 2

我建议使用Trie数据结构。

如何实现呢？每个“叶子”代表一行，但是您需要为每个“行”的内存实例提供“两条路径”（一个用于数字，另一个用于名称）。

然后，您可以牺牲您的条件：

(ideally, but not required) ELEM will return 291 156TH ELEMENT.

或者为您的行实例提供更多路径。

- doblak

---

有趣的想法；我肯定会研究实施这个并看看它的性能如何。我没有在原始帖子中包含这个事实，但我可能可以在程序开始时进行初始树创建；如果这需要一点额外的时间，那当然不是世界末日。谢谢！ - James Cronen

做得很好。你比我更快地完成了这件事；-) - EBarr

这个解决方案比起“内存使用最优”的方案更像是一个“邪恶”的方案。当你实现它的时候，它会让你像个孩子一样哭泣 :) 正如Phil所提到的，Lucene.Net是一个不错的解决方案，但它真的取决于你具体的用例。如果有100k这样的字符串...大概是1MB左右。如果你可以直接在内存中使用它们，那么并不算太多，但如果你需要从数据库中多次请求并首先构建一个trie，那就另当别论了。 - doblak

当文件被打开或应用程序首次打开并保存在内存中时，可能会构建trie。用户可能会在一天中多次使用这个特定的搜索。如果用户在一定时间内不再使用搜索，则我也可以自己放置一些简单的垃圾回收，并在必要时按需重建trie。 - James Cronen

我认为这个变体将是胜利者。我正在编写一个基数 trie 的实现，它将带来每个 trie 节点可用的有效负载的好处。有效负载将携带对由此字符串表示的对象的引用。这也将允许具有共同开头的条目（如“APPLE”和“APPLESAUCE”）指向不同的实体。此外，数字部分和名称部分将拥有自己的 trie 路径，并且都将指向相同的基础对象，因为它们代表相同的对象。谢谢大家！ - James Cronen

Answer 3

由于您正在搜索单词的开头，基于键的集合将不起作用，除非您存储所有可能的单词部分，例如“a”、“ap”、“app”、“appl”、“apple”。

我的建议是使用System.Collections.Generic.List<T>与二进制搜索结合使用。您必须提供自己的IComparer<T>，它也可以找到单词的开头。您将使用两个数据结构。

一个List<KeyValuePair<string,int>>保存单词或数字为键和数字为值。

一个Dictionary<int,string>保存整个名称。

您可以按以下步骤进行：

1. 将句子（整个名称）拆分为单个单词。

2. 将它们添加到列表中，其中单词作为KeyValuePair的键，数字作为值。

3. 将数字添加到列表中，作为KeyValuePair的键和值。

4. 当列表已满时，对其进行排序以允许二进制搜索。

搜索单词的开头：

1. 使用 BinarySearch 结合你的 IComparer<T> 在列表中进行搜索。

2. 从搜索得到的索引可能不是第一个匹配的，因此请在列表中返回，直到找到第一个匹配项。

3. 使用存储在列表中的数字作为值，在字典中查找整个名称，将该数字作为键。

- Olivier Jacot-Descombes