比较XML节点的高效算法

小编典典

比较XML节点的高效算法

algorithm

我想确定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：p节点），该段落（w：pPr节点）的属性与文档前面的另一个段落相同。

我的一个想法是将节点的外部XML存储在散列集中（通常，我必须首先获得规范的字符串表示形式，其中属性和子注释始终以相同的方式排序，但是我可以期望我的节点已经以这种形式）。

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

我的环境是C＃（.Net 2.0）；任何反馈和进一步的想法都非常欢迎。也许有人甚至已经有一个好的解决方案？

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

EDIT2：我终于根据这里提出的建议实现了自己的XmlNodeEqualityComparer。非常感谢！！！！

谢谢，divo

阅读 306

2020-07-28

共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方法生成的节点的哈希值。

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

2020-07-28