search - 产品名称字符串与树匹配(支持省略)

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 中。如果您计划构建一个静态树然后查询它，您可以构建树并且只像往常一样只更新直接子树，然后在一次深度优先遍历树中添加所有较短的路径。每个节点占用 O(d) 空间而不是常数，因此总体而言这类似于 O(n^2) 空间而不是线性空间，但这对于相对较小的项目集应该是可行的。

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