Программа сравнения не читает текст, как человек, и не решает, «что изменилось». Вместо этого она ищет способ превратить один список в другой с помощью наименьшего числа удалений и добавлений. В этой статье объясняется, как diff вычисляет такой ответ и почему результат иногда расходится с ожиданиями человека.
Единица сравнения: строка, слово, символ
Сначала diff разбивает текст на список токенов. Классический diff и git считают одним токеном одну строку. Поэтому если в строке изменился всего один символ, вся строка выводится как «удалена 1 строка + добавлена 1 строка».
Построчное сравнение быстрое и хорошо подходит для ревью кода, но в документах, где длинный абзац записан одной строкой, трудно понять, что именно поменялось. Поэтому многие инструменты сравнивают в два этапа.
- Сравнивают по строкам и находят изменённые строки.
- Объединяют изменённые строки в пары и сравнивают их содержимое ещё раз — по словам или символам.
Этот сайт работает так же. Единицу сравнения внутри строки можно выбрать: слова, фрагменты между пробелами или символы.
Наибольшая общая подпоследовательность (LCS)
Математическая основа diff — наибольшая общая подпоследовательность (Longest Common Subsequence, LCS). Подпоследовательность — это часть элементов, выбранных с сохранением порядка. Например, у ABCABBA и CBABAC самая длинная общая подпоследовательность имеет длину 4 — например, CABA или BABA.
Элементы, вошедшие в LCS, — это то, что «осталось без изменений», а остальные либо «удалены» (есть только слева), либо «добавлены» (есть только справа). Чем длиннее LCS, тем меньше удалений и добавлений. Если длины списков N и M, а длина LCS равна L, то суммарное число удалений и добавлений D равно:
D = (N - L) + (M - L)В примере выше N=7, M=6, L=4, поэтому D = 3 + 2 = 5. Это D называют редакционным расстоянием (когда разрешены только вставки и удаления), а список удалений и добавлений — сценарием редактирования (edit script).
Граф редактирования и алгоритм Майерса
Если искать LCS учебным способом (динамическим программированием), нужна таблица размером N×M. Для двух файлов по 10 000 строк это 100 миллионов ячеек — медленно и затратно по памяти. В 1986 году Юджин Майерс (Eugene W. Myers) в статье «An O(ND) Difference Algorithm and Its Variations» предложил более быстрый метод, который лёг в основу стандартных алгоритмов GNU diff и git.
Майерс сводит сравнение к поиску кратчайшего пути на сетке.
- Путь идёт из левого верхнего угла (0,0) в правый нижний (N,M).
- Шаг вправо — удаление одного элемента левого текста, шаг вниз — добавление одного элемента правого текста. Каждый такой шаг стоит 1.
- Там, где элементы совпадают, можно бесплатно пройти по диагонали. Такой непрерывный диагональный участок называется snake («змейка»).
Путь с наименьшей стоимостью и есть кратчайший сценарий редактирования. Алгоритм Майерса по очереди расширяет «самую дальнюю точку, достижимую за стоимость 0», «самую дальнюю точку за стоимость 1» и так далее, пока не достигнет конца. На каждом шаге достаточно помнить лишь одну самую дальнюю позицию на каждой диагонали, поэтому время работы примерно пропорционально (N+M)×D. Если тексты почти одинаковы, D мало и алгоритм очень быстр; если они совсем разные — медленнее.
Линейная память и middle snake
Чтобы восстановить путь, нужно хранить записи о каждом шаге, и память может расти пропорционально D². В той же статье Майерс описал вариант, где поиск ведётся одновременно с начала и с конца, пока оба направления не встретятся на диагональном участке (middle snake). Если разбить задачу в этой точке на две меньшие и повторять это рекурсивно, память будет расти лишь пропорционально размеру входных данных.
Когда слишком дорого: приближённая эвристика
Если оба входа содержат десятки тысяч строк и сильно различаются, D тоже велико, и (N+M)×D может достигать миллиардов. На этот случай в GNU diff есть эвристика: когда число шагов поиска превышает порог, задача разрезается на той диагонали, которая к этому моменту продвинулась дальше всех. Результат остаётся правильным сценарием редактирования, но кратчайшим он уже быть не обязан. Опция --minimal в GNU diff и в git заставляет искать минимальный результат, даже если это дольше.
Минимальный — не всегда удобный для чтения
Путей с одинаковым редакционным расстоянием может быть несколько. Например, если добавить в код новую функцию, закрывающие скобки } и пустые строки встречаются во многих местах, и алгоритм может сопоставить «} новой функции» с «} существующей». Результат минимален, но человеку читать его неудобно. Именно поэтому git по умолчанию применяет эвристику, сдвигающую границы по отступам, и предлагает другие алгоритмы — patience и histogram. Подробное сравнение — в статье Сравнение алгоритмов diff.
В этом инструменте
Механизм сравнения на этом сайте реализует на JavaScript вариант алгоритма Майерса с линейной памятью, а на больших входных данных переходит к приближённому разбиению по тому же принципу, что и GNU diff. Вычисления идут в Web Worker, поэтому интерфейс не зависает даже на больших файлах. Получив построчный результат, инструмент объединяет в пары похожие по содержанию изменённые строки, помечает их как «изменено» и ещё раз сравнивает их содержимое в выбранных единицах (слова, фрагменты или символы), подсвечивая различия.
Вставьте два текста в сравнение текстов и посмотрите, как меняется результат при разных единицах сравнения внутри строки. О том, как читать результат в формате git, рассказано в статье Как читать unified diff.