如何在列表中实现增量搜索

Question

我希望在一个字符串列表上实现增量搜索。假设我有一个包含store、state、stamp、crawl和crow的字符串数组。我的应用程序中有一个文本框，用户可以输入搜索字符串。当用户输入文本时，我需要突出显示所有匹配项。例如，当用户输入“st”时，我需要突出显示“Store、state、stamp”，现在当他键入“a”时，我需要从列表中删除“Store”。我正在使用C#和.NET框架开发应用程序。我的计划是，在文本更改事件上进行后台搜索并显示结果。是否有其他解决方法？

- Pi.

---

当要匹配的字符串改变时，您想从当前位置继续匹配吗？还是想从开头开始？ - Anthony Mastrean

Answer 1

您可以只查看新输入的字母；如果新的第三个字母是'a'，则丢弃所有位置三没有'a'的元素。如果用户删除一个字母，则必须重新扫描整个原始列表并恢复所有已删除的项。

但是，如果用户从剪贴板中粘贴多个字母，通过选择它们来删除多个字母，在中间某个位置插入或删除单个或多个字母怎么办？

您需要关注的情况太多了。您可以使用新输入字母的方法，并在搜索文本以添加单个字母以外的方式更改时返回完整的重新扫描，但即使是这种简单的方法，也可能不值得花费大量精力仅仅为了避免几十或几百个字符串比较。正如先前提到的，如果您有非常大的数据集或想要快速操作，则Trie或Patricia trie是正确的选择。

- danbruc

---

请问您能否推荐一些可以完成这种工作的库？ - tong

Answer 2

我曾经在过去做过类似的事情，使用了一个包含大约500,000个单词的集合。我发现 有向无环词图 的效果很好。DAWG与trie的性能大致相同，但它更节省空间。然而，它的实现略微复杂。

不幸的是，我的工作是用C语言完成的，我没有一个好的参考来实现C#中的DAWG。

- Jim Mischel

Answer 3

如果您的列表长度可以增长到很大（超过数百个条目），那么trie数据结构是一个可扩展的选择。可以查看这个示例实现。

- Pontus Gagge

---

这就是为什么我们不提供链接。示例实现链接已过期。 - TEK

Answer 4

以下是一个函数，它会逐步搜索一个字符串以匹配子字符串。

public IEnumerable<int> FindAllMatches(string toMatch, string source) {
  var last = 0;
  do {
    var cur = source.IndexOf(toMatch,last);
    if ( cur < 0 ) {
      break;
    }
    yield return cur;
    last = cur + toMatch.Length;
  while(true);
}

- JaredPar

---

每次更改匹配的字符串，搜索都将从开头开始。 - Anthony Mastrean

Answer 5

你可以使用泛型集合代替字符串数组。这样，你就可以使用委托来搜索项目，使用FindAll方法。

string searchString = "s";
List<string> sl = new List<string>();
sl.Add("store");
sl.Add("state");
sl.Add("stamp");
sl.Add("crawl");
sl.Add("crow");
List<string> searchResults = sl.FindAll(delegate(string match) 
                                                { 
                                                    return   match.StartsWith(searchString, StringComparison.CurrentCultureIgnoreCase); 
                                                });

- Matthew Dresser

Answer 6

哇...

只需在文本框上使用内置的自动完成功能即可。您可以向其提供要匹配的单词列表，它将为您执行匹配操作。

- Rappa

Answer 7

好的，我已经为这个问题实现了Trie和DAWG，并遇到了两个令人烦恼的问题：

1）DAWG-->有向 无环 单词图。当使用诸如'bot'和'boot'之类的单词遍历此图时，'boot'中的'oo'会基于DAWG导致一个循环。 2）Trie可以消除此问题，但随后会引入一些分支管理问题。

构建图形比实际使用它生成想要的单词更容易（在我看来），而不会增加更多的运行时间。

我仍在继续解决这个问题。

- Christian Bongiorno

---

解决方案是不使用DAWG而是使用Trie。它就像是一种强化版的基数排序。 - Christian Bongiorno