Сравнить XML

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

Кого отсортировать?

perl Xml::Simple.

System.Xml.Linq

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

perl Xml::Simple.

Перл недоступен.

System.Xml.Linq

.Net недоступен.

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

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

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

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

алгоритмом Левенштайна

Это? https://ru.wikipedia.org/wiki/Расстояние_Левенштейна

Спасибо за общую информацию, но столь глубоко пока не лезу.

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

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

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

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

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

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

Владимир

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

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

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

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

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

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

Владимир

строишь dom по исходному xml, пытаешься добавить в dom второй xml, если есть незадвоенные элементы - документы не равны

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

Так и сделал.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

А для abc, cba тоже будет совпадать. Хороший алгоритм, ничего не скажешь.

Это где ты нашел систему без перла?

Ты имеешь в виду случай, когда в XML-е будет массив однотипных элементов? Такой случай придётся обрабатывать отдельно, конечно.

В докере.

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

Как успехи?

Как успехи?

Последний абзац стартового поста. Через сортировку списков получилось читаемее.