21

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

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

有限性要求意味着树中的节点总数是一个正有限整数。因此，附加符号的总数、树的深度和每个子树中的节点总数都是有限的。

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

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

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

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

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

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

4

2 回答 2

6

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

这篇论文相当复杂 -联系作者看看他是否有任何可用的源代码可能是值得的。

于 2013-06-16T04:24:05.890 回答
4

您需要的是一个有限状态机，它可以跟踪您可能拥有的一组潜在匹配项。

本质上，这样的机器是模式相互匹配的结果，并确定它们共享的个体匹配的部分。这类似于词法分析器如何将一组正则表达式用于标记并将它们组合成一个大型 FSA，该 FSA 可以通过一次处理一个字符来匹配任何正则表达式。

您可以在术语重写系统下找到有关执行此操作的方法的参考。

于 2013-06-16T04:28:52.833 回答