node - Cómo verificar la similitud de dos árboles Xml(Tree Edit Distance en C#)

levenshtein distance online

Question

En una aplicación de C # necesito verificar la salida de mi algoritmo, que es un árbol XML contra otro árbol XML para ver si son similares. (El orden de los nodos es importante, pero la estructura (nodos anidados), los nombres de los nodos son más importantes). Tal vez el número de adds , removes y moves que se producen en algunos algoritmos de " Distancia de edición de árbol " sea un buen indicador. Pero las respuestas son más paquetes de Java o Python.

Por lo tanto, traté de usar XMLDiffPatch , funciona bien cuando el tipo de algoritmo se establece en Precise . Sin embargo, su punto negativo es que solo genera un archivo DiffGram que necesita ser analizado para encontrar el número de operaciones. Además, tiene muchos errores y genera la OutOfRangeException para algunos árboles XML. Tampoco pude encontrar mejores paquetes para mi propósito para .Net. Hay algunos paquetes de diferencia de XML, pero tal vez ninguno o pocos de ellos están en la Tree Edit Distance .

Un ejemplo:

<A>
<B>
<C></C>
<D></D>
<E>
<F>
</F>
</E>
</B>
</A>

A:

<A>
<C></C>
<D></D>
<G></G>
</A>

Para convertir el primer Xml en el segundo, debe eliminar E y F (2 costos), luego debe eliminar B (pero no su subárbol) y agregar G Entonces los costos totales son 4.

Entonces, como sé aquí, no debería pedir paquetes y herramientas, pido un algoritmo simple o ( algoritmo de distancia de edición de árbol en .Net ) para hacer eso. Este es mi propio algoritmo para verificar la similitud e ignorar las diferencias menores (tener uno o pocos nodos anidados) pero es muy primario y solo para un punto de partida:

public int XMLCompare(XmlNode primary, XmlNode secondary)
{
int x = 0;
if (secondary == null || primary == null)
return 1;
if (secondary.ChildNodes.Count == 1 && primary.ChildNodes.Count > 1)
{
x += XMLCompare(primary, secondary.ChildNodes[0]);
}
else if (secondary.ChildNodes.Count > 1 && primary.ChildNodes.Count == 1)
{
x += XMLCompare(primary.ChildNodes[0], secondary);
}
else
{
if (primary.Name.ToLower() != secondary.Name.ToLower())
x = 1;
int m = Math.Max(primary.ChildNodes.Count, secondary.ChildNodes.Count);
for (int i = 0; i < m i++)
{
x += XMLCompare(
i < primary.ChildNodes.Count ? primary.ChildNodes[i] : null,
i < secondary.ChildNodes.Count ? secondary.ChildNodes[i] : null);
}
}
return x;
}

Answer 1

Microsoft tiene una API para eso. mira this Esta puede ser una referencia antigua de dll, pero solo para tu información, necesitas usar algo como esto. C: / Windows / assembly / GAC / XmlDiffPatch / 1.0.8.28__b03f5f7f11d50a3a / XmlDiffPatch.dll