Jeśli ludzie znajdą to pytanie i potrzebują czegoś zaimplementowanego dla Node.js lub przeglądarki, podaję link i przykład kodu do implementacji, którą napisałem, którą możesz znaleźć na github tutaj: ( https://github.com /hoonto/jqgram.git ) w oparciu o istniejący kod PyGram Python ( https://github.com/Sycondaman/PyGram ).
To jest odległość edycji drzewa algorytm przybliżenia , ale jest o wiele, dużo szybszy niż próba znalezienia prawdziwej odległości edycji. Przybliżenie jest wykonywane w O (n log n) czasie i O (n) przestrzeni, podczas gdy prawdziwa odległość edycji jest często O (n ^ 3) lub O (n ^ 2) przy użyciu znanych algorytmów dla rzeczywistej odległości edycji. Zobacz artykuł naukowy, z którego pochodzi algorytm PQ-Gram: ( http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf )
Więc używając jqgram:
Przykład:
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);
});
A to daje liczbę od 0 do 1. Im bliżej zera, tym bardziej zbliżone są dwa drzewa do jqgram. Jednym podejściem mogłoby być użycie jqgram do zawężenia kilku blisko spokrewnionych drzew spośród wielu drzew, biorąc pod uwagę jego prędkość, a następnie wykorzystanie rzeczywistej odległości edycji na kilku pozostałych drzewach, które trzeba bliżej przyjrzeć się i do tego można znaleźć pytona implementacje w celach informacyjnych lub port algorytmu Zhang & Shasha na przykład.
Zwróć uwagę, że parametry lfn i cfn określają, w jaki sposób każde drzewo powinno niezależnie określać nazwy etykiet węzłów i tablice potomne dla każdego korzenia drzewa, dzięki czemu możesz robić dziwne rzeczy, takie jak na przykład porównywanie obiektu z DOM przeglądarki. Wszystko, co musisz zrobić, to dostarczyć te funkcje wraz z każdym korzeniem, a jqgram zrobi resztę, wywołując funkcje dostarczone przez lfn i cfn, aby zbudować drzewa. W tym sensie jest (w każdym razie moim zdaniem) znacznie łatwiejszy w użyciu niż PyGram. Plus, jego Javascript, więc używaj go po stronie klienta lub serwera!
TAKŻE, aby odpowiedzieć na temat wykrywania cykli, sprawdź metodę klonowania wewnątrz jqgram, jest tam wykrywanie cykli, ale zasługa tego należy do autora klonu węzła, z którego ten element został nieco zmodyfikowany i uwzględniony.
MOVE(A,B)wydaje się być taki sam,INSERT(A,B)jakbyAnie miał dzieci. Co dzieje się z dziećmi,Ajeśli tak się stanieINSERT(A,B)? (czy będą przywiązani doArodzica?)