Implementación y resultados empíricos para un algoritmo de detección de cambios en documentos XML

Abstract

Los contenidos de la Web pueden ser expresados en un formato que pueda ser entendido, interpretado y usado por diferente(s) software, permitiéndoles buscar, compartir e integrar información de manera más sencilla. Una vez que se concibe el diseño de XML también lo hace el concepto de DTD (Definición del Tipo de Documento) expresamente reflejado en la aplicación RDF. Mediante RDF podemos extraer la información de la Base de Datos para crear un formato más comprensible para las máquinas. Con esta información podemos realizar deducciones lógicas, combinar información, generar información nueva a partir de una ya existente, realizar consultas complejas en buscadores, entre otras. La detección de cambios en XML se ha vuelto más importante en muchas áreas de aplicación. Los algoritmos de detección de cambios en documentos XML proporcionan a usuarios y aplicaciones una descripción más significativa de los cambios detectados. Cada algoritmo de detección de cambios en documentos XML se centra en su aspecto de detección de cambios tomando en cuenta sus propiedades y optimizaciones. Se proveerán descripciones de algoritmos de detección de cambio para documentos XML y descripción de ciertos tipos de propiedades que juegan un papel clave en estos algoritmos. Asimismo, se presentan algunos ejemplos de detección de cambios en XML aplicados en el área de fusión, versiones y sincronización de documentos XML. Se tratará de explicar los tipos de propiedades más importantes a considerar cuando la velocidad, exactitud o minimización es la exigencia principal. La eficiencia del algoritmo propuesto reside en la detección de isomorfismo en los sub-árboles. La complejidad teórica del algoritmo es O(n logm n), donde n es el número de vértices y m es el mayor número de sub-árboles que posee la raíz. El cual se compara con el desempeño del algoritmo X-Diff, de O(n2), mostrando algunos resultados preliminares sobre su tiempo de ejecución y la calidad del resultado final.