Алгоритмы сравнения текстов Myers Diff и LCS: теория и разбор

Фундаментальная математическая формулировка diff сводится к нахождению LCS (Longest Common Subsequence) — самой длинной последовательности элементов, которая содержится в обеих сравниваемых строках без нарушения их взаимного порядка.

Если у нас есть строка A длиной M и строка B длиной N, классическое решение через динамическое программирование строит матрицу DP[M+1][N+1]:

`javascript
if (A[i - 1] === B[j - 1]) {
DP[i][j] = DP[i - 1][j - 1] + 1;
} else {
DP[i][j] = Math.max(DP[i - 1][j], DP[i][j - 1]);
}
`

Сложность алгоритма по времени и памяти составляет O(M × N). Для текстов из сотен строк это вычисляется за миллисекунды прямо в браузере.

Полезный инструмент: Проверить работу алгоритма на реальных строках кода можно через инструмент сравнения текста Diff.

Полезный инструмент: Для предварительной очистки сравниваемых списков используйте инструмент дедупликация строк.

Для файлов исходного кода из тысяч строк матрица O(MN) требует слишком много оперативной памяти. В 1986 году Юджин Майерс опубликовал алгоритм *«An O(ND) Difference Algorithm and Its Variations»*, ставший де-факто мировым стандартом в GNU diff и Git.

Майерс переформулировал задачу diff как поиск кратчайшего пути на графе редактирования (Edit Graph):
• Перемещение вправо по оси X соответствует удалению символа из строки A;
• Перемещение вниз по оси Y соответствует добавлению символа в строку B;
• Диагональное перемещение (x+1, y+1) бесплатно (символы совпадают).

Параметр D отражает минимальное количество вставок и удалений (различий). Если тексты похожи, D мало, и алгоритм Майерса находит кратчайший путь за время O(N × D), что на порядки быстрее классической матрицы DP.

В веб-утилитах выбор токенизации определяет информативность результата:

1. Построчный diff (Line-by-line): входной текст разбивается по символу перевода строки \n. Идеально для программного кода, списков и конфигов;
2. Пословный diff (Word-by-word): текст разбивается на слова регулярным выражением \S+|\s+. Идеально для редактирования статей, копирайтинга и договоров, когда внутри длинного абзаца заменили всего 2–3 слова;
3. Посимвольный diff (Character): применяется для исправления опечаток в коротких строках и токенах.