大量模式的数据结构

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或布尔值，具体取决于它是否是模式的结尾。像这样：

# 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)

挑战在于，这些模式非常多。有数百万种。这有好处吗？如果没有，您有什么建议。

- paytonpy

---

@Alex，纯金啊。有时一个单词就能开启新世界。非常感谢。如果你想发布它作为答案，我甚至会接受它。 - paytonpy

好的，我会将它作为答案添加，并允许问题通过接受的答案来“关闭”。 - Alex

Answer 1

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

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

具体来说，紧凑前缀树或patricia trie似乎非常适合您的问题。

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

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

您可以在网上找到一些实现，例如C#、Java或Haskell。

- Alex

---

Aho-Corasick字符串搜索算法构建了一个非常相似的数据结构，并且可以快速地进行搜索。看起来这是解决这个问题的完美方案。 - Jim Mischel

是的，这似乎更适合这个特定的问题（因为“键”不需要包含关联值）。我会在答案中添加参考。 - Alex

Answer 2

你可以考虑实现wu-manber，它编码简单且内存效率高。

- ravan