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

Question

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

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

---

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

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

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

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

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

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

UPDATE:

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

• http://code.google.com/p/google-diff-match-patch/wiki/Plaintext
• Существует ли библиотека JS diff для htmlstring, как google-diff-match-patch для простого текста?

---

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

Answer 1

Я являюсь автором библиотеки diff / match / patch из Google в виде простого текста.

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

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

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

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

  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>

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

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

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

- Нил Фрейзер

Answer 2

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

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

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

Answer 3

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

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

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

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

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

Answer 4

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