Я могу использовать алгоритм разности простого текста для отслеживания изменений XML?
Я работаю в Flex/AS3 над (для простоты) XML-редактор. Я должен обеспечить функциональность отмены/восстановления.
Конечно, одно решение состоит в том, чтобы снабдить весь исходный текст каждым редактированием. Однако для сохранения памяти я хотел бы сохранить diffs вместо этого (эти diffs будут также использоваться для передачи обновлений сервера для автоматического сохранения).
Мой вопрос - я могу использовать алгоритм разности простого текста для отслеживания этих изменений XML?
Мое исследование в Интернете указывает, что я не могу сделать так. Однако я, очевидно, пропускаю что-то. Разность простого текста обеспечивает функциональность, которая является предположительно:
diff(text, text') -> diffs
patch(text, diffs) -> text'
XML является просто текстом, итак, почему я не могу только использовать разность () и патч () для преобразования текста надежно?
Например: Скажем, то, что я - поэт. Когда я пишу стихи, я использую большую броскую пунктуацию... Вы знаете, как . (Вы могли бы видеть, куда я иду с этим...), Если я пишу свои стихи в приложении, которое использует diffs для обеспечения функциональности отмены/восстановления, моя поэзия становится искаженной, когда я отменяю/восстанавливаю свои редактирования? Это - просто текст! Почему это имеет значение к алгоритму?
Я, очевидно, не получаю что-то здесь... Спасибо за объяснение!:)
ОБНОВЛЕНИЕ:
Некоторое обсуждение я встретился относительно diffing XML с алгоритмом простого текста:
- http://code.google.com/p/google-diff-match-patch/wiki/Plaintext
- Существует ли различная библиотека JS против htmlstring точно так же, как google-diff-match-patch на простом тексте?
Кроме того, я понимаю, что Шаблон "команда" вероятен лучший способ реализовать Отмену/Восстановление. Я упростил свой вариант использования ради простоты, и я действительно все еще думаю, что XML diffing является лучшим подходом.
4 ответа
Я являюсь автором библиотеки plain-text 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>
Давайте внимательно рассмотрим этот пример. Оригинальный diff вернул две правки: изменить крайний SPAN на DIV. Простое изменение. К сожалению, текст, к которому применяется эта правка, изменился по сравнению с оригиналом. Слово "Jabberwock" было удалено. Теперь первое изменение SPAN->DIV совпадает со вторым тегом SPAN, а не с первым. Поскольку алгоритм исправления не знает правил XML, это приводит к незаконно вложенным тегам.
Есть несколько хаков, которые позволяют гарантировать корректность XML при использовании патча с обычным текстом, но они приводят к некоторой потере гибкости (в исходном вопросе уже есть ссылка на страницу вики, которую я написал об этом). Окончательным решением для исправления XML, конечно, является использование XML-совместимого алгоритма разделения и исправления. Они значительно сложнее и дороже, но они существуют. Погуглите имена Танкреда Линдхольма и Себастьяна Рённау, они проделали огромную работу в области XML (особенно в отношении DocEng).
Дайте мне знать, если я могу что-то еще добавить.
-- Нил Фрейзер
Если вы единственный "владелец" данных между точками отмены/повтора, то, конечно, вы можете использовать для них plaintext diff. Как вы отметили, это равносильно набору преобразований.
Однако в зависимости от операций, которые вы предоставляете, plaintext diff может и отдаленно не быть оптимальным для записи отмены/повтора, и вам, возможно, придется специализироваться на некоторых случаях. Представьте себе запись команды ReplaceAll, которая может занимать всего несколько байт плюс строка поиска и замены. Это может создать огромные различия в открытом тексте.
В более широком контексте, если вы разрешаете внешнее редактирование этих документов, и вы больше думаете о том, как хранить дельты на сервере, вы подражаете git или другим системам контроля версий. Вы должны использовать какой-то алгоритм разницы, потому что простая запись ваших команд, очевидно, не является единственным источником преобразований. На этом этапе вы начинаете смешивать undo/redo с контролем версий, и вам, возможно, стоит хорошенько подумать о том, как запутать эти понятия для ваших пользователей.
Я бы оставил отмену/повтор в пределах сеанса редактирования и запретил внешнее редактирование, пока файл открыт. Это позволит вам оптимизировать запись команд для широких случаев, как я уже говорил выше.
Кроме того, либо используйте обычный контроль версий (рассмотрите возможность использования git), либо реализуйте свой собственный способ борьбы с файлами, изменяемыми вне вашего редактора.
Я думаю, вы можете использовать текстовый diff для xml, особенно в вашем случае, когда человек будет писать xml построчно. Я не знаю, какую информацию вы получили о том, что вы не можете этого сделать, но я предполагаю, что это утверждение было основано на том факте, что символы пробела (пробел, табуляция, новая строка ...) несколько отличаются от того, что они находятся в текстовом файле, который может привести к тому, что два разных текстовых файла будут идентичны с точки зрения XML. Но опять же, для редактора, ориентированного на человека, я не понимаю, почему вы не можете.
Я постоянно использую Beyond Compare для сравнения XML-документов. В определенной степени он понимает XML.
Возможно, вам придется предварительно обработать два документа, чтобы текстовое сравнение сделало работу наилучшим образом. Например, в некоторых документах XML порядок некоторых элементов может не иметь значения. Это, безусловно, будет иметь значение для вашего инструмента сравнения! Вам может потребоваться предварительная обработка XML с помощью преобразования XML, которое сортирует эти элементы в общем порядке в обоих файлах, прежде чем сравнивать два отсортированных файла.
Вы также захотите использовать одинаковые отступы для обоих документов. Я считаю полезным начинать каждый элемент с новой строки и использовать одинаковое количество отступов с пробелами для каждого уровня. Если ваш документ становится очень глубоким, вы можете использовать только один или два пробела на уровне, чтобы сравнение поместилось на экране. Возможно, вы даже захотите использовать один атрибут в каждой строке (и отсортировать атрибуты в общем порядке).