Алгоритм управления версиями 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

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

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

Answer 3

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

Answer 4

XMLDiff

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