algorithm - para - ¿Cómo calculo la distancia de edición del árbol?

distancia de levenshtein sql

Question

Necesito calcular la distancia de edición entre árboles para un proyecto personal mío. This artículo describe un algoritmo, pero no puedo hacer caras ni colas. ¿Conoce algún recurso que describa un algoritmo aplicable de una manera más accesible? El pseudocódigo o el código también serían útiles.

Answer 1

(Edite esta respuesta para vincular a la versión actual de la implementación dada por tim.tadh)

Esta biblioteca de Python implementa el algoritmo 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 no es correcta y es casi imposible de ejecutar.

Answer 2

Aquí encontrará implementaciones Java de algoritmos de distancia de edición de árbol:

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

Además del algoritmo de Zhang & Shashas de 1989, también hay implementaciones a distancia de edición de árbol de algoritmos más recientes, como Klein 1998, Demaine et al. 2009, y el algoritmo Robust Tree Edit Distance (RTED) de Pawlik & Augsten, 2011.

Answer 3

Aquí hay algo de código fuente de Java (archivo comprimido comprimido con gzipped en la parte inferior) para un algoritmo de distancia de edición de árbol que podría ser útil para usted.

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

Edit: Si bien esta respuesta fue aceptada porque apuntaba al algoritmo Zhang-Shasha, el código en el enlace tiene errores. Steve Johnson y tim.tadh han proporcionado código Python de trabajo . Vea el comentario de Steve Johnson para más detalles.

Answer 4

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

Answer 5

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

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

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

A menudo, en las aplicaciones del mundo real, no es necesario conocer la verdadera distancia de edición 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 fundamental en la implementación y diseño de algoritmos; así 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 lfn y cfn especifican cómo cada árbol debe determinar los nombres de las etiquetas de nodo y la matriz secundaria para cada raíz de árbol de manera independiente, de modo que pueda hacer cosas extrañas, como comparar un objeto con un DOM del 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. Así que en ese sentido es (en mi opinión) mucho más fácil de usar que PyGram. Además, es Javascript, así que úsalo del lado del cliente o del servidor.

Ahora, un enfoque que puede usar 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 más pequeño de árboles, ¿por qué gastar todo el cálculo en árboles que ya puede determinar fácilmente? Son muy lejanos, o viceversa. Así que puedes usar jqgram para reducir las opciones también.

Espero que el código ayude a algunas personas.

Answer 6

Hay muchas variaciones de la distancia de edición del árbol. Si puede ir con la distancia de edición de árbol de arriba a abajo, que limita las inserciones y elimina las hojas, le sugiero que pruebe el siguiente documento: 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 y directa con un costo de O (n2).

Answer 7

Hay una versión de diario del artículo de ICALP2007 que consulta en http://www.wisdom.weizmann.ac.il/~oweimann/Publications/TEDinTALG.pdf Esta versión también tiene un pseudocódigo.

Answer 8

Hice un envoltorio de python simple (apted.py) para el algoritmo jpype utilizando 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
''''''