¿Cómo calculo la distancia de edición de árbol?

Question

Necesito calcular la distancia de edición entre árboles para un proyecto personal mío. El documento This describe un algoritmo, pero no puedo sacarle cara o cruz. ¿Conoce algún recurso que describa un algoritmo aplicable de una manera más accesible? Pseudocódigo o código también sería útil.

Answer 1

Aquí hay algunos java source code (tarball con gzip en la parte inferior) para un algoritmo Tree Edit Distance que podría ser útil para usted.

La página incluye referencias y algunas diapositivas que pasan por el algoritmo "Zhang y Shasha" paso a paso y otros enlaces útiles para ponerlo al día.

Editar: Si bien esta respuesta fue aceptada porque apuntaba al algoritmo de Zhang-Shasha, el código en el enlace tiene errores. Steve Johnson y tim.tadh han proporcionado working Python code. Ver Steve Johnson's comment para más detalles.

Answer 2

Creo que solo está buscando el camino más corto entre dos vértices. Si es así, puede usar Dijkstra's algorithm. (La página de wikipedia tiene un seudocódigo para que pueda consultar).

Answer 3

Hay una versión del diario del documento ICALP2007 al que hace referencia en http://www.wisdom.weizmann.ac.il/~oweimann/Publications/TEDinTALG.pdf Esta versión también tiene un pseudocódigo.

Answer 4

Hay muchas variaciones de la distancia de edición del árbol. Si puede ir con la distancia de edición desde arriba hacia abajo, lo que limita las inserciones y elimina las hojas, le sugiero que pruebe el siguiente artículo: http://portal.acm.org/citation.cfm?id=671669&dl=GUIDE&coll=GUIDE&CFID=68408627&CFTOKEN=54202965. La implementación es una matriz de programación dinámica directa con costo O (n2).

Answer 5

(Editado esta respuesta para enlazar a la versión actual de la aplicación dada por tim.tadh)

biblioteca

Este Python implementa el algoritmo de Zhang-Shasha correctamente: https://github.com/timtadh/zhang-shasha

Comenzó como un puerto directo de la fuente Java enumerada en la respuesta actualmente aceptada (la que tiene el enlace tarball), pero esa implementación es no correcta y es casi imposible de ejecutar en absoluto.

Answer 6

Aquí encontrará las implementaciones de Java del árbol de editar algoritmos distancia:

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

Además de algoritmo de 1989 de Zhang & Shasha, también existen implementaciones árbol de distancia de edición de algoritmos más recientes, incluyendo Klein 1998, Demaine et al. 2009, y el algoritmo robusto árbol Editar Distancia (rted) por Pawlik & Augsten, 2011.

Answer 7

escribí una implementación (https://github.com/hoonto/jqgram.git) basado en el código Python pygram existente (https://github.com/Sycondaman/PyGram) para aquellos de ustedes que deseen utilizar el árbol de edición aproximación de distancia utilizando el algoritmo PQ-Gram en el navegador y/o en Node.js.

El módulo de aproximación de distancia de edición del árbol jqgram implementa el algoritmo PQ-Gram para las aplicaciones del lado del servidor y del lado del navegador; Tiempo de O (n log n) y O (n) rendimiento de espacio donde n es el número de nodos.Consulte el documento académico del que proviene el algoritmo: (http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf)

La aproximación de PQ-Gram es mucho más rápida que obtener la distancia de edición verdadera a través de Zhang & Shasha, Klein o Guha et. al, que proporcionan algoritmos de distancia de edición verdadera que todos realizan un mínimo de tiempo O (n^2) y, por lo tanto, a menudo son inadecuados.

A menudo en las aplicaciones del mundo real no es necesario conocer la distancia de edición verdadera si se puede obtener una aproximación relativa de varios árboles a un estándar conocido. Javascript, en el navegador y ahora en el servidor con la llegada de Node.js, trata con frecuencia las estructuras de árbol y el rendimiento del usuario final suele ser crítico en la implementación y el diseño de algoritmos; por lo tanto, jqgram.

Ejemplo:

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

Tenga en cuenta que los parámetros de LFN y CFN especifican cómo cada árbol debe determinar los nombres de las etiquetas de nodo y la matriz niños para cada raíz del árbol de forma independiente para que pueda hacer las cosas cobardes como comparar un objeto a un DOM de navegador por ejemplo. Todo lo que necesita hacer es proporcionar esas funciones junto con cada raíz y jqgram hará el resto, llamando a las funciones proporcionadas por lfn y cfn para construir los árboles. Entonces, en ese sentido, es (en mi opinión, de todos modos) mucho más fácil de usar que PyGram. Además, es Javascript, ¡así que úsela cliente o servidor!

Ahora, un enfoque que puede utilizar es usar jqgram o PyGram para obtener algunos árboles que están cerca y luego usar un algoritmo de distancia de edición real contra un conjunto de árboles más pequeño, ¿por qué gastar todos los cálculos en los árboles? ya puede determinar fácilmente son muy distantes, o viceversa. Entonces puedes usar jqgram para restringir las opciones también.

Espero que el código ayude a algunas personas.

Answer 8

Hice un simple envoltorio pitón (apted.py) para el algoritmo APTED usando jpype si alguien está interesado:

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