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

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

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

谢谢，迪沃

4

5 回答 5

11

我建议不要滚动您自己的哈希创建函数，而是依赖内置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生成的节点的哈希。XNodeEqualityComparerGetHashCode

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

于 2008-12-05T14:00:47.637 回答
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>节点的引用作为值来构建一个集合。

在执行此操作的过程中，当您遇到给定键已存在于集合中的点时，您会发现一个具有相同属性的段落。如果您想继续收集，请使用节点列表作为收集值。

我不能说这会表现如何，但我想实施和发现并不难。

于 2008-12-05T13:12:48.250 回答
3

即使正确定义问题也是非常具有挑战性的

“当两个 xml 文档相等时？”

这件事情是由很多原因导致的：

  1. XML 文档是可能具有不同文本表示的树。
  2. 在比较中可能会或可能不会考虑仅空白节点
  3. 在比较中可能会或可能不会考虑评论节点
  4. 在比较中可能会或可能不会考虑 PI 节点
  5. 词汇差异：或
  6. 不同的前缀可能与两个文档中的同一个命名空间相关联
  7. 命名空间节点可以显示为在 doc1 的节点上定义，也可以显示为未定义但继承自 doc2 中相应节点的父节点
  8. 可以在 doc1 中的属性周围使用引号，但在 doc2 中可以使用撇号
  9. 实体可以在 doc1 中使用，但它们可以在 doc2 中预先展开
  10. 两个文档可能有不同但语义上等价的 DTD
  11. 等等。

因此，尝试为两个 XML 文档的相等性比较生成函数的正确实现似乎是幼稚和不切实际的。

我的建议是将deep-equal()函数与兼容的 XPath 2.0 引擎一起使用。

于 2008-12-05T14:37:45.597 回答
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;
}

想法是使子节点的顺序显着，但属性的顺序不显着。

于 2008-12-05T15:24:05.003 回答
0

不是对您的问题的直接回答，而是与您要实现的目标密切相关：看看XmlDiff (.net XML power tools)

于 2008-12-05T12:42:57.390 回答