Определить различия между древовидными структурами

Это вопрос CS, но интересный:

Скажем, у нас есть две древовидные структуры с более или менее одинаковыми реорганизациями узлов. Как бы вы нашли

любой
в некотором смысле минимальный

последовательность операций

MOVE(A, B) - перемещается node A под node B (со всем поддеревом)
INSERT(N, B) - вставляет новый node N под node B
DELETE (A) - удаляет node A (со всем поддеревом)

который преобразует одно дерево в другое.

Вероятно, могут быть случаи, когда такое преобразование невозможно, тривиальным является корень A с потомком B с корнем B с дочерним элементом A и т.д.). В таких случаях алгоритм просто доставляет результат "невозможно".

Еще более впечатляющая версия - это обобщение для сетей, т.е. когда мы предполагаем, что node может встречаться несколько раз в дереве (эффективно имея несколько "родителей" ), в то время как циклы запрещены.

Отказ от ответственности: это не домашнее задание, на самом деле оно исходит из реальной бизнес-проблемы, и мне было очень интересно узнать, может ли кто-нибудь узнать о решении.

Ответ 1

Существует не только статья Википедии об изоморфизме графа (как указывает Space_C0wb0y), но также специальная статья о проблеме о изоморфизме графа. Он имеет раздел Solved special cases, для которого известны решения полиномиального времени. Деревья - один из них, и он приводит следующие две ссылки:

P.J. Келли, "Теорема сравнений для деревьев" Pacific J. Math., 7 (1957), стр. 961-968
Ахо, Альфред В.; Хопкрофт, Джон; Ульман, Джеффри Д. (1974), "Дизайн и анализ компьютерных алгоритмов", "Чтение", М.: Эддисон-Уэсли.

Ответ 2

Вам было не ясно, сравниваете ли вы абстрактные синтаксические деревья для исходного кода, XML-документы, интерпретируемые как деревья, или какой-то другой тип дерева.

Существует ряд статей, в которых обсуждается сравнение синтаксических деревьев и вычисление минимальных расстояний различными способами. Идеи должны быть релевантными.

Хорошая статья Изменить дистилляцию, которая пытается сравнить исходный код для двух абстрактных деревьев синтаксиса и сообщить о минимальной разнице. В документе говорится о конкретном методе, а также кратко упоминается (и дается ссылка) на множество подобных методов.

Немногие из этих алгоритмов фактически реализованы в доступных инструментах для сравнения исходного текста. Наш Smart Differencer является одним из них.

Ответ 3

Хотя этот вопрос старый, я добавлю еще несколько ссылок и алгоритмов ниже:

Кроме того, в GitHub (в javascript) есть библиотеки и фреймворки, которые реализуют различение древовидных структур, например приложений, работающих с данными JSON или XML-деревьями (например, для MVC/MVVM на стороне клиента):

Ответ 4

В случае, если люди находят этот вопрос и нуждаются в чем-то, что реализовано для Node.js или браузера, я предоставляю пример ссылки и кода для реализации, которую я написал, которую вы можете найти в github здесь: (https://github.com/hoonto/jqgram.git) на основе существующего кода PyGram Python (https://github.com/Sycondaman/PyGram).

Это алгоритм приближения расстояния к дереву, но он намного быстрее, чем поиск истинного расстояния редактирования. Аппроксимация выполняется в O (n log n) времени и O (n) пространстве, тогда как истинное расстояние редактирования часто O (n ^ 3) или O (n ^ 2), используя известные алгоритмы для истинного расстояния редактирования. См. Академическую статью, из которой следует алгоритм PQ-Gram: (http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf)

Итак, используя jqgram:

Пример:

var jq = require("jqgram").jqgram;
var root1 = {
    "thelabel": "a",
    "thekids": [
        { "thelabel": "b",
        "thekids": [
            { "thelabel": "c" },
            { "thelabel": "d" }
        ]},
        { "thelabel": "e" },
        { "thelabel": "f" }
    ]
}

var root2 = {
    "name": "a",
    "kiddos": [
        { "name": "b",
        "kiddos": [
            { "name": "c" },
            { "name": "d" },
            { "name": "y" }
        ]},
        { "name": "e" },
        { "name": "x" }
    ]
}

jq.distance({
    root: root1,
    lfn: function(node){ return node.thelabel; },
    cfn: function(node){ return node.thekids; }
},{
    root: root2,
    lfn: function(node){ return node.name; },
    cfn: function(node){ return node.kiddos; }
},{ p:2, q:3 },
function(result) {
    console.log(result.distance);
});

И это дает вам число от 0 до 1. Чем ближе к нулю, тем более тесно связаны два дерева в jqgram. Один из подходов может заключаться в том, чтобы использовать jqgram для сужения на нескольких тесно связанных деревьях из многих деревьев с учетом его скорости, а затем использовать истинное расстояние редактирования на немногих оставшихся деревьях, которые вам нужно для более тщательного изучения, и для этого вы можете найти python реализации для ссылки или порт алгоритма Чжан и Шаши, например.

Обратите внимание, что параметры lfn и cfn определяют, как каждое дерево должно определять имена ярлыков node и дочерний массив для каждого корня дерева независимо друг от друга, чтобы вы могли делать смешные вещи, например, сравнение объекта с DOM браузера. Все, что вам нужно сделать, это предоставить эти функции вместе с каждым корнем, а jqgram сделает все остальное, вызвав ваши lfn и cfn предоставленные функции для создания деревьев. Так что в этом смысле это (по-моему, так или иначе) гораздо проще в использовании, чем PyGram. Кроме того, его Javascript, так что используйте его клиент или сервер!

ТАКЖЕ, чтобы ответить на вопрос об обнаружении цикла, проверьте метод clone внутри jqgram, там есть обнаружение цикла, но кредит для этого принадлежит автору node -clone, из которого эта часть была слегка изменена и включен.