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

Ответ 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, передавая хэш node, который мы генерируем с использованием метода XNodeEqualityComparer GetHashCode.

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

Ответ 2

Как насчет этого подхода:

Для всех узлов <w:pPr> в документе (я полагаю, что не более одного на <w:p>) объединяет все соответствующие данные (имена элементов, атрибуты, значения) в строку:

// string format is really irrelevant, so this is just a bogus example
'!w:[email protected]="true"!w:[email protected]:before="10"@w:after="120"'

Сделайте это в алфавитном порядке, чтобы учитывать различный порядок документов.

Создайте коллекцию, используя эти строки, в качестве ключа и ссылку на соответствующий <w:p> node как значение.

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

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

Ответ 3

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

"Когда два документа xml равны?"

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

• XML-документ - это дерево, которое может иметь разные текстовые представления.
• Только узлы с пробелами могут рассматриваться или не учитываться при сравнении
• Узлы комментариев могут рассматриваться или не учитываться при сравнении.
• Узлы PI могут рассматриваться или не учитываться при сравнении.
• Лексические отличия: или
• Различные префиксы могут быть связаны с тем же пространством имен в двух документах
• Пространство имен node может отображаться как определено в node документа doc1 и как не определено, но унаследовано от родителя соответствующего node в doc2
• Цитаты могут использоваться вокруг атрибута в doc1, но апострофы могут использоваться в doc2
• Объекты могут использоваться в doc1, но они могут быть предварительно расширены в doc2
• Два документа могут иметь разные, но семантически эквивалентные DTD
• Etc.

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

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

Ответ 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;
}

Идеи состояли в том, чтобы сделать упорядочение сундомов значительным, но порядок атрибутов не значителен.

Ответ 5

не прямой ответ на ваш вопрос, но тесно связанный с тем, что вы пытаетесь достичь: посмотрите XmlDiff (.net XML-инструменты)