Wykrywanie różnic między strukturami drzew

Nie było jasne, czy porównujesz abstrakcyjne drzewa składniowe dla kodu źródłowego, dokumentów XML interpretowanych jako drzewa, czy innego typu drzewa.

Istnieje wiele artykułów, które omawiają porównywanie drzew składniowych i obliczanie minimalnych odległości za pomocą różnych środków. Pomysły powinny być istotne.

Dobrym artykułem jest Change Distilling, który próbuje porównać kod źródłowy dla dwóch abstrakcyjnych drzew składniowych i zgłosić minimalną różnicę. W artykule omówiono konkretny metoda, a także breifly wspomina (i podaje odniesienia) do różnych podobnych technik.

Kilka z tych algorytmów jest faktycznie realizowanych w dostępnych narzędziach do porównywania tekstu źródłowego. Nasz Smart Differencer jest jednym z nich.

Chociaż to pytanie jest stare, dodam jeszcze kilka referencji i algorytmów poniżej:

1. X-Diff: efektywny algorytm wykrywania zmian w dokumentach XML, Yuan Wang, David J. DeWitt, Jin-Yi CAI
2. KF-Diff+: wysoce wydajny algorytm wykrywania zmian w dokumentach XML
3. diffX: algorytm wykrywania zmian w wielu wersjach Dokumenty XML
4. wykrywanie zmian w drzewach XML: ankieta, Luuk Peters
5. podobieństwo w Tree Data Structures

Ponadto istnieją biblioteki i frameworki na Githubie (w javascript), które implementują różnice w tree-podobnych strukturach na przykład aplikacji zajmujących się danymi JSON lub drzewami XML (np. dla MVC/MVVM po stronie klienta):

1. reaguj.js
2. JSON-Patch
3. jsondiffpatch
4. objectDiff

Na wypadek, gdyby ludzie znaleźli to pytanie i potrzebowali czegoś zaimplementowanego dla Node.js lub przeglądarka, podaję link i przykład kodu dla implementacji, którą napisałem, którą można znaleźć na GitHubie tutaj: ( https://github.com/hoonto/jqgram.git ) na podstawie istniejącego kodu Pythona PyGram ( https://github.com/Sycondaman/PyGram).

Jest to algorytm przybliżenia odległości edycji drzewa , ale jest to znacznie szybsze niż próba znalezienia prawdziwej odległości edycji. Na przybliżenie odbywa się w czasie o (n log n) 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 prawdziwej odległości edycji. Zobacz artykuł, 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ę z zakresu od 0 do 1. Im bliżej zera, tym bliżej spokrewnione oba drzewa wyglądają na jqgram. Jedno podejście może być użycie jqgram, aby zawęzić kilka blisko spokrewnionych drzew spośród wielu drzew, biorąc pod uwagę jego szybkość, a następnie wykorzystać prawdziwą odległość edycji na kilku pozostałych drzewach, które musisz przyjrzeć się bliżej, i za to można znaleźć implementacje Pythona dla odniesienia lub portu algorytmu Zhang & Shasha na przykład.

Zauważ, że parametry lfn i CFN określają, w jaki sposób każde drzewo powinno określać nazwy etykiet węzłów i tablicę Potomków dla każdego korzenia drzewa niezależnie, więc że możesz robić dziwne rzeczy, takie jak porównywanie obiektu do DOM przeglądarki na przykład. Wszystko, co musisz zrobić, to dostarczyć te funkcje wraz z każdym korzeniem, a jqgram zrobi resztę, wywołując funkcje LFN i CFN, aby zbudować drzewa. W tym sensie jest więc (moim zdaniem) znacznie łatwiejszy w użyciu niż PyGram. Plus, jego Javascript, więc używać go po stronie klienta lub serwera!

Ponadto, aby odpowiedzieć w odniesieniu do wykrywania cyklu, sprawdź metodę klonowania wewnątrz jqgram, jest tam wykrywanie cyklu, ale za to zasługa autora node-clone, z którego ten kawałek został nieco zmodyfikowany i dołączony.