与 trie 匹配的产品名称字符串（支持遗漏）

Question

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

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

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

尝试是解决这个问题的正确任务吗？想过用带通配符的trie搜索，但是这里的通配符可以在序列的任意位置

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

Answer 1

虽然我不确定它是否是任务的最佳数据结构，但您可以使用增强的特里树，其中每个节点都直接 links 到每个后代。显然你会想要比线性搜索更好的（trie 根对每个其他节点都有一个 link），而且你还必须处理重复项，但只要你的深度，内存成本应该没问题是合理的（对于 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) space 而不是常量，因此总体而言这类似于 O(n^2) space 而不是线性的，但这对于相对较小的项目集应该是可行的。

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

与 trie 匹配的产品名称字符串（支持遗漏）

Product name string matching against a trie (supporting omissions)

search

string-matching

string-search

data-structures