Могу ли я использовать алгоритм сравнения открытого текста для отслеживания изменений XML?

https://stackoverflow.com/questions/2430083

19-09-2019
|

Вопрос

Я работаю в Flex/AS3 над (для простоты) редактором XML.Мне нужно предоставить функцию отмены/повтора.

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

Мой вопрос: могу ли я использовать алгоритм сравнения открытого текста для отслеживания этих изменений XML?

Мои исследования в Интернете показывают, что я не могу Сделай так.Однако я явно что-то упускаю.Plaintext diff обеспечивает функциональность, которая предположительно:

diff(text, text') -> diffs
patch(text, diffs) -> text'

XML — это просто текст, так почему я не могу просто использовать diff() и patch() для надежного преобразования текста?

Например:Допустим, я поэт.Когда я пишу стихи, я использую много причудливых знаков препинания...Знаете, например, <, / и >.(Возможно, вы поймете, к чему я клоню...) Если я пишу свои стихи в приложении, которое использует различия для обеспечения функции отмены/повтора, искажаются ли мои стихи, когда я отменяю/повторяю свои изменения?Это просто текст!Почему это имеет значение для алгоритма?

Я явно чего-то не понимаю... Спасибо за объяснение!:)

ОБНОВЛЯТЬ:

Некоторые обсуждения, с которыми я столкнулся относительно различия XML с помощью алгоритма открытого текста:

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

Решение

Я автор текстовой библиотеки diff/match/patch от Google.

Ключевой вопрос заключается в том, точны ли ваши патчи.В идеальном мире:

  diff(old_text, new_text) -> edits
  patch(edits, old_text) -> new_text

Обратите внимание, что базовый текст (old_text) один и тот же в обеих операциях.В этом идеальном случае простые текстовые различия и исправления будут работать идеально, независимо от типа контента.Если этот случай относится к вам, то все готово.

Проблема связана с нечетким исправлением.Вот соответствующий пример:

  diff(old_text, new_text) -> edits
  patch(edits, old_forked_text) -> new_forked_text

Обратите внимание, что базовый текст не одинаков в обеих операциях.Они должны быть похожими, но операция исправления теперь должна использовать «суждение» о том, что она должна делать.Некоторые патчи могут идеально подходить, как указано в редактировании, другие, возможно, потребуется настроить по положению, другие, возможно, потребуется настроить для измененного контекста, третьи могут вообще не подходить и их следует удалить.Если ваш алгоритм исправлений не учитывает структуру XML при принятии своих решений, вы вполне можете получить неверный XML.Вот образец:

  old_text = Jabberwock<SPAN>Hello<SPAN>World</SPAN></SPAN>
  new_text = Jabberwock<DIV>Hello<SPAN>World</SPAN></DIV>
  diff(old_text, new_text) -> edits
  edits = ["SPAN" -> "DIV" @ character 11,
           "SPAN" -> "DIV" @ character 41]
  old_forked_text = <SPAN>Hello<SPAN>World</SPAN></SPAN>
  patch(edits, old_forked_text) -> new_forked_text
  new_forked_text = <SPAN>Hello<DIV>World</SPAN></DIV>

Давайте посмотрим на это внимательно.Исходный дифференциал вернул два изменения: крайний SPAN был изменен на DIV.Простое изменение.К сожалению, текст, к которому применяется это редактирование, изменился по сравнению с оригиналом.Слово «Бармаглот» удалено.Теперь первое изменение SPAN->DIV соответствует второму тегу SPAN, а не первому.Поскольку алгоритм исправления не учитывает правила XML, это приводит к недопустимому вложению тегов.

Есть некоторые хаки, которые позволяют вам гарантировать корректность XML при использовании текстового патча, но они приводят к некоторой потере гибкости (в исходном вопросе уже есть ссылка на вики-страницу, которую я писал об этом).Конечно, лучшим решением для исправления XML является использование алгоритма сравнения и исправления, учитывающего XML.Они значительно сложнее и дороже, но они существуют.Поищите в Google имена Танкреда Линдхольма и Себастьяна Рённау за огромную работу, которую они проделали в области XML (особенно в отношении DocEng).

Дайте мне знать, если я могу добавить что-нибудь еще.

-- Нил Фрейзер

Другие советы

я использую Вне всякого сравнения все время сравнивать XML-документы.Он в определенной степени понимает XML.

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow