algorithm - 部分子树匹配算法

Question

我搜索了论坛，但我无法弄清楚其他类似的问题是否必然与这个问题有关。

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

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

我试图将图片中红色节点给出的子树与更大的树进行匹配，无论树的整体结构或红色节点是否有子节点。

直接模式匹配不起作用的原因是没有可用的节点排序（后/预排序、广度）。

所以我正在考虑编写一个递归算法，它从子树的根开始并尝试匹配节点，然后是它们的子节点。

我想知道是否存在任何这样的（有效的算法）。抱歉，如果这已经被问到了。

Answer 1

以下是一些可能对您有所帮助的参考资料：

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

斯坦福的树模式匹配程序

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

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;
}

希望这对其他人也有帮助。