algorithm - 大量模式的数据结构

Question

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

例如，模式是这样的:

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

输入是一个最少 2 位最多 18 位的数字，我们需要从数据结构中找到最长的匹配模式，并在末尾提取 bool 值。

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

我的答案是使用一棵树，并在每一层都有一个 key value 对列表。键是数字，值是 null 或等于 bool 值，具体取决于它是否是模式的结尾。喜欢:

# 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

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

In computer science, a trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest. For the space-optimized presentation of prefix tree, see compact prefix tree.

特别是紧凑型前缀树或 patricia trie 似乎很适合您的问题。

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

在这个 SO 问题中讨论了 Aho Corasick algorithm

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