XML Versioning Algorithm

Question

Estoy buscando una forma eficiente de comparar y obtener diferencias entre dos árboles de análisis basados ​​en XML.

¿Qué sugieres que sea la mejor manera de almacenar esas diferencias? Yo he hecho esto:

XML A:

<w:p> 
    <w:pPr> 
    <w:spacing w:after="1"/> 
    </w:pPr> 
    <w:r> 
    <w:t>World</w:t> 
    </w:r> 
</w:p> 

XML B:

<w:p> 
    <w:pPr> 
    <w:spacing w:after="1"/> 
    </w:pPr> 
    <w:r> 
    <w:t>ASDF</w:t> 
    </w:r> 
</w:p> 

El algoritmo determina que "mundo" ha cambiado a "ASDF" y luego los almacena:

div: <w:p><w:r><w:t>World</w:t> -> <w:p><w:r><w:t>ASDF</w:t> 

¿Esto es suficiente para cubrir todos los casos que puedan ocurrir?

¿Alguien sabe de una buena manera de hacerlo? ¡Cualquier ayuda realmente sería apreciada!

Answer 1

Puede ser más difícil. Mira este ejemplo:

<w:p> 
    <w:pPr> 
    <w:spacing w:after="1"/> 
    </w:pPr> 
    <w:r> 
    <w:t>World</w:t> <-- Case 1: this changes to <w:t>ASDF</w:t> 
    <w:t>World</w:t> <-- Case 2: this changes to <w:t>ASDF</w:t> 
    </w:r> 
</w:p> 

Para ser capaz de reconocer ambos casos, usted tiene que almacenar una como

div: <w:p><w:r><w:t>World</w:t> -> <w:p><w:r><w:t>ASDF</w:t> 

y el otro como

div: <w:p><w:r><w:t>World</w:t><w:t>World</w:t> -> <w:p><w:r><w:t>World</w:t><w:t>ASDF</w:t> 

o algo similar (es posible que también desee agregar etiquetas de cierre "w: p" a ambos para que sean subárboles XML válidos).

En general, estos programas pueden ser muy complicados, por lo que no recomendaría crear algo completamente nuevo, sino utilizar algún algoritmo de diff existente (la mayoría será suficiente incluso sin analizar la estructura XML) o modificar uno de ellos para satisfacer sus necesidades.

Answer 2

XMLDiff:

explica cómo usar el XML Dif y herramienta Parche, que compara dos archivos XML y produce una salida XML de las diferencias, mediante la utilización de un escenario típico que los lectores puedan aplicar a sus propias aplicaciones.

Answer 3

¿Qué tal una simple búsqueda en profundidad sobre la parte común? Es decir, realice una búsqueda en profundidad y tan pronto como encuentre una diferencia almacénelo y comience a retroceder. La información adicional necesaria para construir la parte de contexto de la salida se puede almacenar fácilmente en la "pila de retroceso".

Answer 4

cuando desee comparar la diferencia entre dos árboles y, de alguna manera, producir la "diferencia" de esa comparación, básicamente está buscando una variante de tree edit distance problema. Para empezar, mira this paper.

Un problema más común de "distancia de edición" es el problema de la distancia de edición para las cadenas. El software de control de versiones como CVS o SVN que usa "codificación delta" para almacenar los cambios hechos a archivos usan variantes de los algoritmos de distancia de edición de cadenas para calcular los deltas.El caso de los árboles es menos común pero definitivamente interesante.