如何使用字符串列表进行查找？

我有一个字符串列表（一个List<String>），可以有1到6个条目的任何地方。我希望能够做的就是使用该字符串列表进行查找，但是我希望可能的查找能够使用2个或更多这些字符串的任意组合来执行查找。目前我正在使用Dictionary<List<String>, String>。如何使用字符串列表进行查找？

ex。假设我的名单中有以下内容：“火”，“航空”，“雷声”，“水”，“暴风雪”和我在我的字典以下条目：

List<String>(){"fire", "aero"}, "searing wind" 
List<String>(){"fire", "aero", "thunder"} "firestorm" 
List<String>(){"aero", "thunder"}, "storm" 
List<String>(){"aero", "water", "blizzard"}, "snowstorm" 
List<String>(){"aerora", "blizzara"}, "hailstorm"

希望查找返回前4个条目，因为我的基础列表包含查找它们所需的所有值。我还需要能够知道使用哪些值进行查找，因为稍后需要从基本列表中清除这些值。字典中的条目数可能会大约为400

我可以想到一个详尽的方法来执行此查找，但是因为执行查找时顺序将很重要的事实，所以它会花费时间做出所有的排列并查找它们。如果可以帮助，我可以在字典键列表中强制执行字母顺序。有没有人知道有更好的方法来做到这一点，或者是另一种更有效的方式来做到这一点？我已经在这个程序中使用sqlite的一些其他的东西，所以如果这将让我更快的查找我可以使用它。

感谢

来源

2011-02-28 Megatron

一种选择你可能想探索将使用decision tree。这个想法会是这样的。选择一些任意字符串，然后将所有集合分成两组 - 包含该字符串的组和不包含该字符串的组。然后，在这两个组上递归地重复这个过程，并根据你所做的所有决定构建一棵树。例如，下面我们来介绍一种简写为您的符号：

A =航空

R = Aerora

F =火

T =雷霆

W =水

B = Blizzard

然后你可以建立一个树是这样的：

start --> A? -- NO --> R? -- YES --> B? -- YES --> "hailstorm" 
      | 
      +--- YES --> F? -- YES --> T? -- YES --> "firestorm" 
          |    | 
          |    +----- NO --> "searing wind" 
          | 
          +----- NO --> T? -- YES --> "storm" 
             | 
             +----- B? -- YES --> "snowstorm"

一旦你有这样的树，你可以在你的属性存储为一组字符串，然后查找所有匹配如下。从树的根开始，查看给定节点指示的字符串。如果该字符串包含在您的字符串集合中，则递归地继续执行YES分支并查找该树部分中的所有匹配。然后，无论您是否查看该分支，都可以查看NO分支以获取可能与您的查询匹配的所有其他字符串。

这种方法的优点是，假设您有少量字符串作为关键字，树的深度可以非常小 - 对于k个关键字最多为O（k） - 所以在最好的情况下，您的搜索只需要O（k）时间。在最坏的情况下，你只需要探索整个树，这需要时间O（n）。而且，使用机器学习技术，可以构建一个非常好的树形结构，在大小和查找速度之间进行权衡。

希望这会有所帮助！

来源

2011-02-28 01:58:32 templatetypedef

如何使用字符串列表进行查找？

回答

相关问题