Алгоритм XML-управления версиями

Question

Я ищу эффективный способ сравнения и получения различий между двумя деревьями синтаксического анализа на основе XML.

Что вы предлагаете, чтобы быть лучшим способом хранения этих различий? Я сделал бы это:

XML A:

<w:p> 
    <w:pPr> 
    <w:spacing w:after="1"/> 
    </w:pPr> 
    <w:r> 
    <w:t>World</w:t> 
    </w:r> 
</w:p> 

XML B:

<w:p> 
    <w:pPr> 
    <w:spacing w:after="1"/> 
    </w:pPr> 
    <w:r> 
    <w:t>ASDF</w:t> 
    </w:r> 
</w:p> 

алгоритм определяет, что "Мир" изменился на "ASDF", а затем магазины:

div: <w:p><w:r><w:t>World</w:t> -> <w:p><w:r><w:t>ASDF</w:t> 

Этого достаточно, чтобы охватить все случаи, которые могут произойти?

Кто-нибудь знает, как это сделать? Любая помощь будет действительно оценена!

Answer 1

Это может усложниться. Посмотрите на этот пример:

<w:p> 
    <w:pPr> 
    <w:spacing w:after="1"/> 
    </w:pPr> 
    <w:r> 
    <w:t>World</w:t> <-- Case 1: this changes to <w:t>ASDF</w:t> 
    <w:t>World</w:t> <-- Case 2: this changes to <w:t>ASDF</w:t> 
    </w:r> 
</w:p> 

Чтобы быть в состоянии распознать оба случая, вы должны будете хранить один, как

div: <w:p><w:r><w:t>World</w:t> -> <w:p><w:r><w:t>ASDF</w:t> 

а другой

div: <w:p><w:r><w:t>World</w:t><w:t>World</w:t> -> <w:p><w:r><w:t>World</w:t><w:t>ASDF</w:t> 

или что-то подобное (вы также можете добавить теги «w: p» для обоих из них, чтобы сделать их действительными XML-деревьями).

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

Answer 2

XMLDiff:

Объясняет, как использовать XML Diff и Patch инструмент, который сравнивает два XML файлы и производит вывод XML из различий, за счет использования типичный сценарий, что читатели могут применяются к их собственным приложениям.

Answer 3

Как насчет простого поиска по глубине по общей части? То есть, выполните поиск по глубине и как только вы столкнетесь с разницей, сохраните его и начните откат. Дополнительная информация, необходимая для создания контекстной части вывода, может быть легко сохранена в стеке «backtrack stack».

Answer 4

Если вы хотите сравнить разницу между двумя деревьями и каким-то образом создать «разницу» из этого сравнения, вы в основном смотрите на вариант отредактируйте расстояние до дерева проблема. Для стартера проверьте this paper.

Более распространенная проблема «редактирования расстояния» - проблема расстояния редактирования для строк. Программное обеспечение для управления версиями, такое как CVS или SVN, которые используют «дельта-кодирование» для хранения изменений , сделанных в файлах, использует варианты алгоритмов расстояния редактирования строк для расчета дельт.Случай с деревьями встречается реже, но определенно интересен.