Détecter des différences entre les structures en arbre

Vous n'étiez pas clair, si vous étiez la comparaison de l'arbre de syntaxe abstraite pour le code source, les documents XML interprétées comme des arbres, ou d'un autre type d'arbre.

Il y a un certain nombre de textes portant sur la comparaison de l'arbre de syntaxe et de calcul des distances minimales par divers moyens. Les idées doivent être pertinentes.

Un papier de bonne qualité est Changement De Distillation, qui tente de comparer le code source pour les deux l'arbre de syntaxe abstraite et de signaler une différence minime. Le livre parle d'une méthode spécifique, et également breifly mentionne (et fournit des références) à une variété de techniques similaires.

Quelques-uns de ces algorithmes sont effectivement réalisés dans les outils disponibles pour la comparaison du texte source. Notre Smart Differencer est l'un d'entre eux.

Dans le cas de gens trouvent cette question et besoin de quelque chose de mis en œuvre pour Node.js ou le navigateur, je suis en fournissant un lien et un exemple de code pour une application que j'ai écrit que vous pouvez trouver sur github ici: ( https://github.com/hoonto/jqgram.git ), fondés sur le PyGram code Python (https://github.com/Sycondaman/PyGram).

C'est un arbre d'une distance d'édition rapprochement algorithme, mais il est beaucoup, beaucoup plus rapide que d'essayer de trouver la véritable distance d'édition. Le rapprochement effectue en O(n log n) en temps et O(n) l'espace alors que la vraie distance d'édition est souvent O(n^3) ou O(n^2) à l'aide d'algorithmes connus pour la vraie distance d'édition. Voir le document académique à partir de laquelle le PQ-Gramme de l'algorithme, il vient: (http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf)

Donc à l'aide d'jqgram:

Exemple:

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

Et qui vous donne un nombre entre 0 et 1. Le plus proche de zéro, plus étroitement liés les deux arbres à jqgram. Une solution pourrait être d'utiliser jqgram à l'étroit dans plusieurs étroitement liés arbres, parmi de nombreux arbres, compte tenu de sa vitesse, puis utiliser la vraie distance d'édition sur les quelques arbres restants que vous avez besoin de prendre un coup d'inspection, et pour que vous puissiez trouver python implémentations de référence ou le port de la Zhang & Shasha algorithme par exemple.

Noter que le lfn et cfn paramètres spécifient la façon dont chaque arbre doit déterminer l'étiquette du nœud noms et les enfants de tableau pour chaque racine de l'arbre de façon indépendante, de sorte que vous pouvez faire des choses funky comme comparer un objet à un navigateur DOM par exemple. Tout ce que vous devez faire est de fournir à ces fonctions avec chaque racine et jqgram fera le reste, en appelant votre lfn et cfn fonctions fournies pour construire les arbres. Donc, dans ce sens, il est (à mon avis en tout cas) beaucoup plus facile à utiliser que PyGram. De Plus, son Javascript, afin de l'utiliser côté client ou côté serveur!

AUSSI, pour répondre à l'égard de cycle de détection, découvrez la méthode clone à l'intérieur de jqgram, il y a le cycle de détection de là, mais le crédit pour cela va à l'auteur de nœud-clone à partir de laquelle cette pièce a été légèrement modifiée, et inclus.