局部子树匹配算法 [英] Partial subtree-matching algorithm

问题描述

我搜索了这些论坛，但是如果其他类似的问题必然与此论坛有关，我无法弄清楚.

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

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

我试图将图中红色节点给出的子树与较大的树进行匹配，而不管树的整体结构或红色节点是否有子节点.

直接模式匹配不起作用的原因是，节点的排序(后期/预排序，广度)将不可用.

因此，我正在考虑编写一种从子树的根部开始并尝试先匹配节点再匹配其子节点的递归算法.

我想知道是否存在这样的(高效算法).抱歉，如果已经有人问过了.

解决方案

看来，我正在寻找的是一种解决树包含问题"的算法.我找到了一些有用的文件:

用于查找最接近的祖先的快速算法

树包含问题:在最佳空间中且速度更快

树同构和相关问题

我将上一篇论文中的一种算法转换为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;
}

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

I searched the forums but I couldn't figure it out if the other similar questions are necessarily related to this one.

What I'm trying to do is match a subtree to a tree of objects.

I know there are pattern matching algorithms based on suffix trees or automata, but I'm not sure whether they apply here.

I am trying to match the subtree given by the red nodes in the picture against the bigger tree, regardless of the overall structure of the tree or whether the red nodes have children or not.

The reason straightforward pattern matching does not work is that no ordering of the nodes (post/preorder, breadth) will be usable.

So I'm thinking of writing a recursive algorithm that starts from the root of the subtree and tries to match nodes and then their children.

I was wondering if there exists any such (efficient algorithm). Apologies if this has already been asked.

解决方案

It appears that what I was looking for was an algorithm to solve the "tree inclusion problem". I have found some useful documents:

Fast Algorithms for Finding Nearest Common Ancestors

The Tree Inclusion Problem: In Optimal Space and Faster

Tree Isomorphism And Related Problems

I translated one of the algorithms from the last paper into C# (returns the number of pairs in a largest matching between first-level subtrees of a and 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;
}

Hope this helps others too.

这篇关于局部子树匹配算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！