Algorithme efficace pour comparer les noeuds XML

Je veux déterminer si deux nœuds enfants au sein d'un document XML sont égaux ou non. Deux nœuds doivent être considérées comme égales si elles ont le même ensemble d'attributs et de l'enfant les notes et tous les enfants de notes sont égales, trop (c'est à dire l'ensemble des sous arbres doivent être identiques).

Le document d'entrée est peut-être très large (jusqu'à 60 mo, plus de 100000 nœuds à comparer) et de la performance est un problème.

Ce qui serait un moyen efficace pour vérifier l'égalité de deux nœuds?

Exemple:

<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>

Ce fragment de code XML décrit dans les paragraphes d'un document OpenXML. L'algorithme serait utilisé pour déterminer si un document contient un paragraphe (en w:p nœud) avec les mêmes propriétés (w:pPr nœud) comme un autre paragraphe plus haut dans le document.

Une idée que j'ai serait de stocker les nœuds externes XML dans une table de hachage set (Normalement je devrais obtenir un canoniques représentation de chaîne des attributs et de l'enfant notes sont triées toujours de la même façon, mais je peux attendre mon nœuds déjà d'être dans un formulaire).

Une autre idée serait de créer un objet XmlNode pour chaque nœud et d'écrire un comparateur qui compare tous les attributs et les nœuds enfants.

Mon environnement C# (.Net 2.0); tous les commentaires et idées sont les bienvenus. Peut-être quelqu'un a même déjà une bonne solution?

EDIT: Microsoft XmlDiff API peut réellement le faire, mais je me demandais si il y aurait un plus léger approche. XmlDiff semble toujours produire un diffgram et à toujours produire un canoniques nœud représentation première, les deux choses que je n'ai pas besoin.

EDIT2: j'ai enfin mes propres XmlNodeEqualityComparer basé sur la suggestion faite ici. Merci beaucoup!!!!

Grâce,
divo

source d'informationauteur Dirk Vollmar

algorithm c#comparison performance xml

Je le recommande à l'encontre de roulement de votre propre hachage fonction de création et, au lieu de compter sur la XNodeEqualityComparer's GetHashCode méthode. Cela garantit à prendre en compte les attributs et les nœuds descendants lors de la création de la suite et pourrait vous faire économiser du temps.

Votre code devrait ressembler à la suivante:

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);
    }
}

Mon XmlFile1.xml est:

<?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 finira contenant une collection unique de Nœuds et de leurs hashes. Les doublons sont détectés à l'aide de la Dictionary's ContainsKey méthode, en passant de la valeur de hachage du nœud, qui nous générer à l'aide de la XNodeEqualityComparer's GetHashCode méthode.

Je pense que cela devrait être assez rapide pour vos besoins.

3

Ce sujet de cette approche:

Pour tous <w:pPr> nœuds dans le document, je le suppose, il n'y a pas plus d'un par <w:p>), concaténer toutes les données pertinentes (les noms des éléments, attributs, valeurs) dans une chaîne de caractères:
```
//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"'
```
Le faire sur l'ordre alphabétique, pour tenir compte des différents de l'ordre du document.

Construire une collection à l'aide de ces chaînes comme la clé et la référence à l' <w:p> nœud en tant que valeur.

Dans le processus de le faire, quand vous frappez le point d'une clé existe déjà dans la collection, vous avez trouvé un paragraphe avec les mêmes propriétés. Travailler avec une liste de nœuds comme la valeur de la collection, si vous voulez garder la collecte.

Je ne peux pas dire à quel point ce serait réaliser, mais je suppose que c'est pas trop dur à mettre en œuvre et de savoir.
3

Il est très difficile, même pour définir correctement le problème de la

"Lorsque deux documents xml sont égaux?"

Il y a de nombreuses raisons à cela:
1. Un document XML est un arbre qui peut avoir différentes représentations textuelles.
2. Blanc, seuls les nœuds peuvent ou ne peuvent pas être considérés dans une comparaison
3. Commentaire nœuds peuvent ou ne peuvent pas être considérés dans une comparaison
4. PI nœuds peuvent ou ne peuvent pas être considérés dans une comparaison
5. Lexicale différences: ou
6. Différents préfixes peuvent être associés avec le même espace de noms dans les deux documents
7. Un nœud d'espace de noms peut être montré comme défini sur un noeud de doc1 et de ne pas définis, mais a hérité du parent du nœud correspondant dans doc2
8. Guillemets peuvent être utilisés autour d'un attribut dans doc1 mais apostrophes peuvent être utilisés dans doc2
9. Entités peuvent être utilisés dans doc1, mais ils peuvent être pré-déployé dans doc2
10. Les deux documents différents, mais sémantiquement équivalent Dtd
11. Etc.
Par conséquent, il semble naïf et irréaliste d'essayer de produire une mise en œuvre correcte de la fonction de comparaison d'égalité de deux documents XML.

Ma recommandation est d'utiliser le profondeur égale() fonction avec la conformité de XPath 2.0 moteur.

Ici est une fonction de hachage j'ai frappé vers le haut qui tente de résoudre une partie du problème. Notez que j'ai très peu d'expérience de la rédaction de fonctions de hachage, et ont inclus principalement pour obtenir les commentaires de personnes en efficacité dans la résolution de ce problème particulier. Je ne voudrais pas vous recommandons de l'utiliser en production.

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;
}

Les idées était de faire de la commande de sous-nœuds importants, mais l'ordre des attributs non significative.

0

pas une réponse directe à votre question, mais étroitement liée à ce que vous essayez d'atteindre: jetez un oeil à XmlDiff (.net, XML, les outils électriques)

Vous devez vous connecter pour publier un commentaire.