在有根、标记、有向树中查找所有子树重复
Finding all subtree repeats in a rooted, labeled, directed tree
对于我目前正在进行的研究项目，我需要做的任务之一如下：给定一个有根、有标签、有向的树，我需要找到所有 子树在此树中重复；换句话说，给定 all 树的子树（至少有一个节点），我需要将具有相同标签集的所有子树组合在一起 and同样的层次结构。因此，例如，假设我们有以下树，根 A:
A
/ \
/ \
B A
|\ |\
C C B A
|
C
在这种情况下，有几个重复的子树模式，例如下面...
模式 1（出现 3 次）：
A
|
B
|
C
模式 2（出现 3 次）：
A
|\
B A
|
C
模式 3（出现 2 次）：
A
|
B
...等等等等。仅供参考，我关心的 "rooted, labeled, directed tree" 是从 JavaScript 代码生成的抽象语法树 (AST)。
现在，我想出了自己的算法来查找所有子树重复项。当 JavaScript 代码非常小（因为 AST 也很小）时它工作得很好，并且算法立即完成。但是当我将 JavaScript 代码的行数增加到只有 10 行时，算法甚至在一个多小时后都没有执行完！ 所以我的问题是，有人知道找到所有子树重复的更有效和可扩展的算法吗？ 仅供参考，我实现此算法所用的语言也是 JavaScript。
供您参考，我当前的算法基本上是一种递归算法，它对树进行 post 次遍历（其中 post 次序在此上下文中意味着 "visit the children of this node first, then visit the node" ).在每次访问节点时，该算法通过遍历算法先前确定的其子树的每个组合，找到以该节点为根的所有子树；对于它找到的以该节点为根的每个子树，该算法基于三件事计算哈希值：（1）节点的标签； (2) 在这棵子树中出现的节点的子节点个数； (3) 当前出现在该子树中的子树的哈希值。然后将散列为相同值的子树放在同一组中。 （散列函数的潜在不准确性也需要解决，但我什至还没有涉及到那部分...）。
您正在尝试重新发明抽象语法树中的克隆检测。是的，匹配树的基本思想是使用哈希将它们放入 "possibly-equivalent" 个桶中，然后检查那些可能等价的树是否实际等价。这是用于支持查找公共子表达式的经典编译器算法。
如果等效子树的数量与散列桶的数量相比较小，并且您的散列算法不错，那么这在树的大小上基本上是线性的。 （糟糕的散列或一个桶可以使它成为 N^2）。
我不太明白你的算法；听起来你基本上就是这样做的。如果没有更精确的表征（例如，伪代码），将很难看出问题所在。
研究已久。请参阅我关于 CloneDR 的技术论文，这是一种执行此操作的工具：http://www.semanticdesigns.com/Company/Publications/ICSM98.pdf（您可以在同一站点找到 JavaScript CloneDR）。
找到几乎相同的子树是一个更困难的问题，本文也涵盖了这一点。这是迄今为止最有趣的部分，
并且更难做到快速。
我们定期 运行 数百万行系统上的 CloneDR。在这种规模下，它确实需要数小时才能完成其并行的、编译为本机代码的实现。 JavaScript 可能不是你的朋友。
对于我目前正在进行的研究项目，我需要做的任务之一如下：给定一个有根、有标签、有向的树，我需要找到所有 子树在此树中重复；换句话说，给定 all 树的子树（至少有一个节点），我需要将具有相同标签集的所有子树组合在一起 and同样的层次结构。因此，例如，假设我们有以下树，根 A:
A
/ \
/ \
B A
|\ |\
C C B A
|
C
在这种情况下，有几个重复的子树模式，例如下面...
模式 1（出现 3 次）：
A | B | C
模式 2（出现 3 次）：
A |\ B A | C
模式 3（出现 2 次）：
A | B
...等等等等。仅供参考，我关心的 "rooted, labeled, directed tree" 是从 JavaScript 代码生成的抽象语法树 (AST)。
现在，我想出了自己的算法来查找所有子树重复项。当 JavaScript 代码非常小（因为 AST 也很小）时它工作得很好，并且算法立即完成。但是当我将 JavaScript 代码的行数增加到只有 10 行时，算法甚至在一个多小时后都没有执行完！ 所以我的问题是，有人知道找到所有子树重复的更有效和可扩展的算法吗？ 仅供参考，我实现此算法所用的语言也是 JavaScript。
供您参考，我当前的算法基本上是一种递归算法，它对树进行 post 次遍历（其中 post 次序在此上下文中意味着 "visit the children of this node first, then visit the node" ).在每次访问节点时，该算法通过遍历算法先前确定的其子树的每个组合，找到以该节点为根的所有子树；对于它找到的以该节点为根的每个子树，该算法基于三件事计算哈希值：（1）节点的标签； (2) 在这棵子树中出现的节点的子节点个数； (3) 当前出现在该子树中的子树的哈希值。然后将散列为相同值的子树放在同一组中。 （散列函数的潜在不准确性也需要解决，但我什至还没有涉及到那部分...）。
您正在尝试重新发明抽象语法树中的克隆检测。是的，匹配树的基本思想是使用哈希将它们放入 "possibly-equivalent" 个桶中，然后检查那些可能等价的树是否实际等价。这是用于支持查找公共子表达式的经典编译器算法。
如果等效子树的数量与散列桶的数量相比较小，并且您的散列算法不错，那么这在树的大小上基本上是线性的。 （糟糕的散列或一个桶可以使它成为 N^2）。
我不太明白你的算法；听起来你基本上就是这样做的。如果没有更精确的表征（例如，伪代码），将很难看出问题所在。
研究已久。请参阅我关于 CloneDR 的技术论文，这是一种执行此操作的工具：http://www.semanticdesigns.com/Company/Publications/ICSM98.pdf（您可以在同一站点找到 JavaScript CloneDR）。
找到几乎相同的子树是一个更困难的问题，本文也涵盖了这一点。这是迄今为止最有趣的部分， 并且更难做到快速。
我们定期 运行 数百万行系统上的 CloneDR。在这种规模下，它确实需要数小时才能完成其并行的、编译为本机代码的实现。 JavaScript 可能不是你的朋友。