Если люди найдут этот вопрос и ему понадобится что-то для 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 определяют, как каждыйtree должен определять имена меток узла и дочерний массив для каждого корня дерева независимо, так что вы можете делать такие интересные вещи, как, например, сравнение объекта с DOM браузера.Все, что вам нужно сделать, это предоставить эти функции вместе с каждым корнем, а jqgram сделает все остальное, вызвав предоставленные вами функции lfn и cfn для построения деревьев.Так что в этом смысле (на мой взгляд, в любом случае) его гораздо проще использовать, чем PyGram.Кроме того, это Javascript, так что используйте его на стороне клиента или на стороне сервера!
ТАКЖЕ, чтобы ответить относительно обнаружения циклов, проверьте метод клонирования внутри jqgram, там есть обнаружение циклов, но заслуга в этом идетавтору узла-клона, из которого эта часть была слегка изменена и включена.