Это в первую очередь зависит от вашего использования текста изменений. Когда последовательность включает в себя как вставки, так и удаления, теоретически невозможно узнать подробности каждой вставки, поскольку некоторые из вставленных символов впоследствии могли быть удалены. Поэтому вы должны выбрать, какие результаты вы действительно хотите:
- Для некоторых целей вам необходимо знать точную последовательность изменений, даже если некоторые из вставленных символов следует оставить как «?».
- Для других целей вы должны точно знать, чем новый текст отличается от старого, но не точную последовательность, в которой были внесены изменения.
Я буду техники для достижения каждого из этих результатов. Я использовал обе техники в прошлом, поэтому я знаю, что они эффективны.
Чтобы получить точную последовательность
Это более уместно, если вы внедряете историю или журнал отмены или ищете конкретные действия.
Для этих целей описанный вами процесс, вероятно, является наилучшим, с одним возможным изменением: вместо «нахождения сопоставлений между неизвестными символами и действительными», просто запустите сканирование вперед, чтобы найти текст каждого «Удалить» затем запустите его назад, чтобы найти текст каждой «Вставки».
Другими словами:
Начните с исходного текста и обработайте изменения по порядку. Для каждой вставки вставьте «?» символы. Для каждого удаления удалите указанное количество символов и запишите их как удаленный текст.
Начните с окончательного текста и обработайте изменения в обратном порядке. Для каждого удалить , вставить '?' символы. Для каждой вставки удалите указанное количество символов и запишите их как вставленный текст.
Когда это будет завершено, все ваши записи изменений «Вставить» и «Удалить» будут иметь соответствующий текст, насколько нам известно, и любой текст, который был вставлен и немедленно удален, будет «?» символы.
Чтобы получить разницу
Это больше подходит для маркировки ревизий или сравнения версий.
Для этих целей просто используйте информацию об изменении текста, чтобы вычислить набор целочисленных диапазонов, в которых могут быть найдены изменения, а затем используйте стандартный алгоритм сравнения различий, чтобы найти реальные изменения. Это имеет тенденцию быть очень эффективным при обработке добавочных изменений, но все же дает вам лучшие обновления.
Это особенно хорошо, когда вы вставляете абзац замены, который почти идентичен оригиналу: использование информации об изменении текста будет означать, что весь абзац новый, но использование diff (т. Е. Этот метод) помечает только те серии символов которые на самом деле разные.
Код для вычисления диапазона изменений прост: представить изменение как четыре целых числа (oldstart, oldend, newstart, newend). Выполнить каждое изменение:
- Если изменение начинается до запуска, уменьшите запуск до изменения и уменьшите старое равное количество
- Если changeend после newend, увеличить newend до changeend и увеличить oldend на равную величину
Как только это будет сделано, извлеките диапазон [oldstart, oldend] из старого документа и диапазон [newstart, newend] из нового документа, а затем используйте стандартный алгоритм сравнения для их сравнения.