algorithm tree comparison diff computer-science

algorithm - Detecta diferencias entre las estructuras de los árboles



tree comparison (4)

Esta es más una pregunta CS, pero una interesante:

Digamos que tenemos 2 estructuras de árbol con más o menos los mismos nodos reorganizados. ¿Cómo encontrarías?

  1. alguna
  2. en cierto sentido, mínimo

secuencia de operaciones

  • MOVE(A, B) - mueve el nodo A debajo del nodo B (con todo el subárbol)
  • INSERT(N, B) - inserta un nuevo nodo N debajo del nodo B
  • DELETE (A) - borra el nodo A (con todo el subárbol)

eso transforma un árbol en el otro.

Obviamente, puede haber casos en que dicha transformación no sea posible, siendo trivial la raíz A con el niño B hasta la raíz B con el niño A, etc.). En tales casos, el algoritmo simplemente entregaría un resultado " imposible ".

Una versión aún más espectacular es una generalización para las redes, es decir, cuando suponemos que un nodo puede ocurrir varias veces en el árbol (teniendo efectivamente múltiples "padres"), mientras que los ciclos están prohibidos.

Descargo de responsabilidad: Esta no es una tarea, en realidad proviene de un problema de negocios real y me pareció bastante interesante, preguntándome si alguien podría saber una solución.

Aunque esta pregunta es antigua, agregaré un par de referencias y algoritmos a continuación:

  1. X-Diff: un algoritmo eficaz de detección de cambios para documentos XML, Yuan Wang, David J. DeWitt, Jin-Yi Cai
  2. KF-Diff +: Algoritmo de detección de cambios altamente eficiente para documentos XML
  3. diffX: Algoritmo para detectar cambios en documentos XML de varias versiones
  4. Detección de cambios en árboles XML: una encuesta, Luuk Peters
  5. Similitud en las estructuras de datos de árbol

Además, hay bibliotecas y marcos en GitHub (en javascript) que implementan la diferenciación de estructuras tipo árbol, por ejemplo, aplicaciones que tratan con datos JSON o árboles XML (por ejemplo, para MVC / MVVM del lado del cliente):

  1. React.js
  2. JSON-Patch
  3. jsondiffpatch
  4. objectDiff

En caso de que la gente encuentre esta pregunta y necesite algo implementado para Node.js o para el navegador, proporciono un ejemplo de enlace y código para una implementación que he escrito que puede encontrar en github aquí: ( https://github.com/hoonto/jqgram.git ) basado en el código de PyGram Python existente ( https://github.com/Sycondaman/PyGram ).

Este es un algoritmo de aproximación de distancia de edición en árbol, pero es mucho, mucho más rápido que tratar de encontrar la distancia de edición verdadera. La aproximación se realiza en O (n log n) tiempo y O (n) espacio mientras que la verdadera distancia de edición es a menudo O (n ^ 3) u O (n ^ 2) utilizando algoritmos conocidos para la distancia de edición verdadera. Vea el documento académico del cual proviene el algoritmo PQ-Gram: ( http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf )

Entonces usando 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 }, function(result) { console.log(result.distance); });

Y eso le da un número entre 0 y 1. Cuanto más cerca de cero, más relacionados están los dos árboles con jqgram. Un enfoque podría ser usar jqgram para estrechar varios árboles estrechamente relacionados entre muchos árboles dada su velocidad, luego utilizar la distancia de edición verdadera en los pocos árboles restantes que necesita para una inspección más cercana, y para eso puede encontrar python implementaciones de referencia o puerto del algoritmo de Zhang y Shasha, por ejemplo.

Tenga en cuenta que los parámetros lfn y cfn especifican cómo cada árbol debe determinar los nombres de etiqueta de nodo y la matriz de elementos secundarios para cada raíz de árbol de forma independiente para poder hacer cosas divertidas, como comparar un objeto con 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!

TAMBIÉN, para responder con respecto a la detección de ciclo, revise el método de clonación dentro de jqgram, hay detección de ciclo allí, pero el crédito para eso va al autor del clon de nodo desde el cual esa pieza fue ligeramente modificada e incluida.

No estaba claro si estaba comparando árboles sintácticos abstractos para código fuente, documentos XML interpretados como árboles o algún otro tipo de árbol.

Hay una serie de documentos que discuten la comparación de árboles de sintaxis y el cálculo de las distancias mínimas por varios medios. Las ideas deben ser relevantes.

Un buen artículo es Change Distilling , que intenta comparar el código fuente de dos árboles sintácticos abstractos e informar una diferencia mínima. El documento habla sobre un método específico, y también menciona brevemente (y proporciona referencias) a una variedad de técnicas similares.

Pocos de estos algoritmos se realizan en realidad en las herramientas disponibles para comparar el texto fuente. Nuestro Smart Differencer es uno de ellos.

No solo hay un artículo de Wikipedia sobre el isomorfismo gráfico (como señala Space_C0wb0y) sino también un artículo dedicado sobre el problema del isomorfismo gráfico . Tiene una sección de Solved special cases para los que se conocen soluciones de tiempo polinomial. Trees es uno de ellos y cita las dos referencias siguientes: