algorithm - 部分的なサブツリー マッチング アルゴリズム

Question

フォーラムを検索しましたが、他の同様の質問が必然的にこの質問に関連しているかどうかわかりませんでした。

私がやろうとしているのは、サブツリーをオブジェクトのツリーに一致させることです。

接尾辞ツリーまたはオートマトンに基づくパターン マッチング アルゴリズムがあることは知っていますが、それらがここに適用されるかどうかはわかりません。

ツリーの全体的な構造や赤いノードに子があるかどうかに関係なく、図の赤いノードで指定されたサブツリーをより大きなツリーと一致させようとしています。

単純なパターン マッチングが機能しない理由は、ノードの順序付け (post/preorder、幅) が使用できないためです。

そのため、サブツリーのルートから開始し、ノードとその子を照合しようとする再帰アルゴリズムを作成することを考えています。

そのような（効率的なアルゴリズム）が存在するかどうか疑問に思っていました。これがすでに尋ねられている場合はお詫び申し上げます。

Answer 1

以下に、役立つ参考資料をいくつか示します。

Aho の効率的なツリー パターン マッチング: コード生成の補助

スタンフォードの木のパターン マッチング プログラム

IMCS 2011 より:簡潔なデータ構造を使用したツリー パターン マッチング アルゴリズム

Answer 2

私が探していたのは、「ツリー包含問題」を解決するためのアルゴリズムだったようです。私はいくつかの有用な文書を見つけました:

最も近い共通の祖先を見つけるための高速アルゴリズム

ツリー包含問題: 最適な空間でより高速に

ツリー同型と関連する問題

前回の論文のアルゴリズムの 1 つを C# に翻訳しました (a と b の第 1 レベルのサブツリー間で最大一致するペアの数を返します)。

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

これが他の人にも役立つことを願っています。