Algoritmo eficiente para comparar nodos XML

Question

Quiero determinar si dos nodos secundarios diferentes dentro de un documento XML son iguales o no. Dos nodos deben considerarse iguales si tienen el mismo conjunto de atributos y notas del niño y todas las notas del niño son iguales también (es decir, el subárbol completo debe ser igual).

El documento de entrada puede ser muy grande (hasta 60 MB, más de 100000 nodos para comparar) y el rendimiento es un problema.

¿Cuál sería una forma eficiente de verificar la igualdad de dos nodos?

Ejemplo:

<w:p> 
    <w:pPr> 
    <w:spacing w:after="120"/> 
    </w:pPr> 
    <w:r> 
    <w:t>Hello</w:t> 
    </w:r> 
</w:p> 
<w:p> 
    <w:pPr> 
    <w:spacing w:after="240"/> 
    </w:pPr> 
    <w:r> 
    <w:t>World</w:t> 
    </w:r> 
</w:p> 

Este fragmento de XML describe los párrafos en un documento OpenXML. El algoritmo se usaría para determinar si un documento contiene un párrafo (nodo w: p) con las mismas propiedades (nodo w: pPr) que otro párrafo anterior en el documento.

Una idea que tengo sería almacenar el XML externo de los nodos en un conjunto hash (normalmente tendría que obtener una representación de cadena canónica donde los atributos y notas secundarias se ordenan siempre de la misma manera, pero puedo esperar mis nodos ya están en tal forma).

Otra idea sería crear un objeto XmlNode para cada nodo y escribir un comparador que compare todos los atributos y los nodos secundarios.

Mi entorno es C# (.Net 2.0); cualquier comentario y más ideas son bienvenidas. ¿Tal vez alguien ya tiene una buena solución?

EDITAR: XmlDiff API de Microsoft realmente puede hacer eso, pero me preguntaba si habría un enfoque más ligero. XmlDiff parece producir siempre un diffgram y siempre producir primero una representación canónica de nodo, ambas cosas que no necesito.

EDIT2: Finalmente implementé mi propio XmlNodeEqualityComparer basado en la sugerencia realizada aquí. ¡¡¡¡Muchas gracias!!!!

Gracias, divo

Answer 1

Recomendaría no hacer rodar su propia función de creación de hash y en su lugar confiar en el método incorporado XNodeEqualityComparer. Esto garantiza tener en cuenta los atributos y los nodos descendientes al crear el resultado y también puede ahorrarle algo de tiempo.

Su código se parecería a lo siguiente:

XNodeEqualityComparer comparer = new XNodeEqualityComparer(); 
XDocument doc = XDocument.Load("XmlFile1.xml"); 
Dictionary<int, XNode> nodeDictionary = new Dictionary<int, XNode>(); 

foreach (XNode node in doc.Elements("doc").Elements("node")) 
{ 
    int hash = comparer.GetHashCode(node); 
    if (nodeDictionary.ContainsKey(hash)) 
    { 
     // A duplicate has been found. Execute your logic here 
     // ... 
    } 
    else 
    { 
     nodeDictionary.Add(hash, node); 
    } 
} 

Mi XmlFile1.xml es:

<?xml version="1.0" encoding="utf-8" ?> 
<doc> 
    <node att="A">Blah</node> 
    <node att="A">Blah</node> 
    <node att="B"> 
    <inner>Innertext</inner> 
    </node> 
    <node>Blah</node> 
    <node att="B"> 
    <inner>Different</inner> 
    </node> 
</doc> 

nodeDictionary terminará contiene una colección única de nodos y sus hash. Los duplicados se detectan utilizando el método DictionaryContainsKey, pasando el hash del nodo, que generamos utilizando el método XNodeEqualityComparerGetHashCode.

Creo que esto debería ser lo suficientemente rápido para sus necesidades.

Answer 2

no

una respuesta directa a su pregunta, pero estrechamente relacionado con lo que usted está tratando de acheive: echar un vistazo a (herramientas eléctricas .NET XML) XmlDiff

Answer 3

¿Qué pasa con este enfoque:

Para todos <w:pPr> nodos en el documento (supongo que no hay más de uno por <w:p>), concatenar todos los datos relevantes (nombres de elementos, atributos, valores) en una cadena:

// string format is really irrelevant, so this is just a bogus example 
'!w:keep-with-next@value="true"!w:spacing@w:before="10"@w:after="120"' 

Hazlo por orden alfabético, para tener en cuenta la variación del orden de los documentos.

Genere una colección utilizando estas cadenas como la clave y la referencia al nodo respectivo <w:p> como el valor.

En el proceso de hacer esto, cuando llega al punto en que ya existe una clave dada en la colección, encontró un párrafo con las mismas propiedades. Trabaje con una lista de nodos como valor de recopilación, si desea seguir recopilando.

No puedo decir qué tan bien funcionaría esto, pero supongo que no es demasiado difícil de implementar y descubrir.

Answer 4

Es muy difícil incluso para definir correctamente el problema de

"Cuando dos documentos XML son iguales?"

Hay muchas razones para esto:

1. Un documento XML es un árbol que puede tener diferentes representaciones textuales.
2. Whitespace nodos sólo pueden o no pueden ser considerados en una comparación
3. nodos de comentario pueden o no pueden ser considerados en una comparación
4. nodos PI pueden o no pueden ser considerados en una comparación
5. diferencias léxicas: o
6. diferentes prefijos pueden estar asociados con el mismo espacio de nombres en los dos documentos
7. un nodo de espacio de nombres se puede mostrar como se define en un nodo de doc1 y como no definida pero heredado del padre del nodo correspondiente en doc2
8. cotizaciones pueden ser utilizados alrededor de un atributo en doc1 pero apóstrofes se pueden utilizar en doc2
9. Las entidades pueden ser utilizados en doc1 pero pueden ser pre-expandida en doc2
10. Los dos documentos pueden tener diferentes pero semánticamente equivalentes DTD
11. Etc.

por lo tanto, parece ingenuo y poco realista tratar de producir una correcta implementación de una función de comparación de igualdad de dos documentos XML.

Mi recomendación es para usar la función deep-equal() con un motor compatible con XPath 2.0.

Answer 5

Aquí hay una función hash que he destruido que intenta resolver una parte de su problema. Tenga en cuenta que tengo muy poca experiencia en la escritura de funciones hash, y lo he incluido principalmente para obtener retroalimentación de las personas sobre su efectividad para resolver este problema en particular.No recomendaría su uso en producción.

static int HashXElement(XElement elem) 
{ 
    int hash = 23; 

    foreach (XAttribute attrib in elem.Attributes()) 
    { 
     int attribHash = 23; 
     attribHash = attribHash * 37 + attrib.Name.GetHashCode(); 
     attribHash = attribHash * 37 + attrib.Value.GetHashCode(); 
     hash = hash^attribHash; 
    } 

    foreach(XElement subElem in elem.Descendants()) 
    { 
     hash = hash * 37 + XmlHash(subElem); 
    } 

    hash = hash * 37 + elem.Value.GetHashCode(); 

    return hash; 
} 

La idea era hacer significativo el orden de los subnodos, pero el orden de los atributos no era significativo.