Comment calculer la distance d'édition de l'arbre?

(édité cette réponse pour lier à la version actuelle de l'implémentation donnée par tim.tadh)

Cette bibliothèque Python implémente correctement L'algorithme Zhang-Shasha : https://github.com/timtadh/zhang-shasha

Il a commencé comme un port direct de la source Java listée dans la réponse actuellement acceptée (celle avec le lien tarball), mais cette implémentation est incorrecte et est presque impossible à exécuter.

J'ai écrit une implémentation ( https://github.com/hoonto/jqgram.git ) basé sur le code Python PyGram existant ( https://github.com/Sycondaman/PyGram ) pour ceux d'entre vous qui souhaitent utiliser l'approximation de distance d'édition d'arbre en utilisant l'algorithme PQ-Gram dans le navigateur et / ou dans le nœud.js.

Le module d'approximation de distance d'édition de l'arborescence jqgram implémente l'algorithme PQ-Gram pour les applications côté serveur et côté navigateur; O(N log n) temps et O (N) espace performant où n est le nombre de nœuds. Voir l'article académique d'où provient l'algorithme: ( http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf )

L'approximation PQ-Gram est beaucoup plus rapide que l'obtention de la véritable distance d'édition via Zhang & Shasha, Klein ou Guha et. al, qui fournissent de véritables algorithmes de distance d'édition qui effectuent tous un temps O(N^2) minimum et sont donc souvent inadaptés.

Souvent dans les applications réelles, il n'est pas nécessaire de connaître la véritable distance d'édition si un par rapport rapprochement de plusieurs arbres à une norme connue peut être obtenue. Javascript dans le navigateur et maintenant sur le serveur avec l'avènement de Nœud.js traitent fréquemment avec des structures arborescentes et la performance de l'utilisateur final est généralement critique dans la mise en œuvre et la conception de l'algorithme; ainsi 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, depth:10 },
function(result) {
    console.log(result.distance);
});

Notez que les paramètres lfn et cfn spécifient comment chaque arbre doit déterminer les noms d'étiquette de noeud et le tableau enfants pour chaque racine d'arbre indépendamment afin que vous puissiez faire des choses géniales comme comparer un objet à un DOM du navigateur par exemple. Tout ce que vous devez faire est de fournir ces fonctions avec chaque racine et jqgram fera le reste, en appelant vos fonctions fournies par LFN et cfn pour construire les arbres. Donc, en ce sens, il est (à mon avis de toute façon) beaucoup plus facile à utiliser que PyGram. De plus, son Javascript, alors utilisez-le côté client ou serveur!

Maintenant une approche que vous pouvez utiliser est d'utiliser jqgram ou PyGram pour obtenir quelques arbres qui sont à proximité, puis d'utiliser un véritable modifier l'algorithme de distance contre un plus petit ensemble d'arbres, pourquoi dépenser tout le calcul sur les arbres que vous pouvez déjà facilement déterminer sont très éloignés, ou vice versa. Ainsi, vous pouvez utiliser jqgram pour affiner les choix aussi.

J'espère que le code AIDE certaines personnes.

Vous trouverez ici des implémentations Java d'algorithmes de distance d'édition d'arbre:

Http://www.inf.unibz.it/dis/projects/tree-edit-distance

En plus de L'algorithme de Zhang&Shasha de 1989, il existe également des implémentations de distance d'édition d'arbres d'algorithmes plus récents, y compris Klein 1998, Demaine et al. 2009, et l'algorithme robuste Tree Edit Distance (RTED) par Pawlik&Augsten, 2011.

J'ai fait un simple wrapper python (apted.py) pour l'algorithme APTED en utilisant jpype si quelqu'un est intéressé:

# To use, create a folder named lib next to apted.py, then put APTED.jar into it

import os, os.path, jpype 

global distancePackage
distancePackage = None

global utilPackage
utilPackage = None

def StartJVM():
  # from http://www.gossamer-threads.com/lists/python/python/379020
  root = os.path.abspath(os.path.dirname(__file__)) 
  jpype.startJVM(jpype.getDefaultJVMPath(), 
  "-Djava.ext.dirs=%s%slib" % (root, os.sep))
  global distancePackage
  distancePackage = jpype.JPackage("distance")
  global utilPackage
  utilPackage = jpype.JPackage("util")


def StopJVM():
  jpype.shutdownJVM()


class APTED:
  def __init__(self, delCost, insCost, matchCost):
    global distancePackage
    if distancePackage is None:
      raise Exception("Need to call apted.StartJVM() first")
    self.myApted = distancePackage.APTED(float(delCost), float(insCost), float(matchCost))

  def nonNormalizedTreeDist(self, lblTreeA, lblTreeB):
    return self.myApted.nonNormalizedTreeDist(lblTreeA.myLblTree, lblTreeB.myLblTree)


class LblTree:
  def __init__(self, treeString):
    global utilPackage
    if utilPackage is None:
      raise Exception("Need to call apted.StartJVM() first")

    self.myLblTree = utilPackage.LblTree.fromString(treeString)

'''
# Example usage:

import apted
apted.StartJVM()
aptedDist = apted.APTED(delCost=1, insCost=1, matchCost=1)
treeA = apted.LblTree('{a}')
treeB = apted.LblTree('{b{c}}')
dist = aptedDist.nonNormalizedTreeDist(treeA, treeB)
print dist


# When you are done using apted
apted.StopJVM()
# For some reason it doesn't usually let me start it again and crashes python upon exit when I do this so call only as needed
'''

Il existe une version journal de L'article ICALP2007 auquel vous vous référez à http://www.wisdom.weizmann.ac.il/ ~ oweimann / Publications / TEDinTALG.pdf Cette version a également un pseudocode.

Il existe de nombreuses variantes de la distance d'édition de l'arbre. Si vous pouvez aller avec la distance d'édition d'arbre de haut en bas, qui limite les insertions et les suppressions aux feuilles, je suggère d'essayer le papier suivant: http://portal.acm.org/citation.cfm?id=671669&dl=GUIDE&coll=GUIDE&CFID=68408627&CFTOKEN=54202965. la mise en œuvre est une matrice de programmation dynamique simple avec un coût O(n2).

Je pense que vous cherchez juste le chemin le plus court entre deux vertiges. Si c'est le cas, vous pouvez utiliser l'algorithme de Dijkstra. (La page wikipedia a pseudocode sur elle pour vous de vous référer.)