如何将树与大量模式匹配？

Question

我有一组潜在的无限符号: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的数据结构和检查匹配的算法.任何编程语言或伪代码都可以.

Answer 1

本文描述了Aho-Corasick算法的一种变体,其中不使用有限状态机(标准Aho-Corasick算法用于字符串匹配),而是使用下推自动机进行子树匹配.与Aho-Corasick字符串匹配算法一样,它们的变体只需要一次通过输入树来匹配整个S字典.

这篇论文非常复杂 - 可能值得联系作者,看看他是否有任何可用的源代码.