Oblicz minimalne operacje, aby dwie struktury drzewiaste były identyczne

To jest bardziej pytanie dotyczące CS, ale interesujące:

Powiedzmy, że mamy 2 struktury drzewiaste z mniej więcej tymi samymi zreorganizowanymi węzłami. Jak byś znalazł

1. każdy
2. w pewnym sensie minimalne

kolejność operacji

• MOVE(A, B) - przenosi węzeł A pod węzeł B (z całym poddrzewem)
• INSERT(N, B)- wstawia nowy węzeł N pod węzłem B
• DELETE (A) - usuwa węzeł A (wraz z całym poddrzewem)

która przekształca jedno drzewo w drugie.

Mogą oczywiście zaistnieć przypadki, w których taka transformacja nie jest możliwa, trywialne jest to, że root A z dzieckiem B jest rootem B z dzieckiem A itd.). W takich przypadkach algorytm po prostu dałby wynik „ niemożliwy ”.

Jeszcze bardziej spektakularna wersja jest uogólnieniem dla sieci, tj. Kiedy zakładamy, że węzeł może występować wielokrotnie w drzewie (efektywnie mając wielu „rodziców”), a cykle są zabronione.

Zastrzeżenie: to nie jest praca domowa, w rzeczywistości pochodzi z prawdziwego problemu biznesowego i uznałem to za całkiem interesujące, zastanawiając się, czy ktoś może znać rozwiązanie.

Jest nie tylko artykuł w Wikipedii o izomorfizmie grafów (jak wskazuje Space_C0wb0y), ale także artykuł poświęcony problemowi izomorfizmu grafów . Ma sekcję, Solved special casesdla której znane są rozwiązania wielomianowe. Drzewa jest jednym z nich i cytuje następujące dwa odniesienia:

• PJ Kelly, "A congruence theorem for trees" Pacific J. Math., 7 (1957) str. 961–968
• Aho, Alfred V .; Hopcroft, John; Ullman, Jeffrey D. (1974), The Design and Analysis of Computer Algorithms, Reading, MA: Addison – Wesley.

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

Istnieje wiele artykułów omawiających porównywanie drzew składniowych i obliczanie minimalnych odległości różnymi metodami. Pomysły powinny być trafne.

Dobrym artykułem jest Change Distilling , który próbuje porównać kod źródłowy dwóch abstrakcyjnych drzew składniowych i zgłosić minimalną różnicę. Artykuł mówi o konkretnej metodzie, a także zwięźle wspomina (i podaje odniesienia) do różnych podobnych technik.

Niewiele z tych algorytmów jest faktycznie realizowanych w dostępnych narzędziach do porównywania tekstu źródłowego programu komputerowego. Nasz Smart Differencer jest jednym z nich; kieruje się wyraźną gramatyką językową dla wielu języków.

Chociaż to pytanie jest stare, dodam poniżej kilka dodatkowych odniesień i algorytmów:

1. X-Diff: skuteczny 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 dokumentach XML w wielu wersjach
4. Wykrywanie zmian w drzewach XML: ankieta, Luuk Peters
5. Podobieństwo w strukturach danych drzewa

Ponadto istnieją biblioteki i frameworki na GitHub (w javascript), które implementują różnicowanie struktur przypominających drzewo, na przykład aplikacje obsługujące dane JSON lub drzewa XML (np. Dla MVC / MVVM po stronie klienta):

1. React.js
2. Poprawka JSON
3. jsondiffpatch
4. objectDiff

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.

Nazywa się to problemem korygowania drzewa do drzewa lub problemem edycji drzewa do drzewa . Większość literatury zajmującej się tym bezpośrednio odnosi się do porównywania drzew XML z jakiegoś powodu, więc wyszukanie „algorytmu różnicującego XML” daje wiele wyników. Oprócz listy linków Nikosa znalazłem te:

• Drobnoziarniste wykrywanie zmian w dokumentach z tekstem strukturalnym (2014)
• Wykrywanie zmian według poziomu (CDL): skuteczny algorytm do wykrywania zmian w dokumentach XML (2010)
• Porównanie dokumentów XML jako uporządkowanych drzew z etykietami uwzględniającymi odniesienia (2011) Kod do tego - VTracker nadal istnieje! Edycja: w rzeczywistości interesujący fragment kodu nie jest uwzględniony. To wskazało mi ...
• UMLDiff: An Algorithm for Object-Oriented Design Difference (2005).
• Powrót do odległości edycji drzewa i jego śledzenia wstecznego: Samouczek (2018) - wygląda jak dobry tutorial dla algorytmu Zhang-Shashy, który wydaje się być "klasycznym" rozwiązaniem, ale ma straszną złożoność czasową, ponieważ porównuje każde poddrzewo z co inne poddrzewo.

Polecam również przeczytanie lektury Wykrywanie zmian w drzewach XML: ankieta ale pochodzi z 2005 r., Więc prawie żadne z wymienionych narzędzi już nie istnieje. Porównywanie dokumentów XML jako uporządkowanych drzew z etykietami uwzględniającymi odnośniki daje najbardziej intuicyjny opis niektórych algorytmów, jakie do tej pory znalazłem (zacznij od sekcji 2.1.2).

Niestety wydaje się, że nie ma zbyt wielu dostępnych kodów open source, które to robią i nie są starożytne. Tylko wiele zbyt skomplikowanych dokumentów. : - /