Алгоритм частичного совпадения поддеревьев

Question

Я искал форумы, но я не мог понять, если другие подобные вопросы обязательно связаны с этим.

Я пытаюсь сопоставить поддерево с деревом объектов.

Я знаю, что существуют алгоритмы сопоставления с образцом, основанные на суффиксных деревьях или автоматах, но я не уверен, применимы ли они здесь.

Я пытаюсь сопоставить поддерево, данное красными узлами на изображении, с большим деревом, независимо от общей структуры дерева или от того, есть ли у красных узлов дочерние элементы или нет.

Причина, по которой прямое сопоставление с образцом не работает, состоит в том, что никакое упорядочение узлов (post/preorder, width) не может быть использовано.

Поэтому я думаю о написании рекурсивного алгоритма, который начинается с корня поддерева и пытается сопоставить узлы, а затем их дочерние элементы.

Мне было интересно, существует ли такой (эффективный алгоритм). Извиняюсь, если об этом уже спрашивали.

Answer 1

Похоже, что я искал алгоритм для решения "проблемы включения дерева". Я нашел несколько полезных документов:

Быстрые алгоритмы поиска ближайших общих предков

Проблема включения дерева: в оптимальном пространстве и быстрее

Изоморфизм деревьев и связанные с ним проблемы

Я перевел один из алгоритмов из последней статьи на 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;
}

Надеюсь, что это помогает другим.

Answer 2

Вот несколько ссылок, которые могут вам помочь:

Эффективное сопоставление с образцом дерева Aho : помощь в генерации кода

Программы сопоставления с образцом дерева Стэнфорда

Из IMECS 2011: алгоритм сопоставления шаблонов дерева с использованием краткой структуры данных