部分子树匹配算法

Question

我在论坛上搜索过，但如果其他类似的问题并不一定与这个问题有关，我就无法理解了。

我想做的是将子树与对象树匹配。

我知道基于后缀树或自动机的模式匹配算法，但我不确定它们是否适用于此处。

我试图将图片中的红色节点表示的子树与更大的树进行匹配，而不考虑树的整体结构或红色节点是否具有子节点。

直接的模式匹配不起作用的原因是节点的顺序（后序/前序，宽度）都不能使用。

因此，我打算编写一个递归算法，从子树的根开始，尝试匹配节点及其子节点。

我想知道是否存在任何这样的（高效算法）。 如果已经问过了，请见谅。

- Bogdan B

---

你想要做什么还不是非常清楚。也许你可以提供示例输入和预期输出来帮助阐明？ - Antimony

树中的节点是对象，比如说A、B、C...它们可以根据其属性进行比较，因此我们有了排序和相等性。预期输入是类似于上面红色部分的片段以及完整的树。预期输出是片段在树中被发现的位置。 - Bogdan B

Answer 1

这里有几个可能会对你有帮助的参考资料：

Aho的 高效树模式匹配：代码生成辅助

斯坦福大学的 树模式匹配程序

来自IMECS 2011：使用简明数据结构的树模式匹配算法

- Doug Currie

Answer 2

我似乎需要的是解决“树包含问题”的算法。我找到了一些有用的文档：

寻找最近公共祖先的快速算法

树包含问题：在最优空间和更快的时间内解决

树同构及相关问题

我将最后一篇论文中的一个算法翻译成了C#（返回a和b的一级子树之间最大匹配对数）。

public static int Match(Node a, Node b, NodeSimilarityComparer comp) {
  if (!comp.Equals(a, b))
    return 0;
  int m = a.SubtreeCount;
  int n = b.SubtreeCount;
  var matrix = new int[m + 1, n + 1];

  for (int i = 0; i <= m; ++i)
    matrix[i, 0] = 0;

  for (int j = 0; j <= n; ++j)
    matrix[0, j] = 0;

  for (int i = 1; i <= m; ++i)
    for (int j = 1; j <= n; ++j) {
      var ai = a.GetSubtree(i - 1);
      var bj = b.GetSubtree(j - 1);
      var match = Match(ai, bj, comp);
      matrix[i, j] = Math.Max(Math.Max(matrix[i, j - 1], matrix[i - 1, j]), matrix[i - 1, j - 1] + match);
    }
  return matrix[m, n] + 1;
}

希望这也能帮助其他人。

- Bogdan B