代码之家 › 专栏 › 技术社区 › Dirk Vollmar

一种高效的XML节点比较算法

performance comparison algorithm xml c#

Dirk Vollmar · 技术社区 · 17 年前

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

例子:

<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节点)。

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

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

谢谢迪沃

5 回复 | 直到 13 年前

Dave R. 17 年前

我建议不要使用自己的散列创建函数,而是使用内置函数 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 方法,传递使用的方法

我认为这应该足够快满足你的需要。

Tomalak 17 年前

这种方法怎么样:

总的来说 <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> 节点作为值。

我不能说这会有多好,但我想实现和发现它并不难。

Dimitre Novatchev 17 年前

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

在比较中可以考虑也可以不考虑只有空格的节点
PI节点可以在比较中考虑,也可以不考虑
词汇差异:或
命名空间节点可以显示为在doc1的节点上定义的,也可以显示为未定义但从doc2中相应节点的父节点继承的
doc1中的属性周围可以使用引号,但doc2中可以使用撇号
这两个文档可能具有不同但语义相同的DTD
等

我的建议是 使用 deep-equal()

ICR 17 年前

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

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

其想法是使子节点的顺序变得重要,但属性的顺序并不重要。

PW. 17 年前

不是对你的问题的直接回答,而是与你想要实现的目标密切相关:看一看 XmlDiff (.net XML power tools)