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

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

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

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

Пример

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

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

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

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


matching algorithm subtree
person Bogdan B    schedule 07.07.2012    source источник
comment
До сих пор не ясно, что именно вы пытаетесь сделать. Возможно, вы могли бы добавить примеры входных данных и ожидаемых результатов?   -  person Antimony    schedule 07.07.2012
comment
Узлы в дереве — это объекты, скажем, A, B, C... Их можно сравнивать на основе их атрибутов, поэтому у нас есть порядок и равенство. Ожидаемый ввод — это фрагмент, подобный красному выше, и полное дерево. Ожидаемый результат — это позиции, в которых фрагмент находится в дереве.   -  person Bogdan B    schedule 07.07.2012

Ответы (2)


arrow_upward
3
arrow_downward

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

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

Стэнфордские программы сопоставления древовидных шаблонов

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

person Doug Currie    schedule 07.07.2012

arrow_upward
3
arrow_downward

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

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

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

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

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

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

person Bogdan B    schedule 08.07.2012