大量模式的数据结构

Question

在一次采访中,我被要求提出可以容纳数百万个模式的数据结构,并通过它们快速搜索以找到最长的匹配模式.

例如,模式如下:

1- 8876 8893 87          | true
2- 8876 889              | false
3- 8876 8                | false
4- 887                   | true

输入是一个至少有2位且最多18位的数字,我们需要从数据结构中找到最长的匹配模式,并在结尾处提取布尔值.

例如,8876 8893 9943 53将匹配1并true返回.8876 8397 5430 74将匹配3并false返回.

我的回答是使用一棵树并key value在每个级别都有一个对列表.作为数字和值的键是null或等于boolean,具体取决于它是否是模式的结尾.喜欢:

# matching 8875
# start the search by first digit
[..., (7, null), (8, null), (9, null)] 
                  ^
                 [..., (7, null), (8, null), (9, null)] 
                                   ^
                                   [..., (7, true), (8, null), ...]
# at the last step because we don't have a pattern 
# to match the digit 5, we return the `true` from (7, true)

具有挑战性的部分是,模式非常多.数以百万计.这有什么好处吗？如果没有,你的建议是什么.

Answer 1

一个非常好的数据结构，非常适合您描述的问题，即一个集合结构，其中许多条目共享一个公共前缀（和/或后缀），并且您基于共享前缀执行搜索的地方是Trie。

\n\n

\n

在计算机科学中，特里树，也称为数字树，有时也称为基数树或前缀树（因为它们可以通过前缀搜索），是一种有序树数据结构，用于存储动态集或关联数组，其中键通常是字符串。与二叉搜索树不同，树中没有节点存储与该节点关联的键；相反，它在树中的位置定义了与其关联的键。节点的所有后代都有与该节点关联的字符串的公共前缀，并且根与空字符串关联。值通常不与每个节点相关联，仅与叶节点和一些与感兴趣的键相对应的内部节点相关联。有关前缀树的空间优化表示，请参阅紧凑前缀树。

\n

\n\n

具体来说，紧凑的前缀树或帕特里夏特里似乎很适合您的问题。

\n\n

鉴于提到的尝试类型通常用于存储与键关联的值，如果您的问题不需要这样做（即您不需要存储输入模式字符串的原始索引并在搜索时返回该索引），则有是一个密切相关的解决方案，可能更适合。正如 @JimMischel 在评论中指出的，Aho\xe2\x80\x93Corasick 字符串匹配算法构建了一个类似于 trie 的结构，在内部节点之间具有附加链接。如果要匹配的模式集是固定的，并且数据结构已构建，那么对于搜索，其运行时间与输入长度加上匹配条目的数量呈线性关系。

\n\n

在这个SO问题Aho Corasick算法中讨论了它

\n\n

您可以在线找到它的一些实现，例如C#或Java或Haskell。

\n