STR Строки и тексты Алгоритм
Diff Майерса
Также: Myers' diff algorithm · Myers diff · O(ND) difference algorithm · алгоритм Майерса · кратчайший сценарий правок · shortest edit script · git diff
Какие строки файла удалили и какие вставили, если изменилась малая часть. Таблица редакционного расстояния обходит все N · M клеток. Майерс ищет кратчайший путь в той же сетке волнами по числу правок d и останавливается, как только волна дошла до угла: время O((N + M) · D), где D — число отличий. На этом алгоритме работают GNU diff и git diff по умолчанию.
Каждый коммит этого сайта git показывает как diff: какие строки удалены, какие вставлены, и по три строки вокруг. Вот одна настоящая правка из истории сайта: раздел открытых данных стал загружать курсы валют окнами по 360 дней. Старая версия файла — 37 строк, новая — 53. Ниже — сетка, где по горизонтали строки старой версии, по вертикали новой, а короткие чёрточки по диагонали отмечают пары одинаковых строк. Нажмите ▶: алгоритм Майерса пускает волны — сначала все пути без правок, потом с одной, с двумя — и останавливается, когда волна дойдёт до угла. Выберите другую правку, побольше.
Для этой правки понадобилось D = 18 правок — 17 строк вставлено, одна удалена — и 211 просмотренных точек сетки, хотя в ней 37 · 53 = 1961 клетка. Таблица редакционного расстояния считает их все. На главе курса о хешировании разница ещё заметнее: 642 строки в обеих версиях, шесть правок, 664 точки вместо 412 164 клеток — в шестьсот с лишним раз меньше. Под сеткой — diff, который даёт найденный путь. Для всех пяти правок он строка в строку совпадает с тем, что печатает git diff --diff-algorithm=myers --no-indent-heuristic, если не считать имени функции, которое git дописывает после @@.
Идея
Сравнение двух файлов — это путь по сетке из левого верхнего угла в правый нижний. Шаг вправо — удалить строку старой версии, вниз — вставить строку новой, по диагонали — строка не изменилась, и такой шаг бесплатен. Нужен путь с наименьшим числом платных шагов. Будем искать его волнами: сначала всё, куда можно дойти без правок, потом с одной правкой, с двумя… На каждой диагонали достаточно помнить одну точку — самую дальнюю, куда дошла волна. Как только волна коснулась угла, число правок D найдено, а работа пропорциональна D, а не площади сетки.
Сетка правок и волны
Пусть в старой версии строки a₁…aN, в новой — b₁…bM. Сетка правок — это точки (x, y) с рёбрами вправо и вниз и диагональными рёбрами там, где ax = by. Любой путь из (0, 0) в (N, M) — способ превратить одну версию в другую, а число шагов вправо и вниз — сколько строк удалено и вставлено. Это та же таблица, что в статье о редакционном расстоянии, только без замен: замена строки в diff — это удаление старой и вставка новой.
У точки на сетке есть номер диагонали k = x − y. Диагональный шаг не меняет k, шаг вправо увеличивает его на единицу, вниз — уменьшает. Путь с d платными шагами кончается на одной из диагоналей −d, −d + 2, … , d. Майерс хранит массив V: V[k] — самый дальний x, куда на диагонали k можно дойти за d правок. Переход от d − 1 к d устроен просто: на диагональ k приходят либо шагом вниз с диагонали k + 1, либо шагом вправо с k − 1 — откуда дальше, — а потом идут по диагонали, пока строки совпадают. Такой бесплатный отрезок диагонали называют змейкой.
Вот пример из статьи Майерса 1986 года: ABCABBA превращается в CBABAC. Листинг из раздела с кодом печатает для каждого d самые дальние точки на каждой диагонали:
d = 0: k=+0 (0,0) d = 1: k=-1 (0,1) k=+1 (1,0) d = 2: k=-2 (2,4) k=+0 (2,2) k=+2 (3,1) d = 3: k=-3 (3,6) k=-1 (4,5) k=+1 (5,4) k=+3 (5,2) d = 4: k=-4 (3,7) k=-2 (4,6) k=+0 (5,5) k=+2 (7,5) k=+4 (7,3) d = 5: k=-5 (3,8) k=-3 (4,7) k=-1 (5,6) k=+1 (7,6) D = 5, the longest common subsequence has 4 letters -A -B C +B A B -B A +C
На пятой волне диагональ k = 1 доходит до (7, 6) — до угла. Путь назад по сохранённым волнам даёт сценарий: удалить A и B, оставить C, вставить B, оставить A и B, удалить B, оставить A, вставить C. Пять правок, и общих букв осталось четыре: D = N + M − 2 · LCS, где LCS — длина наибольшей общей подпоследовательности. Выберите этот пример в сцене — сетка нарисована клетками, как в статье.
Почему волны находят кратчайший путь
Самый дальний путь с d правками, кончающийся на диагонали k, можно получить так: взять самый дальний путь с d − 1 правками на диагонали k + 1 и шагнуть вниз или самый дальний на k − 1 и шагнуть вправо — смотря что даёт больший x, — а затем пройти змейку до конца.
Любой путь с d правками на диагонали k устроен так: путь с d − 1 правками на соседней диагонали, один платный шаг и змейка. Змейка самого дальнего пути обязана быть самой длинной: иначе путь можно было бы продлить по диагонали бесплатно. А если его часть с d − 1 правками не самая дальняя на своей диагонали, заменим её самой дальней: после того же платного шага мы окажемся на диагонали k не раньше, и змейка от более далёкой точки проходит по тем же диагональным рёбрам, что и от ранней, поэтому закончится не ближе. Так самый дальний путь всегда можно составить из самого дальнего пути предыдущей волны, шага и самой длинной змейки — это и вычисляет алгоритм.
Первое d, при котором какая-нибудь волна доходит до угла (N, M), равно наименьшему числу удалений и вставок D. Алгоритм делает O((N + M) · D) шагов.
Угол лежит на диагонали N − M. Если путь с d правками туда существует, то самая дальняя точка на этой диагонали после волны d — не ближе его конца, то есть сам угол. Значит, волна D дойдёт до угла, а более ранние — нет. Без змеек волна d — это d + 1 вычислений по формуле, всего O(D²). Змейки, как считает Майерс, проходят по диагональным рёбрам в полосе между диагоналями −D и D, а в ней не больше (2D + 1) · min(N, M) точек. Вместе — O((N + M) · D).
Это поиск в ширину по графу, где диагональные рёбра весят ноль, а остальные — единицу: все вершины на расстоянии d обходятся до вершин на расстоянии d + 1, а нулевые рёбра проходятся сразу. Алгоритм Дейкстры на этой сетке тоже нашёл бы ответ, но Майерс замечает больше: из всех точек одной волны на диагонали важна только самая дальняя, поэтому волна — это не множество клеток, а 2d + 1 чисел.
Код
shortest_edit — волны: на каждой волне сохраняется копия V, чтобы потом пройти назад. edit_script идёт из угла назад: по сохранённой волне решает, пришли ли на диагональ сверху или слева, и записывает змейку и платный шаг. unified собирает куски в формате diff -u: изменения и по три строки вокруг, а изменения, между которыми не больше шести одинаковых строк, — в один кусок. При равенстве на диагонали алгоритм выбирает шаг вправо, поэтому в куске удалённые строки идут раньше вставленных — как у git. Листинг ради простоты копирует весь массив V; хватило бы его 2d + 1 рабочих чисел, и тогда копии занимают O(D²).
Столбец «same as git» сравнивает число строк вывода с тем, что напечатал git на этих же файлах, — сам git в песочнице не установлен, поэтому число сохранено вместе с данными. Каждая строка тоже совпадает: мы сравнили вывод целиком, когда готовили данные.
Сколько это стоит
| Способ | Время | Память |
|---|---|---|
| таблица редакционного расстояния | O(N · M) при любом D | O(N · M) с путём, O(min(N, M)) без |
| Майерс, волны | O((N + M) · D), в среднем O(N + M + D²) | O(D²) на копии волн |
| Майерс, серединная змейка | O((N + M) · D) | O(N + M) |
Оценка в среднем — из статьи Майерса: если отличия разбросаны случайно, работа растёт как D², а не как произведение. Хранить все волны не обязательно. Вариант с серединной змейкой пускает волны одновременно из начала и из конца, находит, где они встретились, и решает две половины отдельно — как приём Хиршберга для таблицы редакционного расстояния. Памяти нужно O(N + M), а время то же; так устроены и GNU diff, и git.
Замер: файл из тысячи разных строк и его версии с разным числом правок. Волны Майерса против таблицы, которая считает то же число — удаления и вставки без замен.
Таблица не замечает, сколько правок: миллион клеток при любом D. Майерс при одной правке быстрее неё в Python больше чем в тысячу раз. Пока правок мало, его время почти не растёт: основная работа — пройти змейками одинаковые строки, слагаемое N + M. С сотнями правок вперёд выходит D², как обещает оценка в среднем, но и при 244 правках на тысячу строк Майерс в Python больше чем в десять раз быстрее таблицы. Таблица выигрывает, только когда файлы почти не похожи, — а тогда и diff никому не интересен.
Один diff — несколько записей
Кратчайший путь в сетке часто не единственный. Вставленный кусок, у которого первая или последняя строка совпадает с соседней неизменной строкой, можно сдвинуть на строку вверх или вниз, и число правок останется тем же. В правке с курсами валют так и есть: вставленный блок кончается строкой из одной фигурной скобки, и такая же скобка стоит над ним.
Майерс ставит блок после скобки: так получилось при его правиле выбирать на равенстве шаг вправо. С версии 2.14, вышедшей в 2017 году, git по умолчанию двигает такие блоки эвристикой отступов: выбирает положение, при котором границы куска приходятся на строки с меньшим отступом и на пустые строки. Здесь она поднимает блок на строку, и вставка начинается с открывающей скобки нового тела функции fetch. Ни один вариант не короче другого; это вопрос того, какой легче читать.
Есть и алгоритмы, которые жертвуют кратчайшестью ради читаемости. Patience diff, который придумал Брэм Коэн, сначала сопоставляет строки, встречающиеся в обоих файлах ровно по одному разу, — заголовки функций, а не скобки и пустые строки, — и только между ними сравнивает остальное. Histogram diff, пришедший в git из JGit, развивает ту же идею. Оба включаются флагом --diff-algorithm, и оба могут дать diff длиннее, чем у Майерса.
Майерс и редакционное расстояние
Это одна задача в двух постановках. Редакционное расстояние разрешает замену буквы за единицу, diff — только удаления и вставки. Без замен расстояние равно N + M − 2 · LCS, и таблица, и волны считают одно и то же число. Различается порядок обхода. Таблица заполняется по строкам, клетка за клеткой, потому что каждой клетке нужны три соседки. Волны обходят ту же сетку по возрастанию стоимости: сначала всё, что стоит ноль правок, потом одну. Поэтому у Майерса работа пропорциональна ответу, а у таблицы — площади. Тот же приём — считать по диагоналям в порядке роста стоимости — для редакционного расстояния с заменами в 1985 году описал Эско Укконен; о его полосе вокруг диагонали — в статье о редакционном расстоянии.
Где работает
- git. Сравнение в git написано на основе библиотеки LibXDiff Давиде Либенци. Алгоритм по умолчанию — Майерс с серединной змейкой и отсечками для очень дорогих случаев;
--minimalотключает отсечки,--patienceи--histogramвыбирают другие алгоритмы, а эвристика отступов двигает куски после поиска. - GNU diff. Код сравнения из gnulib прямо ссылается на статью Майерса. Чтобы на больших непохожих файлах не тратить квадратичное время, он использует отсечку Пола Эггерта, если не задан
--minimal. - Слияние веток. Чтобы слить две ветки, каждую сравнивают с общим предком, а потом объединяют куски изменений. Кратчайший diff здесь важен: чем меньше лишних правок, тем меньше ложных конфликтов.
- Любые почти одинаковые последовательности. Сравнение вывода программы с образцом в тестах, слов в двух редакциях текста, записей в двух выгрузках базы: везде, где отличий намного меньше, чем элементов.
История
Первый diff в Unix написали Джеймс Хант и Дуглас Макилрой в Bell Laboratories в середине 1970-х, по алгоритму наибольшей общей подпоследовательности. Время его работы зависело от числа пар совпадающих строк, а оно бывает огромным, например, в файлах с множеством пустых строк. Задачу найти алгоритм, время которого зависит от числа отличий, поставил Уэбб Миллер, а решил Юджин Майерс. Статья «An O(ND) difference algorithm and its variations» поступила в журнал Algorithmica в июне 1985 года и вышла в первом томе журнала в 1986-м. В ней Майерс пишет, что на основе алгоритма сделана новая реализация diff, обычно в два–четыре раза быстрее версии из System V, и что она сравнила две последовательности по 1,5 миллиона байт с отличием больше 500 менее чем за две минуты на машине VAX 785. Позже Майерс был одним из авторов программы BLAST, которой ищут похожие последовательности в базах ДНК и белков, а в компании Celera Genomics участвовал в расшифровке генома человека.
Задачи
Найти, сколько строк удалить и вставить между двумя версиями файла в сотню тысяч строк, когда отличий немного. Таблица на десять миллиардов клеток не поместится ни во время, ни в память.
Сколько строк поменялосьДанные: История коммитов legost.in