LINUX.ORG.RU

Сравнить XML

 


0

2

Требуется написать скрипт (на внутрикорпоративном скриптовом языке) для сравнения 2 файлов данных в формате XML и вывода списка различий. Есть API для работы с XML, где есть функции GetRootElement, GetFirstChild, GetNextSibling, GetFirstChildByName, GetNextSiblingByName, GetParent, GetElementTag, GetAttributesCount, GetAttributeByName, GetAttributeByIndex и т.д.

Проблема в следующем. Файлы следует считать одинаковыми, если они отличаются только порядком атрибутов внутри тегов или порядком элементов на одном уровне иерархии.

Вопрос: как лучше сравнивать?

Я сделал следующее.
Для сравнения атрибутов в паре элементов:

  • перебрать все атрибуты в 1-м теге, для каждого искать совпадающие во 2-м теге;
  • перебрать все атрибуты во 2-м теге, проверить, что каждый есть в 1-м.

Для проверки равенства пары элементов из 2 файлов:

  • сравнить тег;
  • сравнить атрибуты;
  • составить 2 списка детей;
  • сравнить число детей;
  • рекурсивно сравнивать каждого из детей из 1-го файла с каждым из детей из 2-го файла, отмечая в списках совпадающих; исключать из дальнейшего сравнения тех, для кого нашлась пара.

Для сравнения файлов:

  • взять корневые элементы и рекурсивно сравнить.

Как-то оптимизировать можно?

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

★★

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

peregrine ★★★★★ ()

В свое время я делал похожую задачу (сравнение 2-х деревьев) так.

Сериализовать дерево (XML) в строку, а потом сравнивать 2 строки.

Сравнивать можно алгоритмом Левенштайна например, с помощью которого можно потом с точностью до символа (до атрибута / тэга / …) показать различия.

В зависимости от произвольно заданной операции сравнения при выполнении алгоритма Левенштайна, можно определить любые варианты сравнения 2-х деревьев.

Все это достаточно просто реализовать даже на сильно урезанном скриптовом языке.

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

anonymous ()

Требуется написать скрипт (на внутрикорпоративном скриптовом языке)

Какие инструменты сравнения узлов, элементов, атрибутов XML и списков доступны в этом чудо-языке?

blexey ★★★★★ ()
Ответ на: комментарий от anonymous

А в задаче оптимизируется количество используемых операций или религия не позволяет их определить?

Кроме того эти операции и так нужны, и так или иначе будут, что в топологической сортировке, что здесь.

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

Для того, чтобы задать отношение порядка, нужно всего лишь определить эквивалентность (все совпадает) и 1 операцию порядка, например больше (сравниваем множества атрибутов) - 2 простые операции, которые автор уже реализовал.

А вообще, «критикуешь - предлагай».

Какой алгоритм / эффективнее лучше на скорую руку? Да еще и на неизвестном «внутрикорпоративном скриптовом языке»?

anonymous ()
Ответ на: комментарий от mky

Отсортировать, а потом сравнивать?

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

olegd ★★ ()
Последнее исправление: olegd (всего исправлений: 1)
Ответ на: комментарий от peregrine

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

Структура в файле древовидная. Я решил преобразовать дерево в список строк и сравнивать списки. То есть каждая цепочка от корня до самого глубокого элемента станет строкой <tag1 [attributes1]> <tag2 [attributes2]> <tag3 [attributes3]> ... Максимальное число вложений – до 10. Как делать это преобразование, если не рекурсией?

olegd ★★ ()
Ответ на: комментарий от blexey

Какие инструменты сравнения узлов, элементов, атрибутов XML и списков доступны в этом чудо-языке?

Для чтения XML – только перечисленное выше. Но есть строки, массивы и списки строк. Похоже, достаточно будет извлечь атрибуты и теги в виде строк, нормализовать и отсортировать атрибуты, склеить всё в строки и сравнивать 2 списка строк.

olegd ★★ ()
Ответ на: комментарий от olegd

Если лень возиться с рекурсивным сравнением ветвей, можно пробежаться по ним и построить линейный список путей (XPath) ко всем элементам любых типов со всеми атрибутами и их значениями, встреченными в узлах.
Тогда задача теоретически сводится к построению всех таких путей от корня до каждого «листа» в виде одной строки, и затем поиску первого попавшегося отличия в строках двух списков.
Но это будет выполняться в два прохода: полный - для построения списка, плюс вероятнее всего неполный - для поиска первого отличия.

Рекурсивное сравнение могло бы справиться за один проход.

Сравнительная эффективность обоих вариантов зависит от реализации используемых инструментов чудо-языка. В общем, тебе придётся самому написать оба варианта и сравнить их производительность в твоих условиях.

blexey ★★★★★ ()

перебрать все атрибуты во 2-м теге, проверить, что каждый есть в 1-м.

Это лишнее.
Вместо этого достаточно проверить, что количество атрибутов равно.

Попробуйте для каждого children nodes подсчитать сумму кодов символов в атрибутах.
В «одинаковых» nodes она будет совпадать.

Владимир

anonymous ()
Ответ на: комментарий от anonymous

операцию порядка

Как задать (легкую) операцию порядка для иерархического элемента. Допустим, есть два элемента-поддерева с одинаковыми корнями, но с разными потомками. Какой из них первее?

anonymous ()
Ответ на: комментарий от mky

Хотел предложить, а потом подумал, что обычно же атрибутов 3-5, можно и за m*n пробежаться без проблем. ТС, что оптимизируешь? Уже тормозит? Если нет, сделай, как получится, потом отрефакторишь.

cdshines ★★★★ ()
Ответ на: комментарий от anonymous

Попробуйте для каждого children nodes подсчитать сумму кодов символов в атрибутах. В «одинаковых» nodes она будет совпадать.

Не оптимальный алгоритм не сложно разработать …

Владимир

anonymous ()
Ответ на: комментарий от blexey

можно пробежаться по ним и построить линейный список путей (XPath) ко всем элементам любых типов со всеми атрибутами и их значениями, встреченными в узлах. Тогда задача теоретически сводится к построению всех таких путей от корня до каждого «листа» в виде одной строки,

Так и сделал.

и затем поиску первого попавшегося отличия в строках двух списков.

Мне нужен список отличающихся путей. Он получается после вычёркивания из сравниваемых списков всех совпадающих строк.

olegd ★★ ()
Ответ на: комментарий от anonymous

Зависит от алгоритма обхода дерева.

В предложенном варианте алгоритм «сериализации» же фиксирован, т.е. обходы одинаковые.

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

anonymous ()
Ответ на: комментарий от peregrine

Любую рекурсию можно заменить на циклы и обход в ширину…

Можно. Но как-то громоздко получается.

Берём корень.
Добавляем в список строку с тегом корня. Перебираем его детей. Для каждого создаём строку <тег корня> + <тег ребёнка>. Возвращаемся к 1-му ребёнку. (GetParent + GetFirstChild) Повторно генерируем его строку, либо надо было её хранить с момента создания, либо нужна какая-то параллельная списку строк структура для навигации. Перебираем его детей. Для каждого добавляем строку в список. Переходим на соседнего родителя. и т.д.

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

olegd ★★ ()
Ответ на: комментарий от olegd

Нее, ты не понял.

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

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

anonymous ()
Ответ на: комментарий от olegd

…либо нужна какая-то параллельная списку строк структура для навигации this Имхо так и придется сделать, создать такую структуру aka index и использовать.

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

Если же сериализовал в строку, то при сравнении строк можно просто выводить все отличия после первого несовпадения «символа».

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

Строки / списки / индексы конструируются ровно 2 раза, по 1 для каждого дерева-документа.

А изобретать деревья на основе массивов как-то не тянет.

Это же просто обход дерева, такой же как и bhs или dhs, разницы нет. Сравнение без какого-либо обхода все равно не выйдет.

anonymous ()
Ответ на: комментарий от cdshines

ТС, что оптимизируешь? Уже тормозит?

Нет. Скрипт должен быть простым, понятным и легко читаемым. Чтобы я через год мог не вчитываясь объяснить незнакомому с ним человеку, как он работает. Если я сам уже через сутки путаюсь, значит надо упростить.

А вообще, самой дорогой операцией может быть нормализация атрибутов. Но пока что самые большие XML были до 8 уровней вложенности и менее 160 элементов. Основное время тратилось на инициализацию скриптового движка :)

olegd ★★ ()
Ответ на: комментарий от olegd

Блин, так бы сразу и написал.

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

Тем более, что если скриптовый движок медленный, то вся эта экономия на спичка ничего не стоит.

Закапывай тред.

anonymous ()

Перебираешь все узлы первого XML (GetRootElement, GetFirstChild, GetNextSibling), для каждого находишь (или нет) узел с таким же путём во втором XML. Если не нашёл - добавляешь путь в список «удалённых узлов». Если нашёл - сравниваешь атрибуты (GetAttributesCount + GetAttributeByIndex у первого узла, GetAttributeByName - у второго). Если атрибуты изменились - добавляешь узел в список «изменённые узлы». Если изменилось содержимое - тоже. Потом меняешь местами XML-ки. Если не нашёл узел - добавляешь его в список «добавленные узлы». Вот и всё. Оптимизация потом.

Beewek ()
Ответ на: комментарий от Beewek

узел с таким же путём во втором XML

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

slovazap ★★★★★ ()
Ответ на: комментарий от Beewek

Перебираешь все узлы первого XML

Если не нашёл - добавляешь путь в список

Если атрибуты изменились - добавляешь узел в список

Потом меняешь местами XML-ки.

Примерно так и было с самого начала. Я искал способ проще. Когда стал преобразовывать XML в списки и сравнивать списки, сократил текст скрипта втрое.

olegd ★★ ()
Ответ на: комментарий от slovazap

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

Можно запоминать обработанные узлы и больше к ним не возвращаться. Но получается громоздко.

olegd ★★ ()

Требуется написать скрипт (на внутрикорпоративном скриптовом языке) для сравнения 2 файлов данных в формате XML

Как успехи?

anonymous ()