Как различать иерархические данные?

Question

Существуют ли инструменты, которые различают иерархии?

IE, рассмотрим следующую иерархию:

A has child B.
B has child C.

по сравнению с:

A has child B.
A has child C.

Мне нужен инструмент, который показывает, что C перешел от потомка B к потомку A. Существуют ли такие утилиты? Если конкретных инструментов нет, я не против написания своих собственных, так какие же хорошие алгоритмы применимы к этой проблеме?

Answer 1

Отличным общим ресурсом для различий иерархий (не только XML, HTML и т. Д.) Является проект github Hierarchical-Diff , основанный на небольшом количестве исследований Дартмута. У них есть довольно обширный список связанных работ в диапазоне от различий в XML до различий в файлах конфигурации и различий в HTML.

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

Answer 2

Вы могли бы рассмотреть наши SmartDifferencer инструменты.

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

Эти компьютерные исходные коды имеют именно ту структуру «иерархии», которую вы предлагаете;Гнездо различных конструкций.Специально для вашей темы, как правило, блоки кода могут вкладываться в блоки кода.Инструменты SmartDifferencer используют точные парсеры целевого языка для «деконструкции» исходного текста в эти иерархические объекты.У нас есть Smart Differencer для XML, в котором вы можете писать вложенные теги.

Ответ не сообщается как «N-й ребенок M переместился», хотя он фактически вычисляется таким образом, работая с деревьями разбора, созданными парсерами.Скорее это сообщается как «фрагмент кода типа в строке x coly, чтобы строка colb переместилась /..."

Answer 3

Ответ, мой добрый сэр: Поиск в глубину , также известный как обход в глубину.Вы можете найти использование шаблона Visitor .

Вы не можете бросить мертвую кошку, не выбрав для этого какую-то реализацию при сравнении деревьев XML.Возьмите гусак на diffxml для примера.