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

Question

我有一个字符串列表(List<String>)，可以包含 1 到 6 个条目。我想要做的是使用该字符串列表进行查找，但我希望可能的查找能够使用 2 个或更多这些字符串的任意组合来进行查找。我用的是 Dictionary<List<String>, String>目前。

例如。假设我的列表中有以下内容:“fire”、“aero”、“thunder”、“water”、“blizzard”并且我的字典中有以下条目:

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 来处理其他一些东西，所以如果那能让我更快地进行查找，我可以使用它。

谢谢

Answer 1

您可能想要探索的一个选项是使用 decision tree .这个想法是这样的。选择一些任意字符串，然后将所有集合分成两组 - 包含该字符串的组和不包含该字符串的组。然后，对两个组递归地重复此过程，并根据您所做的所有决定构建一棵树。例如，让我们为您的符号介绍一个简写形式:

A = 航空

R = 空气

F = 火

T = 雷声

W = 水

B = 暴雪

然后你可以像这样构建一棵树:

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)。此外，使用机器学习技术，可以构建一个非常好的树结构，该结构将在大小和查找速度之间进行可靠的权衡。

希望这对您有所帮助!