查找最长的词典。短语中的关键匹配

Question

我有一个 SortedDictionary，按密钥长度降序排列，格式为：

• 红狐 - 地址1
• 黄鼠狼 - 地址2
• 狐狸 - 地址3
• 狐狸 - 地址3 等等
  和短语列表，例如
  “今天红狐狸回家了”
  “今天没有狐狸”
  等等

我需要找到字典中与给定短语中的子字符串匹配的最长键的值。 鉴于字典有大约一千个条目，有没有比暴力搜索更好的方法？

上面的例子应该返回：
“红狐”-地址1
“狐狸” - 地址3
我有迭代键的强力解决方案，但考虑到键的数量以及需要在数十个短语中执行搜索，我正在寻找一种更聪明的方法。

Answer 1

从您的要求来看，暴力方法确实不是最好的方法。更有效的方法是使用“Trie”（前缀树）类型。使用“Trie”可以帮助您有效地搜索给定短语中最长的匹配键。 只需创建一个“Tire”结构，然后将“SortedDictionary”中的每个键插入“Trie”中。 “Trie”结构中的每个节点将代表键的一个字符。在每个键的末尾，存储相应的值（地址）。 对于最长匹配的搜索，您可以实现如下： 对于每个短语，迭代每个子字符串并在“Trie”结构中搜索它。不仅仅是跟踪为每个短语找到的最长匹配。 我相信这正是您所需要的。