比较XML节点的高效算法

Question

比较XML节点的高效算法

13

我想确定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似乎总是产生一个差异图并始终首先生成规范的节点表示，这两件事我都不需要。

编辑2：我最终根据此处提出的建议实现了自己的XmlNodeEqualityComparer。非常感谢！！！

谢谢，divo

- divo

相关帖子：https://dev59.com/4HVC5IYBdhLWcg3w1E7w 和 https://dev59.com/snVC5IYBdhLWcg3wfxM8 - bruno conde

你好，感谢您的评论。XmlDiff看起来很不错，但对于我这个具体问题来说似乎有些重。我不需要找到任何差异信息，仅一个简单的相等或不相等测试就足够了，并且我也不需要创建一个规范表示，而这正是XmlDiff一直在做的。 - Dirk Vollmar

5个回答

3

即使是正确定义问题 "两个XML文档何时相等?" 也非常具有挑战性。

这有很多原因:

XML文档是一棵树，可能具有不同的文本表示。
仅包含空格的节点可能会或可能不会在比较中被考虑。
注释节点可能会或可能不会在比较中被考虑。
PI节点可能会或可能不会在比较中被考虑。
词汇差异: 或
不同的前缀可能与两个文档中的相同命名空间相关联。
命名空间节点可能被显示为在doc1的节点上定义，在doc2的对应节点的父级上未定义但继承。
在doc1中可能在属性周围使用引号，但在doc2中可能使用撇号。
实体可能在doc1中使用，但在doc2中可能被预先展开。
两个文档可能具有不同但语义等效的DTD。
等等。

因此，尝试编写一个正确实现的函数来比较两个XML文档的相等性似乎是天真和不切实际的。

我建议使用deep-equal()函数与符合XPath 2.0标准的引擎。

- Dimitre Novatchev

有一个W3C建议来处理这些问题：规范化XML版本1.0（http://www.w3.org/TR/xml-c14n.html）。您所描述的问题在许多情况下必须考虑，例如在验证XML文档的数字签名时。 - Dirk Vollmar

1

它不能处理所有这些问题。例如，它没有命名空间重写：http://www.w3.org/TR/xml-c14n.html#NoNSPrefixRewriting。因此，仅具有与特定命名空间相关联的不同前缀的两个XML文档将具有不同的规范化。 - Dimitre Novatchev

3

这种方法怎么样：

对于文档中的所有<w:pPr>节点（我想每个<w:p>中不会有多个此类节点），将所有相关数据（元素名称、属性、值）连接成一个字符串：

// 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"'

按字母顺序进行操作，以考虑不同的文档顺序。

使用这些字符串作为键，将相应的<w:p>节点的引用作为值来构建集合。

在此过程中，当您发现给定的键已经存在于集合中时，您找到了具有相同属性的段落。如果要继续收集，请使用节点列表作为集合值。

我无法确定其性能如何，但我猜想它不太难实现并找出结果。

- Tomalak

我已经制作了一次性的 XSLT 转换，用于执行所描述的字符串构建：http://pastebin.me/49393ec501fe9。也许它比通过 DOM 遍历“手动”完成更快。您将获得该类元素的列表：'<para position="2">!w:spacing@w:after"240"</para>'。 - Tomalak

2

这里是一个哈希函数，我设计它来解决您的问题的一部分。请注意，我很少有编写哈希函数的经验，并且主要包含它是为了从人们那里获得反馈，以确定它在解决此特定问题方面的有效性。我不建议在生产中使用它。

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

这个想法是使子节点的顺序具有重要性，但属性的顺序不具有重要性。

- ICR

0

这不是你问题的直接答案，但与你想要实现的目标密切相关：看一下XmlDiff（.net XML 功能工具）

- PW

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dave R. · Accepted Answer

我建议不要编写自己的哈希创建函数，而是依赖于内置的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 方法生成的。

我认为这对您的需求来说应该足够快了。