Обнаружение различий между древовидными структурами

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

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

хорошая бумага Изменить Перегонки, который пытается сравнить исходный код для двух абстрактных синтаксических деревьев и отчета минимальной разницей. Бумага говорит о конкретном методе, а также breifly упоминает (и дает ссылки) на различные подобные методы.

немногие из этих алгоритмов фактически реализованы в доступных инструментах для сравнения исходного текста. Наши Умный Дифференциал - один из них.

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

1. X-Diff: эффективный алгоритм обнаружения изменений для XML-документов, Yuan Wang, David J. DeWitt, Jin-Yi Cai
2. KF-Diff+: высокоэффективный алгоритм обнаружения изменений для XML-документов
3. diffX: алгоритм для обнаружения изменений в мульти-версии XML-документы
4. обнаружение изменений в XML Trees: a Survey, Luuk Peters
5. сходство в структуре данных дерева

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

1. реагировать.js
2. JSON-Patch
3. jsondiffpatch
4. objectDiff

в случае, если люди находят этот вопрос и нужно что-то решал для узла.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 для ссылки или порта алгоритма Zhang & Shasha, например.

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

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