Эффективный алгоритм сравнения узлов XML

Question

Я хочу определить, равны ли два разных дочерних узла в документе XML. Два узла следует считать равными, если они имеют одинаковый набор атрибутов и дочерних заметок, и все дочерние заметки тоже равны (то есть все поддерево должно быть равным).

Входной документ может быть очень большим (до 60 МБ, более 100 000 узлов для сравнения), и производительность является проблемой.

Какой эффективный способ проверить равенство двух узлов?

Пример:

<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: p) с теми же свойствами (узел w: pPr), что и другой абзац ранее в документе.

Одной из моих идей было бы сохранить внешний XML-узел в хэш-наборе (Обычно мне сначала нужно получить каноническое строковое представление, где атрибуты и дочерние заметки всегда сортируются одинаково, но я могу ожидать узлы уже должны быть в такой форме).

Другой идеей было бы создать объект XmlNode для каждого узла и написать компаратор, который сравнивает все атрибуты и дочерние узлы.

Моя среда - C # (.Net 2.0); любые отзывы и дальнейшие идеи очень приветствуются. Может, у кого-нибудь уже есть хорошее решение?

РЕДАКТИРОВАТЬ: Microsoft XmlDiff API действительно может сделать это, но мне было интересно, будет ли более легкий подход. Кажется, что XmlDiff всегда создает diffgram и всегда сначала создает каноническое представление узла, обе вещи мне не нужны.

EDIT2: я наконец-то реализовал свой собственный XmlNodeEqualityComparer на основе предложенного здесь предложения. Большое спасибо !!!!

Спасибо, диво

Answer 1

Я бы рекомендовал не использовать собственную функцию создания хешей, а вместо этого полагаться на встроенный метод 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.

Я думаю, это должно быть достаточно быстро для ваших нужд.

Answer 2

Очень сложно даже правильно определить проблему

«Когда два XML-документа равны?»

Есть много причин для этого:

1. XML-документ - это дерево, которое может иметь различные текстовые представления.
2. Только пробельные узлы могут учитываться или не учитываться при сравнении
3. Узлы комментариев могут или не могут рассматриваться в сравнении
4. Узлы PI могут учитываться или не учитываться при сравнении
5. Лексические различия: или
6. С одним и тем же пространством имен в двух документах могут быть связаны разные префиксы
7. Узел пространства имен может быть показан как определенный на узле doc1 и как не определенный, но унаследованный от родителя соответствующего узла в doc2
8. Кавычки могут использоваться вокруг атрибута в doc1, но апострофы могут использоваться в doc2
9. Объекты могут использоваться в doc1, но они могут быть предварительно расширены в doc2
10. Два документа могут иметь разные, но семантически эквивалентные DTD
11. 1028 * Etc. *

Поэтому наивно и нереально пытаться создать правильную реализацию функции для сравнения равенства двух XML-документов.

Я рекомендую использовать функцию deep-equal () с совместимым движком XPath 2.0.

Answer 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> в качестве значения.

В процессе этого, когда вы достигли точки, когда данный ключ уже существует в коллекции, вы нашли абзац с такими же свойствами. Если вы хотите продолжить сбор, работайте со списком узлов в качестве значения коллекции.

Я не могу сказать, насколько хорошо это будет работать, но я думаю, что это не так сложно реализовать и выяснить.

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)