Алгоритм объединения текстовых дельт в одну «суперструну» - PullRequest
Новая
       16

Алгоритм объединения текстовых дельт в одну «суперструну»

3 голосов
/ 27 июня 2011

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

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

Таким образом, я могу визуализировать различия между текстами, просто применяя различные атрибуты CSS к документу.

Пример

Если автор изменяет предложение таким образом 

-0-    --1--    ---2---    ---3---
' ' -> 'cat' -> 'crate' -> 'crane'

Мой код создает эти дельты 

0-1) <insert 'cat' at 0>
1-2) <insert 'r' at 1> <insert 'e' at 3>
2-3) <remove from 3 to 4> <insert 'n' at 3>

, которые я хочу обработать, чтобы создатьфайл вроде этого: 

<span class="inserted-1">c</span>
<span class="inserted-2">r</span>
<span class="inserted-1">a</span>
<span class="inserted-1 removed-3">t</span>
<span class="inserted-3">n</span>
<span class="inserted-2">e</span>

Вопрос

Какой лучший алгоритм для выполнения этой задачи?Есть имя для этой проблемы?

1 Ответ

4 голосов
/ 27 июня 2011

Вы можете просто объединить свои изменения и отслеживать, когда они были вставлены / удалены.Обратите внимание, что числа дают индекс в строке (и обратите внимание, что удаленные символы не увеличивают индекс).

Шаг 1: 0-1) <insert 'cat' at 0>

  • [0] c inserted at step 1
  • [1] a inserted at step 1
  • [2] t inserted at step 1

Шаг 2: 1-2) <insert 'r' at 1> <insert 'e' at 3>

  • [0] c inserted at step 1
  • [1] r inserted at step 2 <= это было вставлено здесь на этом шаге в позиции 1 </li>
  • [2] a inserted at step 1
  • [3] t inserted at step 1
  • [4] e inserted at step 2 <= это было вставлено здесь на этом шаге в позиции 3 </li>

Обратите внимание, что позиция 'e' была фактически смещена до 4 из-за другой вставки.

Шаг 3: 2-3) <remove from 3> <insert 'n' at 3> <= Я изменил это значение на минимальное различие </p>

  • [0] c inserted at step 1
  • [1] r inserted at step 2
  • [2] a inserted at step 1
  • [3] t inserted at step 1, removed at step 3 <= больше не считается, поэтому следующий индекс такой же </li>
  • [3] n inserted at step 3 <= это было вставлено здесь на этом шаге в позиции 3 </li>
  • [4] e inserted at step 2

Итак, основной алгоритм:

  • ведение списка символов вместе с шагом вводаДля каждого шага и шага удаления
  • выполните
    • . Разложите ваш diff из этого шага на отдельные вставки и удаления символов
    • для вставки нового символа X в позиции Pвыполните следующее:
      • вставьте новый символ X после последнего символа в вашем списке с индексом P, установите шаг вставки для текущего шага и откорректируйте индексы следующих элементов (т.е. добавьте один).
    • для удаления в позиции P сделать
      • пометить символ в вашем списке с индексом P (есть только один из них, который все еще присутствует, то есть, где шаг удаления не установлен) установив шаг удаления на текущий шаг и скорректировав последующие индексы (т.е. вычтя один)

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

Результатом будет список изменений по мереумиротворён в вашем вопросе.Для многих изменений это может стать совершенно нечитаемым, но, тем не менее, оно будет описывать полную историю вашего текста.

...