产品名称字符串与树匹配（支持省略）

Question

我有一个 CPU 型号列表。现在，我认为最合适的方法是从列表中形成一个特里，如下所示：

Intel -- Core -- i -- 3
      |       |    |- 5
      |       |    |- 7
      |       |    -- 9
      |       |
      |       -- 2 Duo
      |
      |- Xeon -- ...
      |
      |...

现在，我想将输入字符串与此树进行匹配。这对于精确匹配很容易，但是如果我需要一个模糊的匹配，字符串序列可以有遗漏怎么办？对于“Intel i3”，“Core i3”和“i3”都匹配到树中的“Intel -> Core -> i -> 3”。

对于这个问题，尝试是正确的任务吗？我想过使用带通配符的特里搜索，但这里的通配符可以在序列中的任何位置。

我可以使用什么数据结构以最适用于这个问题的方式来表示列表？我使用什么算法进行搜索？

Answer 1

虽然我不确定它是该任务的最佳数据结构，但您可以使用增强特里树，其中每个节点都与每个后代都有直接链接。显然你会想要比线性搜索更好的（trie根将有一个到每个其他节点的链接），并且你还必须处理重复项，但是只要你的深度合理（这对于 CPU 型号来说应该如此）。这看起来像：

class TrieAugmented:

    def __init__(self, val: str):
        self.val = val
        self.children = []
        self.child_paths = {}

添加 CPU 模型时，新节点照常附加到子节点列表中，但必须在每个新节点的每个祖先节点上更新子路径（添加时间为 O(d^2) 而不是 O(d)，其中 d是深度）。我会将child_paths节点后代值映射到具有该值的节点列表self.children或将其存储在 child_paths 中。如果您计划构建一个静态 trie，然后查询它，则可以构建该 trie，并且仅像往常一样更新直接子节点，然后再在一次深度优先遍历 trie 中添加所有较短路径。每个节点占用 O(d) 空间而不是常量，因此总的来说，这类似于 O(n^2) 空间而不是线性空间，但这对于相对较小的项目集来说应该是可行的。

如果存储和实现复杂性比运行时更重要，您可以使用未增强的 trie。这使得运行时在 trie 节点数量上呈线性，而不是在输入大小上大致呈线性，但它与将文件系统路径与任意嵌套结构匹配非常相似。在rust glob语法中，您可以将您的 trie 转换"Core i3"为"/**/Core/**/i/**/3"文件系统并将其视为文件系统（实际上，您确实在序列中的每个位置插入通配符，并且它们可以匹配 trie 的任意多个级别）。这里的 trie 不会使查找太快，但确实可以将省略的模型与其完全指定的版本进行匹配。