javascript - 在有根、标记、有向树中查找所有子树重复

Question

对于我目前正在进行的研究项目，我需要做的任务之一如下:给定一个有根、有标签、有向的树，我需要找到所有子树重复 在这棵树中；换句话说，给定所有树的子树(至少有一个节点)，我需要将具有相同标签集的所有子树分组和相同的层次结构结构。因此，例如，假设我们有以下树，其根为 A:

    A   / \  /   \ B     A |\    |\ C C   B A       |       C

在这种情况下，有几个重复的子树模式，例如下面...

模式 1(出现 3 次):

A|B|C

模式 2(出现 3 次):

A|\B A|C

模式 3(出现 2 次):

A|B

...等等等等。仅供引用，我关心的“有根、有标签、有向树”是从 JavaScript 代码生成的抽象语法树 (AST)。

现在，我想出了自己的算法来查找所有子树重复项。当 JavaScript 代码非常小(因为 AST 也很小)时它工作得很好，并且算法立即完成。但是当我将 JavaScript 代码的行数增加到只有 10 行时，算法甚至在一个多小时后都没有执行完! 所以我的问题是，有没有人知道找到所有子树重复的更有效和可扩展的算法？仅供引用，我实现此算法的语言也是 JavaScript。

供您引用，我目前的算法基本上是一种递归算法，它对树进行后序遍历(这里的后序意味着“先访问该节点的子节点，然后访问该节点”) .在每次访问节点时，该算法通过遍历算法早期确定的其子树的每个组合，找到以该节点为根的所有子树；对于它找到的以该节点为根的每个子树，该算法基于三件事计算哈希值:(1)节点的标签； (2)在这棵子树中出现的节点的子节点个数； (3) 当前出现在该子树中的子树的哈希值。。然后将散列为相同值的子树放在同一组中。 (散列函数的潜在不准确性也需要解决，但我什至还没有涉及到那部分......)。

Answer 1

您正在尝试重新发明抽象语法树中的克隆检测。是的，匹配树的基本思想是使用散列将它们放入“可能等价”的桶中，然后检查那些可能等价的树是否实际等价。这是用于支持查找公共(public)子表达式的经典编译器算法。

如果等效子树的数量与散列桶的数量相比较小，并且您的散列算法不错，那么这在树的大小上基本上是线性的。 (糟糕的散列或一个桶可以使它成为 N^2)。

我不太明白你的算法；听起来你基本上就是这样做的。如果没有更精确的特征(例如，伪代码)，将很难看出问题所在。

这项研究早就完成了。请参阅我关于 CloneDR 的技术论文，这是一种执行此操作的工具:http://www.semanticdesigns.com/Company/Publications/ICSM98.pdf (您可以在同一站点找到 JavaScript CloneDR)。

找到几乎相同的子树是一个更困难的问题，该论文也涵盖了这一点。这是迄今为止最有趣的部分，并且更难做到快速。

我们定期在数百万行的系统上运行 CloneDR。在这种规模下，它确实需要数小时才能完成其并行的、编译为 native 代码的实现。 JavaScript 可能不是你的 friend 。