c# - 比较 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)；非常欢迎任何反馈和进一步的想法。也许有人甚至已经有了一个好的解决方案？

编辑:Microsoft 的 XmlDiff API 实际上可以做到这一点，但我想知道是否会有更轻量级的方法。 XmlDiff 似乎总是生成一个 diffgram，并且总是首先生成一个规范的节点表示，这两个都是我不需要的。

EDIT2:我最终根据此处提出的建议实现了自己的 XmlNodeEqualityComparer。非常感谢!!!!

谢谢，迪沃

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 方法。

我认为这应该足够快，可以满足您的需求。