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

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

输入文档可能非常大（最多60MB，超过100000个节点需要比较）并且性能是个问题。

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

例：

     Hello        World   

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

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

另一个想法是为每个节点创建一个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 nodeDictionary = new Dictionary(); 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是：

   Blah Blah  Innertext  Blah  Different   

nodeDictionary最终将包含一个唯一的节点集合及其哈希值。 通过使用Dictionary的ContainsKey方法检测重复项，传入节点的哈希值，我们使用XNodeEqualityComparer的GetHashCode方法生成该哈希值。

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

Answer 2

这种方法怎么样：

对于文档中的所有节点（我假设每不超过一个），将所有相关数据（元素名称，属性，值）连接成一个字符串：

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

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

使用这些字符串作为键以及对相应节点的引用作为值来构建集合。

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

我不能说这会有多好，但我想这并不难实现并找出答案。

Answer 3

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

“当两个xml文件相同时？”

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

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

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

我的建议是使用深度相等（）函数和兼容的XPath 2.0引擎。

Answer 4

这是一个哈希函数，我试图解决你的部分问题。 请注意，我在编写哈希函数方面的经验很少，并且主要是为了从人们那里得到关于它在解决这个特定问题方面的有效性的反馈。 我不建议它在生产中使用。

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

这些想法是为了使子节点的排序显着，但属性的排序并不重要。

Answer 5

不是你的问题的直接答案，而是与你想要实现的内容密切相关：看看XmlDiff （.net XML电动工具）