Unterschiede zwischen Baumstrukturen erkennen

Waren Sie nicht klar, wenn Sie vergleichen abstrakte syntax-Bäume für source-code, XML-Dokumente interpretiert werden, wie Bäume, oder eine andere Art von Baum.

Gibt es eine Reihe von arbeiten, diskutieren, vergleichen syntax Bäume und informatik minimale Distanzen mit verschiedenen Mitteln. Die Ideen relevant sein sollte.

Ein gutes Papier ist Ändern Destillierendas versucht, zu vergleichen Sie den Quellcode mit zwei abstrakte syntax Bäume und berichten von einer minimalen Differenz. Das Papier spricht von einer bestimmten Methode, und auch breifly erwähnt (und Verweise) zu einer Vielzahl von ähnlichen Techniken.

Einige dieser algorithmen sind tatsächlich realisiert verfügbaren tools für den Vergleich von Quell-text. Unsere Smart Differencer ist einer von Ihnen.

InformationsquelleAutor der Antwort Ira Baxter

In Fall Leute finden, die diese Frage und brauche etwas umgesetzt Node.js oder der browser, ich bin mit link und code-Beispiel für eine Implementierung, die ich geschrieben habe, finden Sie auf github hier: (https://github.com/hoonto/jqgram.git) auf der Grundlage der bestehenden PyGram Python-code (https://github.com/Sycondaman/PyGram).

Dies ist eine Baum-edit-Distanz Annäherung Algorithmus, aber es ist viel, viel schneller, als zu versuchen, zu finden, die wahre edit-Distanz. Die Angleichung vollzieht sich in O(n log n) Zeit und O(n) Platz in der Erwägung, dass wahre edit-Distanz ist oft O(n^3) oder O(n^2) mit den bekannten algorithmen für echte edit-Distanz. Siehe das wissenschaftliche paper, aus dem die PQ-Gram-Algorithmus kommt: (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 dir eine Zahl zwischen 0 und 1. Je näher an null, je mehr eng verwandt, die beiden Bäume sehen zu jqgram. Ein Ansatz könnte sein, zu verwenden jqgram zu eng auf einige eng stehende Bäume, unter vielen Bäumen, angesichts der Geschwindigkeit, dann nutzen Sie wahre edit-Distanz auf die wenigen verbleibenden Bäume, die Sie benötigen, um einen genaueren Inspektion, und für die, die Sie finden können python-Implementierungen für Referenz-oder port des Zhang & Shasha-Algorithmus für Beispiel.

Beachten Sie, dass der lfn und cfn Parameter geben an, wie jeder Baum sollte bestimmen die Knoten-Bezeichnungen und die Kinder-array für jede Baumwurzel unabhängig voneinander, so dass Sie tun können, funky Sachen wie der Vergleich eines Objekts zu einem browser-DOM zum Beispiel. Alles, was Sie tun müssen, ist, bieten diese Funktionen zusammen mit jeder Wurzel und jqgram werden den rest tun, indem Sie mit Ihrer lfn und cfn zur Verfügung stehenden Funktionen zu bauen die Bäume. Also in diesem Sinne ist es (meiner Meinung nach jedenfalls) viel leichter zu bedienen als PyGram. Plus, die Javascript verwenden, so ist es der client oder der server-Seite!

AUCH, zu beantworten, mit Bezug auf Zyklus-Erkennung, überprüfen Sie heraus die clone-Methode innerhalb von jqgram, es ist Zyklus-Erkennung gibt, aber die credit dafür geht an den Autor der node-Klon, von dem dieses Stück leicht modifiziert wurde und im Lieferumfang enthalten.

InformationsquelleAutor der Antwort hoonto