algorithm - 如何将一棵树与大量模式进行匹配？

Question

我有一组可能无限的符号:A, B, C, ...还有一个独特的特殊占位符符号 ? (其含义将在下文解释)。

考虑非空有限树，每个节点都有一个符号附加到它和 0 个或多个非空子树。给定节点的子树的顺序很重要(因此，例如，如果有一个节点有 2 个子树，我们可以区分哪个是左的，哪个是右的)。任何给定的符号都可以出现在树中 0 次，附加到不同的节点。占位符号 ?只能附加到叶节点(即没有子树的节点)。根据树的通常定义，树是无环的。

有限性要求是指一棵树的节点总数是一个有限正整数。由此可见，附加符号的总数、树的深度和每棵子树的节点总数都是有限的。

树以功能符号给出:节点由附加到它的符号表示，如果有任何子树，则其后跟包含以逗号分隔的子树列表的括号，这些子树递归地表示在同一方式。所以，例如树

                    A
                   / \
                  ?   B
                     / \
                    A   C
                   /|\
                  A C Q
                       \
                        ?

表示为 A(?,B(A(A,C,Q(?)),C)) .

我有一组预先计算好的不变的树 S 将用作匹配的模式。该集合通常有 ~ 10⁵ 树，它的每个元素通常有 ~ 10-30 个节点。我可以使用大量时间来预先创建最适合我下面所述问题的任何 S 表示。

我需要编写一个函数来接受树 T(通常有 ~ 10² 个节点)并尽快检查是否 T 包含 S 的任何元素作为子树，前提是任何带有占位符符号 ? 的节点匹配任何非空子树(当它出现在 T 或 S 的元素中时)。

请建议存储集合S 的数据结构和检查匹配的算法。任何编程语言或伪代码都可以。

Answer 1

This paper描述了 Aho–Corasick algorithm 的变体，其中该算法没有使用有限状态机(标准 Aho–Corasick 算法用于字符串匹配)，而是使用下推自动机进行子树匹配。与 Aho-Corasick 字符串匹配算法一样，它们的变体只需要通过输入树一次即可匹配 S 的整个字典。

论文相当复杂 - 可能值得 contact the author看看他是否有可用的源代码。