13

XML ドキュメント内の 2 つの異なる子ノードが等しいかどうかを判断したいと考えています。2 つのノードが同じ属性セットと子メモを持ち、すべての子メモも等しい場合 (つまり、サブツリー全体が等しい場合)、それらは等しいと見なされます。

入力ドキュメントは非常に大きく (最大 60MB、比較するノードは 100000 を超えます)、パフォーマンスが問題になる場合があります。

2 つのノードが等しいことを確認する効率的な方法は何ですか?

例：

<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 をハッシュ セットに格納するというアイデアが 1 つあります (通常、属性と子メモが常に同じ方法でソートされる正規の文字列表現を最初に取得する必要がありますが、ノードが既にこのような形になります）。

もう 1 つのアイデアは、ノードごとに XmlNode オブジェクトを作成し、すべての属性と子ノードを比較する比較子を作成することです。

私の環境は C# (.Net 2.0) です。フィードバックやさらなるアイデアは大歓迎です。誰かがすでに良い解決策を持っているのではないでしょうか?

EDIT：Microsoftの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'sContainsKeyメソッドを使用して検出され、ノードのハッシュを渡します。これは、XNodeEqualityComparer'sGetHashCodeメソッドを使用して生成されます。

これはあなたのニーズに十分な速さであるはずだと思います。

于 2008-12-05T14:00:47.637 に答える
3

このアプローチはどうですか：

ドキュメント内のすべての<w:pPr>ノード ( ごとに 1 つしかないと思います<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

の問題を正しく定義することさえ非常に困難です。

「2 つの xml ドキュメントが等しい場合は?」

これには多くの理由があります。

  1. XML ドキュメントは、さまざまなテキスト表現を持つツリーです。
  2. 空白のみのノードは、比較で考慮される場合と考慮されない場合があります
  3. コメントノードは、比較で考慮される場合と考慮されない場合があります
  4. PIノードは比較で考慮される場合と考慮されない場合があります
  5. 字句の違い: または
  6. 2 つのドキュメントで、同じ名前空間に異なるプレフィックスが関連付けられている可能性があります。
  7. 名前空間ノードは、doc1 のノードで定義されているように表示され、定義されていないが、doc2 の対応するノードの親から継承されているように表示される場合があります。
  8. doc1 では属性の前後に引用符を使用できますが、doc2 ではアポストロフィを使用できます
  9. エンティティは doc1 で使用できますが、doc2 では事前に展開されている可能性があります
  10. 2 つのドキュメントは異なるが、意味的には同等の DTD を持っている可能性があります。
  11. 等。

したがって、2 つの XML 文書の同等性を比較するための関数を正しく実装しようとするのは、素朴で非現実的です。

私の推奨は、準拠した XPath 2.0 エンジンでdeep-equal()関数を使用することです。

于 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パワーツール）を見てください

于 2008-12-05T12:42:57.390 に答える