Calcular operaciones mínimas para hacer dos estructuras de árbol idénticas

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

Digamos que tenemos 2 estructuras de árbol con más o menos los mismos nodos reorganizados. Como encontraras

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) - elimina el nodo A (con todo el subárbol)

que transforma un árbol en otro.

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

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

Descargo de responsabilidad: esto no es una tarea, en realidad proviene de un problema comercial real y me pareció bastante interesante preguntarme si alguien podría conocer una solución.

No solo hay un artículo de Wikipedia sobre isomorfismo de grafos (como señala Space_C0wb0y), sino también un artículo dedicado al problema del isomorfismo de grafos . Tiene una sección Solved special casespara la que se conocen soluciones en tiempo polinómico. Trees es uno de ellos y cita las siguientes dos referencias:

• PJ Kelly, "Un teorema de congruencia para árboles" Pacific J. Math., 7 (1957) págs. 961–968
• Aho, Alfred V .; Hopcroft, John; Ullman, Jeffrey D. (1974), El diseño y análisis de algoritmos informáticos, Reading, MA: Addison-Wesley.

No tenía claro si estaba comparando árboles de sintaxis abstracta para el código fuente, documentos XML interpretados como árboles o algún otro tipo de árbol.

Hay varios artículos que discuten la comparación de árboles de sintaxis y el cálculo de 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 de sintaxis abstractos e informar una diferencia mínima. El documento habla de 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 las herramientas disponibles para comparar el texto fuente de los programas de computadora. Nuestro Smart Differencer es uno de ellos; está impulsado por una gramática explícita del lenguaje para muchos idiomas.

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

1. X-Diff: un algoritmo de detección de cambios eficaz 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: un algoritmo para detectar cambios en documentos XML de múltiples versiones
4. Detección de cambios en árboles XML: una encuesta, Luuk Peters
5. Similitud en estructuras de datos de árbol

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

1. React.js
2. Parche JSON
3. jsondiffpatch
4. objectDiff

En caso de que la gente encuentre esta pregunta y necesite algo implementado para Node.js o el navegador, proporciono un enlace y un ejemplo de 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 PyGram Python existente ( https://github.com/Sycondaman/PyGram ).

Este es un algoritmo de aproximación de distancia de edición de árbol , pero es mucho, mucho más rápido que intentar encontrar la distancia de edición real. La aproximación se realiza en el tiempo O (n log n) y el espacio O (n), mientras que la distancia de edición real suele ser O (n ^ 3) u O (n ^ 2) utilizando algoritmos conocidos para la distancia de edición real. Vea el artículo académico del que 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 estrechamente relacionados se ven los dos árboles con jqgram. Un enfoque podría ser usar jqgram para reducir varios árboles estrechamente relacionados de entre muchos árboles dada su velocidad, luego utilizar la distancia de edición real en los pocos árboles restantes que necesita para inspeccionar más de cerca, y para eso puede encontrar python implementaciones para referencia o puerto del algoritmo Zhang & Shasha, por ejemplo.

Tenga en cuenta que los parámetros lfn y cfn especifican cómo cada árbol debe determinar los nombres de las etiquetas de los nodos y la matriz secundaria para cada raíz del árbol de forma independiente para que pueda hacer cosas divertidas 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 sus funciones proporcionadas 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 utilícelo del lado del cliente o del servidor!

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

Esto se denomina problema de corrección de árbol a árbol o problema de edición de árbol a árbol . La mayor parte de la literatura que trata sobre esto se relaciona explícitamente con la comparación de árboles XML por alguna razón, por lo que la búsqueda de "algoritmo de diferenciación de XML" produce muchos resultados. Además de la lista de enlaces de Nikos, encontré estos:

• Detección de cambios detallados en documentos de texto estructurados (2014)
• Detección de cambios por nivel (CDL): un algoritmo eficiente para detectar cambios en documentos XML (2010)
• Comparación de documentos XML como árboles ordenados etiquetados con referencia (2011) El código para esto: ¡ VTracker todavía existe! Editar: en realidad, el código interesante no está incluido. Esto me señaló ...
• UMLDiff: un algoritmo para la diferenciación de diseños orientados a objetos (2005).
• Revisando la distancia de edición del árbol y su retroceso: un tutorial (2018): parece un buen tutorial para el algoritmo Zhang-Shasha, que parece ser la solución "clásica", pero tiene una complejidad de tiempo terrible porque compara cada subárbol con todos los demás subárboles.

También recomiendo encarecidamente leer Change Detection in XML Trees: a Survey, pero es de 2005, por lo que casi ninguna de las herramientas que menciona ya existen. La comparación de documentos XML como árboles ordenados etiquetados con reconocimiento de referencias tiene la mejor descripción intuitiva de algunos de los algoritmos que he encontrado hasta ahora (comience en la sección 2.1.2).

Desafortunadamente, no parece haber mucho código fuente abierto disponible que haga esto y no sea antiguo. Solo un montón de artículos demasiado complejos. : - /