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

81

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.

Tomas Vana
źródło
MOVE(A,B)wydaje się być taki sam, INSERT(A,B)jakby Anie miał dzieci. Co dzieje się z dziećmi, Ajeśli tak się stanie INSERT(A,B)? (czy będą przywiązani do Arodzica?)
Andre Holzner
różnica polega na tym, że INSERT oznacza naprawdę nowy węzeł, który wcześniej nie znajdował się w drzewie (a zatem nie miał żadnych dzieci, przynajmniej nie w oryginalnym stanie, w którym nie był nawet obecny). Z drugiej strony MOVE to tak naprawdę ruch, czyli ruch węzła łącznie z jego dziećmi
Tomas Vana
11
Wygląda na to, że musisz wykryć izomorfizm wykresu . Część dotycząca transformacji przypomina mi odległość Levenshteina , którą można zgrabnie rozwiązać w O (n * m) za pomocą programowania dynamicznego. Może te wskazówki ci pomogą.
Björn Pollex
Czy kiedykolwiek wymyśliłeś rozwiązanie? Patrząc na artykuł na Wikipedii i odnośniki do linków, nigdzie nie widzę algorytmu. Chciałbym to zrobić w javascript, gdzie znam już oryginalne operacje, które spowodowały, że dwa drzewa się różniły, ale chciałbym utworzyć opcjonalną różnicę: na przykład, jeśli część drzewa została przycięta, a następnie ponownie przeszczepiona w to samo miejsce zoptymalizowałoby się bez zmian.
Michael
@Michael, znalazłeś coś przydatnego? Obserwuję ten sam alhoritm redukcji zmian w drzewie.
Pavel

Odpowiedzi:

25

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:

Andre Holzner
źródło
16

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.

Ira Baxter
źródło
2
Właściwie w naszym przypadku to nie jest kod źródłowy, to naprawdę są drzewa. W tych drzewach jest jakaś semantyczna, ale w sumie nie tak ważna - są bezpośrednio manipulowane przez użytkowników jako drzewo
Tomas Vana
Zepsuty link: Właśnie spędziłem 20 minut na poszukiwaniu artykułu „Change Distilling”. Oto zaktualizowany link: merlin.uzh.ch/publication/show/2531 Sam projekt oprogramowania został przeniesiony na bitbucket.org/sealuzh/tools-changedistiller/wiki/Home (w ten sposób otrzymałem poprawny link do pliku PDF)
Shalom Craimer
13

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
Nikos M.
źródło
Gorąco polecam przeczytanie Change Detection in XML Trees: a Surveyartykułu - zawiera on listę dziesiątek algorytmów porównywania XML (czyli porównywania drzewem).
Timmmm,
8

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.

hoonto
źródło
czy to pozwala na wiele lfn? Chcę dopasować więcej niż etykieta, tj. również wartość przechowywana. node.value.
john ktejik
0

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:

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. : - /

Timmmm
źródło
Nie widzę tego dokumentu, czy łącze do pliku PDF jest uszkodzone? Change Detection in XML Trees: a Survey
Mengo
Pracuje dla mnie. Czy kliknąłeś Download full-test PDFprzycisk? Może wypróbuj Sci-hub, jeśli z jakiegoś powodu jest zablokowany.
Timmmm