用于搜索字符串的数据结构
本文关键字：数据结构 字符串 搜索 用于 | 更新日期: 2023-09-27 18:26:30
我正在为以下情况寻找最佳的数据结构：在我的例子中，我将有数千个字符串，但是在这个例子中，出于明显的原因，我将使用两个。假设我有字符串"Water"answers"Walter"，我需要的是当输入字母"W"时，这两个字符串都会被找到，当输入"Wat"时，"Water"是唯一的结果。我做了一项研究，但我仍然不太确定哪种数据结构是正确的，如果我不确定，我不想实施它，因为这会浪费时间。所以基本上我现在想的要么是"Trie"要么是"后缀树"。看起来"尝试"会奏效，但正如我所说，我需要确定。此外，实现应该不是问题，所以我只需要知道正确的结构。如果有更好的选择，也可以随时告诉我。正如你所猜测的，像Dictionary/MultiDictionary这样的正常结构将不起作用，因为这将是一个内存杀手。我还计划实现缓存以限制内存消耗。很抱歉没有代码，但我希望我能得到答案。提前谢谢。
您应该使用Trie。尝试是已知最快的排序算法之一（burstsort）的基础，它也用于拼写检查，并用于使用文本完成的应用程序。您可以在此处查看详细信息。
实际上，如果您想进行自动建议，那么最多存储3-4个字符就足够了。我的意思是，当用户键入"a"、"ab"或"abc"时，当他键入"abcd"或更多字符时，您可以使用以"abcd"开头的map.keys，使用c#语言支持的lamda表达式。
因此，我建议创建一个地图，如：映射<char，<映射<char，映射<char，设置<字符串>>>>>映射；所以，若用户输入"a"，你们会查找map[a]并找到所有的子项。