用于比较XML节点的高效算法

Question

我想确定XML文档中的两个不同的子节点是否相等.如果两个节点具有相同的属性集和子注释,并且所有子注释也相等(即整个子树应该相等),则应认为它们是相等的.

输入文档可能非常大(最多60MB,超过100000个节点需要比较)并且性能是个问题.

检查两个节点是否相等的有效方法是什么？

例:

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

此XML片段描述了OpenXML文档中的段落.该算法将用于确定文档是否包含具有与文档前面的另一段相同属性(w:pPr节点)的段落(w:p节点).

我的一个想法是将节点的外部XML存储在一个哈希集中(通常我必须首先得到规范的字符串表示,其中属性和子注释总是以相同的方式排序,但我可以期望我的节点已经到是这样一种形式).

另一个想法是为每个节点创建一个XmlNode对象,并编写一个比较所有属性和子节点的比较器.

我的环境是C#(.Net 2.0); 我们非常欢迎任何反馈和进一步的想法.也许有人甚至已经有了一个很好的解决方案？

编辑:微软的XmlDiff API实际上可以这样做,但我想知道是否会有一个更轻量级的方法.XmlDiff似乎总是产生一个diffgram,并且总是先生成一个规范的节点表示,这两件事我都不需要.

EDIT2:我最终根据这里提出的建议实现了我自己的XmlNodeEqualityComparer.非常感谢!!!!

谢谢,divo

Answer 1

我建议不要滚动你自己的哈希创建函数,而是依赖于内置XNodeEqualityComparer的GetHashCode方法.这可以保证在创建结果时考虑属性和后代节点,并且可以节省您一些时间.

您的代码如下所示:

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

我的XmlFile1.xml是:

<?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最终将包含一个独特的节点集合及其哈希值.重复通过使用检测到Dictionary的ContainsKey方法,传入的节点的散列,我们生成使用XNodeEqualityComparer的GetHashCode方法.

我认为这应该足够快,以满足您的需求.