Come si calcola la distanza di modifica dell'albero?

Question

Ho bisogno di calcolare la distanza di modifica tra gli alberi per un mio progetto personale. This la carta descrive un algoritmo, ma non riesco a farne testa o croce. Sei a conoscenza di risorse che descrivono un algoritmo applicabile in un modo più accessibile? Anche lo pseudocodice o il codice sarebbero utili.

Answer 1

Ecco alcuni java source code (tarball gzipped nella parte inferiore) per un algoritmo Tree Edit Distance che potrebbe essere utile.

La pagina include riferimenti e alcune diapositive che eseguono l'algoritmo "Zhang e Shasha" passo dopo passo e altri collegamenti utili per aggiornarsi.

Modifica: Mentre questa risposta è stata accettata perché indica l'algoritmo di Zhang-Shasha, il codice nel collegamento presenta bug. Steve Johnson e tim.tadh hanno fornito working Python code. Vedi Steve Johnson's comment per maggiori dettagli.

Answer 2

Penso che tu stia solo cercando il percorso più breve tra due vertici. In tal caso, è possibile utilizzare Dijkstra's algorithm. (La pagina di wikipedia ha uno pseudocodice su cui puoi fare riferimento.)

Answer 3

C'è una versione di giornale della carta ICALP2007 a cui si fa riferimento a http://www.wisdom.weizmann.ac.il/~oweimann/Publications/TEDinTALG.pdf Questa versione ha anche uno pseudocodice.

Answer 4

Ci sono molte variazioni della distanza di modifica dell'albero. Se si può andare con la distanza di modifica dell'albero top-down, che limita gli inserimenti e cancella le foglie, suggerisco di provare il seguente documento: http://portal.acm.org/citation.cfm?id=671669&dl=GUIDE&coll=GUIDE&CFID=68408627&CFTOKEN=54202965. L'implementazione è una matrice di programmazione dinamica semplice con costo O (n2).

Answer 5

(A cura questa risposta per collegare alla versione corrente di attuazione data dal tim.tadh)

biblioteca

Questa Python implementa l'algoritmo Zhang-Shasha correttamente: https://github.com/timtadh/zhang-shasha

E 'iniziato come una porta diretta della sorgente Java elencata nella risposta attualmente accettata (quella con il collegamento tarball), ma l'implementazione è non corretta ed è quasi impossibile da eseguire.

Answer 6

Qui potete trovare implementazioni Java di albero di modifica algoritmi distanza:

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

Oltre a algoritmo di Zhang & Shasha del 1989, ci sono anche le implementazioni albero di modificare a distanza di algoritmi più recenti, tra cui Klein del 1998, Demaine et al. 2009 e l'algoritmo robusto albero Modifica Distanza (ari) da Pawlik & Augsten, 2011.

Answer 7

ho scritto un'implementazione (https://github.com/hoonto/jqgram.git) sulla base del codice esistente PyGram Python (https://github.com/Sycondaman/PyGram) per quelli di voi che desiderano utilizzare albero di modifica approssimazione della distanza usando l'algoritmo PQ-Gram nel browser e/o in Node.js.

Il modulo di approssimazione della distanza di modifica dell'albero jqgram implementa l'algoritmo PQ-Gram per entrambe le applicazioni lato server e lato browser; O (n log n) tempo e O (n) spazio performante dove n è il numero di nodi.Vedi il documento accademico da cui proviene l'algoritmo: (http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf)

L'approssimazione PQ-Gram è molto più veloce di ottenere la vera distanza di modifica tramite Zhang & Shasha, Klein, o Guha et. al, che forniscono veri algoritmi di modifica della distanza che eseguono tutti un tempo minimo di O (n^2) e sono quindi spesso inadatti.

Spesso nelle applicazioni del mondo reale non è necessario conoscere la vera distanza di modifica se è possibile ottenere un'approssimazione relativa di più alberi a uno standard noto. Javascript, nel browser e ora sul server con l'avvento di Node.js si occupano spesso di strutture ad albero e le prestazioni degli utenti finali sono generalmente fondamentali nell'implementazione e nella progettazione dell'algoritmo; quindi jqgram.

Esempio:

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

Nota che i parametri LFN e CFN specificano come ogni albero dovrebbe determinare i nomi delle etichette del nodo e la matrice dei bambini per ogni radice di un albero in modo indipendente in modo che si possono fare cose funky come paragonare un oggetto per esempio con un DOM del browser. Tutto quello che devi fare è fornire queste funzioni insieme a ciascuna radice e jqgram farà il resto, chiamando le funzioni lfn e cfn fornite per costruire gli alberi. Quindi in questo senso è (secondo me comunque) molto più facile da usare rispetto a PyGram. Inoltre, è Javascript, quindi usalo client o lato server!

Ora un approccio che è possibile utilizzare è utilizzare jqgram o PyGram per ottenere alcuni alberi che sono vicini e quindi utilizzare un vero algoritmo di modifica della modifica su un insieme più piccolo di alberi, perché spendere tutto il calcolo sugli alberi possono già facilmente determinare sono molto distanti, o viceversa. Quindi puoi usare jqgram anche per limitare le scelte.

Spero che il codice aiuti alcuni fuori.

Answer 8

Ho fatto un semplice involucro python (apted.py) per il APTED algoritmo utilizzando jpype se qualcuno è interessato:

# 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 
'''