Comment puis-je calculer l'arbre de distance d'édition?

Voici quelques le code source java (format tarball en bas) pour un Arbre de Distance d'Édition de l'algorithme qui peut être utile pour vous.

La page inclut des références et des diapositives qui vont par le biais de la "Zhang et Shasha" algorithme étape-par-étape et d'autres liens utiles pour vous obtenir jusqu'à la vitesse.

Edit: Alors que cette réponse a été acceptée parce qu'elle a souligné la Zhang-Shasha algorithme, le code dans le lien a des bugs. Steve Johnson et tim.tadh ont fourni travail code Python. Voir Steve Johnson commentaire pour plus de détails.

J'ai écrit une mise en œuvre ( https://github.com/hoonto/jqgram.git ), fondés sur le PyGram code Python (https://github.com/Sycondaman/PyGram) pour ceux d'entre vous qui souhaitent utiliser l'arborescence de la distance d'édition approximation à l'aide de PQ-Gramme de l'algorithme dans le navigateur et/ou dans Node.js.

La jqgram arbre de distance d'édition rapprochement module implémente le PQ-Gramme algorithme pour à la fois côté serveur et côté navigateur applications; O(n log n) en temps et O(n) l'espace performant où n est le nombre de nœuds. Voir le document académique à partir de laquelle l'algorithme, il vient: (http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf)

Le PQ-Gramme rapprochement est beaucoup plus rapide que l'obtention de la vraie distance d'édition par Zhang & Shasha, Klein, ou Guha et. al, qui assurent la distance d'édition algorithmes à tous d'effectuer un minimum de O(n^2) 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 relatif rapprochement de plusieurs arbres à une norme connue peut être obtenue. Javascript dans le navigateur et maintenant sur le serveur avec l'avènement de Node.js traiter souvent avec les structures en arbre et de la performance de l'utilisateur final est généralement critique dans l'implémentation de l'algorithme et de design, 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);
});

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!

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 algorithme edit distance contre un plus petit ensemble d'arbres, pourquoi dépenser de tous les calculs sur les arbres, vous pouvez déjà déterminer facilement, sont très éloignés, ou vice versa. Ainsi, vous pouvez utiliser jqgram pour affiner le choix.

Espère que le code permet à certains gens.

J'ai fait un simple wrapper python (apted.py) pour la APTED algorithme à l'aide de 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 y a beaucoup de variations de l'arbre à une distance d'édition. Si vous pouvez aller avec de haut en bas de l'arborescence de distance d'édition, ce qui limite les insertions et les suppressions à la laisse, je vous propose d'essayer le document suivant: http://portal.acm.org/citation.cfm?id=671669&dl=GUIDE&coll=GUIDE&CFID=68408627&CFTOKEN=54202965. La mise en œuvre est simple de la matrice de programmation dynamique avec O(n2) coût.