diff: как работают алгоритмы сравнения текста

Прямой ответ

diff показывает разницу между двумя версиями текста как минимальную последовательность правок. В основе лежит задача о наибольшей общей подпоследовательности (LCS): найти самую длинную последовательность строк, присутствующую в обоих файлах в том же порядке. Всё, что в неё не вошло, — изменения.

Прямое решение LCS требует времени и памяти O(n·m), где n и m — размеры файлов. Для больших файлов это неприемлемо, поэтому используются оптимизированные алгоритмы.

Алгоритм Майерса (используется в Git по умолчанию) работает за O((n+m)·d), где d — длина кратчайшей последовательности правок. Ключевая идея: вместо перебора всех вариантов он ищет кратчайший путь в графе правок, двигаясь по «диагоналям» совпадений. Чем похожи файлы, тем меньше d и тем быстрее сравнение. Это объясняет, почему diff двух почти одинаковых файлов выполняется мгновенно, а сравнение двух совершенно разных — заметно дольше.

Существуют и другие алгоритмы:

В Git алгоритм выбирают флагом:

git diff --histogram           # удобнее читать при переносе блоков
git diff --patience            # группирует изменения вокруг уникальных строк
git config diff.algorithm histogram

Формат вывода unified diff — стандарт обмена правками:

--- a/src/billing.py
+++ b/src/billing.py
@@ -18,7 +18,7 @@ def apply_discount(total, rate):
-    if rate > 1:
-        raise ValueError("rate больше единицы")
+    if not 0 <= rate <= 1:
+        raise ValueError("ставка должна быть в диапазоне 0..1")
     return total * (1 - rate)

Строка @@ -18,7 +18,7 @@ задаёт позиции: в старом файле фрагмент начинается со строки 18 и занимает 7 строк, в новом — то же. Контекстные строки без префикса нужны, чтобы патч можно было применить даже при небольшом смещении.

Практика: где это используется и что настраивать

1. Код-ревью. Качество diff напрямую влияет на качество ревью. Перенос функции на десять строк выглядит как удаление и добавление большого блока, хотя по сути изменена одна строка. Алгоритмы histogram и patience уменьшают этот эффект. О практике ревью — в статье про код-ревью.

2. Тесты на эталонный вывод. При расхождении тест показывает diff между ожидаемым и фактическим; читаемость вывода определяет скорость разбора — см. снимочное тестирование.

3. Трёхстороннее слияние. Git сравнивает не две, а три версии: общую базу и две изменённые. Конфликт возникает, когда обе стороны правили один фрагмент по-разному.

4. Сравнение в Python. Стандартная библиотека содержит модуль difflib:

import difflib

old = open("before.txt").read().splitlines()
new = open("after.txt").read().splitlines()
print("\n".join(difflib.unified_diff(old, new, "before", "after", lineterm="", n=3)))

Для сравнения структур данных удобнее difflib.ndiff или сравнение сериализованных представлений с сортировкой ключей.

5. Игнорирование несущественного. Пробелы, переносы строк и порядок ключей в JSON часто создают шум. Git поддерживает --ignore-all-space и --ignore-blank-lines; для JSON практичнее нормализовать данные перед сравнением, чем ослаблять diff.

Рекомендации:

1. Настройте алгоритм под свой язык. Для кода с частыми переносами блоков histogram даёт заметно более читаемый результат, чем стандартный.
2. Держите коммиты небольшими. Диф большого коммита труднее проверить, и алгоритм чаще даёт запутанный результат. О структуре истории — в статье про rebase и историю коммитов.
3. Не сравнивайте сгенерированные файлы. Диф минифицированного бандла или файла блокировок не несёт информации; сравнивать нужно исходники.
4. Проверяйте diff до отправки. Часть ошибок — случайно оставленные отладочные строки — видна при просмотре собственных изменений.
5. Используйте контекст. Увеличение числа контекстных строк (-U10) помогает понять, в какой функции произошло изменение.

Практический сценарий: ревью не заметило изменение из-за нечитаемого diff

Контекст: в коммите на 600 строк ревьювер одобрил изменения. После выкатки обнаружилось, что в одном месте условие инвертировано.

1. Разбор. Коммит содержал перенос трёх функций между модулями и одно содержательное изменение условия. Стандартный diff показал перенос как удаление и добавление больших блоков, внутри которых затерялась правка условия.
2. Причина 1. Алгоритм по умолчанию не распознаёт перемещение блоков, поэтому весь перенос выглядел как переписывание кода.
3. Причина 2. Перенос и содержательное изменение оказались в одном коммите, поэтому разделить их при просмотре было нельзя.
4. Действия. (а) Включили diff.algorithm = histogram в конфигурации команды; (б) ввели правило: перенос кода и его изменение — отдельные коммиты; (в) в шаблон pull request добавили вопрос о наличии чистых перемещений; (г) для больших изменений включили режим постраничного просмотра с фильтрацией файлов.
5. Результат. В следующем квартале похожее изменение было замечено на ревью: перенос шёл отдельным коммитом, и содержательная правка осталась единственным изменением во втором.

Вывод: читаемость diff — не косметика. Если изменения трудно увидеть, они не будут проверены; настройка алгоритма и разделение коммитов напрямую влияют на число пропущенных дефектов.

FAQ

Почему diff иногда показывает изменение там, где его не было? Потому что сравниваются последовательности строк, а не семантика кода. Перенос строки, изменение отступа или форматирование дают правки, хотя поведение не меняется. Для сравнения с игнорированием пробелов есть отдельные флаги.

Что такое «конфликт слияния» с точки зрения алгоритма? Это ситуация, когда обе стороны изменили пересекающийся фрагмент относительно общей базы, и алгоритм не может выбрать один вариант. Разрешение конфликта — задача человека.

Можно ли применить diff к бинарным файлам? Стандартный текстовый diff для них не работает. Git сравнивает бинарные файлы по хешу и может хранить бинарную дельту, но человекочитаемого представления изменений не будет.

Чем отличается diff от patch? Diff — результат сравнения, patch — тот же текст, используемый как вход для применения изменений. Формат unified diff служит обеим целям, поэтому термины часто употребляют как синонимы.

Источники: Python difflib docs, Git docs (git-diff), Wikipedia (Myers diff algorithm) — ссылки в шапке.