LINUX.ORG.RU

Сравнить два фрагмента текста и выделить разницу

 , ,


0

2

Всем привет.

Допустим есть два фрагмента текста A и B. Нужно сравнить текст B с текстом A и отличающиеся фрагменты (это могут быть как строки целиком, так и подстроки, и отдельные символы) обрамить, скажем в [].

Пример:

A:
...
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.
...
---
B:
...
Lorem zaebok dolor sit ahuet, consectetur(c) adipiscing(tm) elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua...
...
---
RESULT:
...
Lorem [zaebok] dolor sit [ahuet], consectetur[(c)] adipiscing[(tm)] elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.[..]
...

Подскажите алгоритм, который позволяет такое провернуть.


[ahuet]

Почему не a[hu]et? Или даже

... dolor sit a[huet, consectetur(c) adipiscing(t]m[) ]e[li]t ...

anonymous
()

Гугли “Shortest Edit Script”. Для его вычисления можно воспользоваться O(ND)[1] и O(NP)[2] алгоритмами. Реализацию[2] в продакшене можно увидеть, например, в исходниках Discourse, где он используется для вычисления разницы между версиями сообщений.

——————————

  1. “An O(ND) difference algorithm and its variations” (Eugene Myers, 1986).
  2. “An O(NP) Sequence Comparison Algorithm” (Sun Wu, Udi Manber, Gene Myers, 1989).
theNamelessOne ★★★★★
()
Ответ на: комментарий от theNamelessOne

Фундаментальненько. Спасибо.

Sektor
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.