Berechnen Sie minimale Operationen, um zwei Baumstrukturen identisch zu machen

Dies ist eher eine CS-Frage, aber eine interessante:

Angenommen, wir haben zwei Baumstrukturen mit mehr oder weniger denselben Knoten, die neu organisiert wurden. Wie würden Sie finden

1. irgendein
2. in gewissem Sinne minimal

Reihenfolge der Operationen

• MOVE(A, B) - verschiebt Knoten A unter Knoten B (mit dem gesamten Teilbaum)
• INSERT(N, B)- fügt einen neuen Knoten N unter Knoten B ein
• DELETE (A) - löscht den Knoten A (mit dem gesamten Teilbaum)

das verwandelt einen Baum in den anderen.

Es kann offensichtlich Fälle geben, in denen eine solche Transformation nicht möglich ist, trivial ist Wurzel A mit Kind B zu Wurzel B mit Kind A usw.). In solchen Fällen würde der Algorithmus einfach ein Ergebnis " nicht möglich " liefern .

Eine noch spektakulärere Version ist eine Verallgemeinerung für Netzwerke, dh wenn wir annehmen, dass ein Knoten mehrmals im Baum vorkommen kann (effektiv mehrere "Eltern" haben), während Zyklen verboten sind.

Haftungsausschluss: Dies ist keine Hausaufgabe, sondern stammt aus einem echten Geschäftsproblem, und ich fand es ziemlich interessant, mich zu fragen, ob jemand eine Lösung kennen könnte.

Es ist nicht nur ein Wikipedia - Artikel über Graphisomorphie (wie Space_C0wb0y weist darauf hin) , sondern auch ein dedizierter Artikel über das Graphisomorphie Problem . Es hat einen Abschnitt, Solved special casesfür den Polynomzeitlösungen bekannt sind. Trees ist einer von ihnen und zitiert die folgenden zwei Referenzen:

• PJ Kelly, "Ein Kongruenzsatz für Bäume" Pacific J. Math., 7 (1957), S. 961–968
• Aho, Alfred V.; Hopcroft, John; Ullman, Jeffrey D. (1974), Entwurf und Analyse von Computeralgorithmen, Reading, MA: Addison-Wesley.

Sie waren sich nicht sicher, ob Sie abstrakte Syntaxbäume für Quellcode, als Bäume interpretierte XML-Dokumente oder einen anderen Baumtyp verglichen haben.

Es gibt eine Reihe von Artikeln, in denen der Vergleich von Syntaxbäumen und die Berechnung von Mindestabständen auf verschiedene Weise erörtert werden. Die Ideen sollten relevant sein.

Ein gutes Papier ist Change Distilling , das versucht, den Quellcode für zwei abstrakte Syntaxbäume zu vergleichen und einen minimalen Unterschied zu melden. Das Papier spricht über eine bestimmte Methode und erwähnt (und gibt Hinweise) kurz auf eine Vielzahl ähnlicher Techniken.

Nur wenige dieser Algorithmen werden tatsächlich in verfügbaren Tools zum Vergleichen von Computerprogramm-Quelltext realisiert. Unser Smart Differencer ist einer von ihnen; Es basiert auf einer expliziten Sprachgrammatik für viele Sprachen.

Obwohl diese Frage alt ist, werde ich unten ein paar weitere Referenzen und Algorithmen hinzufügen:

1. X-Diff: Ein effektiver Algorithmus zur Erkennung von Änderungen für XML-Dokumente, Yuan Wang, David J. DeWitt, Jin-Yi Cai
2. KF-Diff +: Hocheffizienter Algorithmus zur Änderungserkennung für XML-Dokumente
3. diffX: Ein Algorithmus zum Erkennen von Änderungen in XML-Dokumenten mit mehreren Versionen
4. Änderungserkennung in XML-Bäumen: eine Umfrage, Luuk Peters
5. Ähnlichkeit in Baumdatenstrukturen

Darüber hinaus gibt es auf GitHub Bibliotheken und Frameworks (in Javascript), die unterschiedliche Baumstrukturen implementieren, z. B. Anwendungen, die sich mit JSON-Daten oder XML-Bäumen befassen (z. B. für clientseitiges MVC / MVVM):

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

Falls Leute diese Frage finden und etwas für Node.js oder den Browser implementieren müssen, stelle ich einen Link und ein Codebeispiel für eine Implementierung bereit, die ich geschrieben habe und die Sie auf github hier finden: ( https://github.com /hoonto/jqgram.git ) basierend auf dem vorhandenen PyGram Python-Code ( https://github.com/Sycondaman/PyGram ).

Dies ist ein Algorithmus zur Approximation der Baumbearbeitungsentfernung, der jedoch viel, viel schneller ist als der Versuch, die wahre Bearbeitungsentfernung zu ermitteln. Die Approximation erfolgt in O (n log n) Zeit und O (n) Raum, während die wahre Bearbeitungsentfernung häufig O (n ^ 3) oder O (n ^ 2) ist, wobei bekannte Algorithmen für die wahre Bearbeitungsentfernung verwendet werden. Siehe die wissenschaftliche Arbeit, aus der der PQ-Gram-Algorithmus stammt: ( http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf )

Also mit jqgram:

Beispiel:

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);
});

Und das gibt Ihnen eine Zahl zwischen 0 und 1. Je näher an Null, desto enger sind die beiden Bäume mit jqgram verwandt. Ein Ansatz könnte darin bestehen, jqgram zu verwenden, um mehrere eng verwandte Bäume unter vielen Bäumen aufgrund seiner Geschwindigkeit einzugrenzen, und dann den tatsächlichen Bearbeitungsabstand für die wenigen verbleibenden Bäume zu verwenden, die Sie genauer untersuchen müssen, und dafür finden Sie Python Implementierungen als Referenz oder Port des Zhang & Shasha-Algorithmus zum Beispiel.

Beachten Sie, dass die Parameter lfn und cfn angeben, wie jeder Baum die Knotenbezeichnungsnamen und das untergeordnete Array für jeden Baumwurzel unabhängig bestimmen soll, damit Sie funky Dinge wie den Vergleich eines Objekts mit einem Browser-DOM ausführen können. Alles, was Sie tun müssen, ist, diese Funktionen zusammen mit jeder Wurzel bereitzustellen, und jqgram erledigt den Rest und ruft Ihre von lfn und cfn bereitgestellten Funktionen auf, um die Bäume aufzubauen. In diesem Sinne ist es (meiner Meinung nach jedenfalls) viel einfacher zu bedienen als PyGram. Plus, sein Javascript, also benutze es client- oder serverseitig!

Um auch in Bezug auf die Zykluserkennung zu antworten, überprüfen Sie die Klonmethode innerhalb von jqgram. Dort gibt es eine Zykluserkennung. Dies geht jedoch an den Autor des Knotenklons, von dem das Teil leicht modifiziert und eingeschlossen wurde.

Dies wird als Baum-zu-Baum-Korrekturproblem oder als Baum-zu-Baum-Bearbeitungsproblem bezeichnet . Der größte Teil der Literatur, die sich damit befasst, bezieht sich aus irgendeinem Grund explizit auf den Vergleich von XML-Bäumen. Die Suche nach "XML-Diffing-Algorithmus" liefert daher viele Ergebnisse. Zusätzlich zu Nikos 'Linkliste habe ich folgende gefunden:

• Feinkörnige Änderungserkennung in strukturierten Textdokumenten (2014)
• Änderungserkennung nach Ebene (CDL): Ein effizienter Algorithmus zur Erkennung von Änderungen in XML-Dokumenten (2010)
• Vergleichen von XML-Dokumenten als referenzbewusste beschriftete geordnete Bäume (2011) Der Code dafür - VTracker existiert noch! Bearbeiten: Eigentlich ist das interessante Stück Code nicht enthalten. Das zeigte mir ...
• UMLDiff: Ein Algorithmus zur objektorientierten Designdifferenzierung (2005).
• Überprüfung der Baumbearbeitungsentfernung und ihrer Rückverfolgung: Ein Tutorial (2018) - sieht aus wie ein gutes Tutorial für den Zhang-Shasha-Algorithmus, der die "klassische" Lösung zu sein scheint, aber eine schreckliche zeitliche Komplexität aufweist, da er jeden Teilbaum mit vergleicht jeder andere Unterbaum.

Ich empfehle außerdem dringend, die Änderungserkennung in XML-Bäumen zu lesen : eine Umfrage, aber sie stammt aus dem Jahr 2005, sodass kaum noch eines der genannten Tools vorhanden ist. Der Vergleich von XML-Dokumenten als referenzbewusste beschriftete geordnete Bäume bietet die beste intuitive Beschreibung einiger der Algorithmen, die ich bisher gefunden habe (beginnen Sie mit Abschnitt 2.1.2).

Leider scheint nicht viel Open Source Code verfügbar zu sein, der dies tut und nicht alt ist. Nur eine Menge zu komplexer Papiere. : - /