Как работает git diff: алгоритм Майерса и кратчайший путь

Как git diff находит минимальные изменения: алгоритм Майерса

Вы запускаете git diff десятки раз в день. Видите красные и зелёные строки, стейджите ханки и идёте дальше. Но каждый раз происходит маленькое алгоритмическое чудо: из астрономического числа способов описать «как файл A стал файлом B» инструмент тихо находит один из самых коротких. Это не трюк с форматированием. Это поиск кратчайшего пути. Поняв его, вы начнёте иначе смотреть на код-ревью, merge-конфликты и то, почему git решил, что вы переместили целый блок.

Diff = кратчайший скрипт правок

Забудьте про цветной вывод. Diff между двумя последовательностями строк — A (длины N) и B (длины M) — это edit script: список вставок и удалений, превращающих A в B. Всегда есть много валидных скриптов. Самый тупой: «удалить всё из A, вставить всё из B» — технически верно, но бесполезно. На самом деле вам нужен скрипт с наименьшим числом правок, потому что строки, которые вы не трогали, остались теми же. Поэтому реальная цель — зеркальная: найти наибольшую общую подпоследовательность (LCS) A и B. Всё, что в ней — «неизменно»; всё остальное — вставка или удаление. Оба подхода — одна задача. Если длина LCS равна L, минимальное число правок равно N + M - 2L. Максимизируйте совпадения, минимизируйте правки. Это число — edit distance — и есть то, что реально вычисляет diff.

Почему очевидные подходы не работают

Первая мысль — идти построчно: обходить оба файла синхронно, отмечать различающиеся строки. Это ломается, как только вы вставляете одну строку в начале — всё ниже сдвигается на единицу, и наивный проход сообщает, что изменился весь остаток файла. Бесполезно для код-ревью. Учебниковое решение — таблица динамического программирования для LCS: сетка (N+1)×(M+1), заполнить её, восстановить путь. Это корректно, но требует O(N×M) времени и памяти. Для двух файлов по 10 000 строк это 100 миллионов ячеек. Git не может позволить себе такое на каждый status. Инсайт, делающий реальные diff'ы практичными: редактируемые файлы обычно похожи. Большинство строк совпадает. Поэтому вместо оплаты всей сетки платите только за изменения.

Майерс: diff как кратчайший путь в графе правок

Алгоритм, который Git использует по умолчанию — Eugene Myers' 1986 diff — основан на одном переосмыслении. Разместите файл A вдоль верхней части сетки, а файл B — вдоль левой стороны. Теперь вы перемещаетесь из верхнего левого угла (0,0) в нижний правый (N,M) с тремя ходами: → вправо = удалить строку из A, ↓ вниз = вставить строку из B, ↘ по диагонали = две строки совпадают (БЕСПЛАТНО). Диагональный ход разрешён только когда A[x] == B[y], и, что ключевое, он бесплатный. Ходы вправо и вниз стоят по 1. Итак: минимальный diff — это самый дешёвый путь из угла в угол, а «самый дешёвый» означает «использующий больше всего бесплатных диагоналей». Diff — это задача поиска кратчайшего пути. Длинные диагональные прогоны — Майерс называет их snakes (змеи) — это ваши неизменённые блоки. Горизонтальные и вертикальные шаги между ними — ханки, которые вы видите красным и зелёным.

Трюк: поиск по числу правок, а не по размеру сетки

Майерс не заполняет сетку. Он делает поиск в ширину, упорядоченный по D = количество сделанных правок (D = 0, 1, 2, …), и на каждом уровне отслеживает только самый дальний путь на каждой диагонали k = x - y. Жадно скользите по каждой бесплатной диагонали, прежде чем потратить следующую правку. Как только путь впервые достигает (N,M), D, которое его туда привело, и есть edit distance, а змеи вдоль пути — это diff. D=0: попробуйте пройти прямо по главной диагонали из (0,0). D=1: потратьте одну правку (одно вправо ИЛИ одно вниз), затем скользите как можно дальше. D=2: потратьте две правки, снова скользите... остановитесь, как только путь коснётся (N,M). Поскольку алгоритм останавливается на истинном edit distance D, стоимость составляет O(N×D) — пропорционально размеру файла, умноженному на количество изменений, а не произведению двух размеров файлов. Когда D мало (нормальный случай: несколько отредактированных строк в большом файле), это фактически линейно. Когда вы вставляете совершенно другой файл, D возрастает, и алгоритм плавно деградирует до стоимости DP. Это свойство «быстро, когда похожи» — именно то, что нужно инструменту, работающему при каждом нажатии клавиши.

Где ещё встречается та же идея

Как только вы поняли, что diff — это «кратчайший путь, максимизирующий бесплатные диагонали», вы замечаете этот паттерн повсюду: git diff, git blame, merge — всё построено на этом ядре edit script. Трёхсторонний merge, разрешающий конфликты, — это два diff'а против общего предка, согласованных. Инструменты код-ревью (GitHub, GitLab): представление side-by-side — это визуализация графа правок в виде двух колонок; соединительные подсветки — это змеи. Сравнение текста/JSON/конфигов: сравнение двух ответов API или двух YAML-файлов — та же задача LCS на строках или токенах. (Совет: сначала pretty-print или отсортируйте ключи с обеих сторон — шумный diff обычно означает два по-разному отформатированных набора одних и тех же данных. Прогоните каждую сторону через форматтер JSON перед сравнением, и diff сожмётся до действительно важных изменений.) rsync / бинарные дельты: та же цель кратчайшего скрипта правок, но с другим уровнем детализации (блоки вместо строк). Биоинформатика: выравнивание последовательностей ДНК — это LCS с взвешенными ходами. Та же сетка, более сложные стоимости.

Подводный камень: минимальный diff ≠ читаемый diff

Вот что кусает людей. Майерс находит один из кратчайших edit script'ов — но «меньше всего правок» и «что человек имел в виду» не всегда совпадают. Переместите функцию, и минимальный diff может сопоставить закрывающую } вашей функции с } следующей функции, порождая тот бесячий ханк, где скобки и сигнатуры перемешаны в бессмыслицу. Алгоритм не ошибается; минимизация количества правок просто не знает, что у кода есть структура. (Поэтому Git поставляет --diff-algorithm=patience и histogram — разные эвристики для выбора того, какой из минимальных diff'ов читается лучше.) Так что когда diff выглядит безумно, это не баг. Это кратчайший путь честно не согласен с вашим чувством смысла. Смена алгоритма или просмотр в чистом side-by-side представлении, позволяющем переключаться между unified и split, обычно возвращает человеческий смысл на место.

Практический вывод

В следующий раз, читая diff, не думайте «он сравнил строки». Думайте: «он нашёл самый дешёвый путь через граф правок, взяв каждое бесплатное совпадение, которое смог». Зелёное и красное — это правки; молчаливые неизменённые строки — это змеи, которые алгоритм старался сохранить. Diff — это не сравнение, это доказательство кратчайшего пути, что вот этих нескольких изменений достаточно, чтобы перейти от A к B. Вся идея инструмента, которому вы доверяете каждый коммит. Не магия — просто очень умный способ подсчёта остановок на сетке. Если хотите увидеть, как змеи и правки выстраиваются на реальных данных, я держу бесплатный, ориентированный на приватность diff-чекер, работающий полностью в браузере (без загрузки на сервер) с unified и side-by-side представлениями — удобно, чтобы разглядеть, какие именно строки алгоритм назвал «изменёнными».