DP Динамическое программирование Алгоритм
Наибольшая общая подпоследовательность
Также: Longest common subsequence · LCS · НОП · алгоритм Хиршберга · Hirschberg's algorithm · алгоритм Ханта — Шиманского · Hunt–Szymanski algorithm
Что осталось от абзаца после правки: самая длинная последовательность слов, которая читается и в старой редакции, и в новой. Таблица m × n находит её за квадратичное время, путь назад по таблице называет сами слова, а приём Хиршберга делает то же в линейной памяти. Когда совпадений мало, задача сводится к возрастающей подпоследовательности; для многих строк она NP-трудна.
В октябре 2026 года абзац о правиле Керкгоффса из главы базового курса этого сайта переписали: было 102 слова, стало 89. Сколько слов старой редакции дожило до новой — причём в том же порядке, чтобы их можно было прочесть подряд, пропуская лишнее? 58. Это и есть наибольшая общая подпоследовательность двух редакций. Сцена показывает её прямо в тексте — зачёркнуто то, что вычеркнули, подчёркнуто то, что вписали, — а под текстом таблицу, которая её нашла. Выберите другой абзац или переключитесь на буквы.
Абзацы правили по-разному. У абзаца об ошибке в таблице Ады Лавлейс из 54 слов осталось 33: правка в основном вычёркивала. Абзац о прогнозе времени программы из 51 слова сохранил всего 16 — его переписали почти заново. Это видно и по таблице: у почти неизменного текста оранжевый путь идёт ровной диагональю, у переписанного — ломается на длинные ступени, где одни слова только вычёркивают, а другие только вписывают.
Переключитесь на буквы. Общих знаков у абзаца о Керкгоффсе 488 из 662 — по доле больше, чем слов, но посмотрите, что они читают: «ТОглянеперьмся». Общая подпоследовательность букв честно склеивает случайные совпадения — «т» из «Теперь» с «т» из чего угодно. Поэтому инструменты сравнения работают с кусками покрупнее: со строками, как diff, или со словами, как git diff --word-diff. Чем крупнее кусок, тем меньше случайных совпадений и тем ближе ответ к тому, что сделал человек.
Идея
Наибольшая общая подпоследовательность двух последовательностей — самая длинная последовательность, которую можно получить из каждой, вычёркивая элементы и не меняя порядка остальных. У «КОЛОС» и «СОКОЛ» это «КОЛ»: из «КОЛОС» вычеркнем «ОС», из «СОКОЛ» — «СО». Элементы могут быть чем угодно, что умеет сравниваться на равенство: буквами, словами, строками файла, генами.
Посмотрим на последние элементы двух последовательностей. Если они равны, их можно поставить в конец общей подпоследовательности, и остаётся та же задача без них. Если различны, хотя бы один из них в ответ не входит — выбросим его, и снова осталась та же задача, только короче; какой из двух выбрасывать, неизвестно, поэтому пробуем оба. Ответы для всех пар начал складываются в таблицу (m + 1) × (n + 1), а сам ответ читается по ней путём назад из правого нижнего угла.
Формально: T[i][j] — длина наибольшей общей подпоследовательности первых i элементов a и первых j элементов b.
$$T[i][j] = \begin{cases} T[i-1][j-1] + 1, & a_i = b_j, \\ \max\bigl(T[i-1][j],\; T[i][j-1]\bigr), & a_i \ne b_j, \end{cases} \qquad T[i][0] = T[0][j] = 0.$$Вот таблица для «КОЛОС» и «СОКОЛ», как её печатает листинг:
С О К О Л 0 0 0 0 0 0 К 0 0 0 1 1 1 О 0 0 1 1 2 2 Л 0 0 1 1 2 3 О 0 0 1 1 2 3 С 0 1 1 1 2 3 LCS(КОЛОС, СОКОЛ) = КОЛ, 3 letters
Числа растут террасами: вправо и вниз они не убывают, и каждая следующая терраса на единицу выше предыдущей. Подняться на новую террасу можно только через клетку, где элементы совпали: это единственное место формулы, где появляется «+ 1». В сцене все совпадения отмечены точками, а на новую террасу поднимают те, что стоят в её углу. Именно такие угловые совпадения Джеймс Хант и Дуглас Макилрой назвали кандидатами и построили на них первый diff в Unix — о нём ниже.
Почему таблица права
Если ai = bj, то T[i][j] = T[i − 1][j − 1] + 1. Если ai ≠ bj, то T[i][j] = max(T[i − 1][j], T[i][j − 1]).
Пусть Z — наибольшая общая подпоследовательность начал a[1..i] и b[1..j]. Каждый её элемент сопоставлен месту в a и месту в b, и места растут вдоль Z.
Последние равны. Если Z не использует ни ai, ни bj, припишем ai в конец — получится общая подпоследовательность длиннее Z, чего быть не может. Значит, последний элемент Z сопоставлен ai или bj; перенесём его сопоставление на пару (ai, bj) — он равен обоим, а все предыдущие элементы стоят левее. Без последнего элемента остаётся общая подпоследовательность начал длины i − 1 и j − 1, и она наибольшая: иначе удлинилась бы и Z.
Последние различны. Последний элемент Z один, и он не может быть сопоставлен сразу ai и bj: они разные. Значит, хотя бы один из них в Z не участвует, и Z — общая подпоследовательность пары a[1..i − 1], b[1..j] или пары a[1..i], b[1..j − 1]. Длиннее ответов для этих пар она быть не может, а каждый из них годится и для (i, j). По индукции по i + j верна вся таблица.
Ответ — путь из угла
Таблица хранит только длины. Сами слова восстанавливает путь назад из клетки (m, n): если последние элементы равны, это элемент ответа, и путь идёт по диагонали; если нет — в ту соседнюю клетку, сверху или слева, где число больше. Шаг вверх означает, что слово старой редакции вычеркнули, шаг влево — что слово новой вписали. Так получается не только общая часть, но и вся правка — оранжевая линия в сцене.
Когда числа сверху и слева равны, годятся оба шага, и разные правила дают разные, одинаково длинные ответы. Наш путь при равенстве идёт вверх. Наибольших общих подпоследовательностей бывает очень много, и это не мелочь: на этом споткнётся склейка «общее у первых двух, потом общее с третьей» в задаче о трёх редакциях ниже.
Каждый шаг пути, кроме диагонального, — одна правка, удаление или вставка. Значит, наименьшее число удалений и вставок, которыми одна последовательность превращается в другую, равно m + n − 2·T[m][n]. Это редакционное расстояние без замен, и ровно его ищет diff Майерса — тот же путь по той же сетке, только найденный волнами, без заполнения всей таблицы. Для абзаца о Керкгоффсе 102 + 89 − 2 · 58 = 75 правок: 44 слова вычеркнуто, 31 вписано.
Код
Таблица, путь назад и вывод правки в духе git diff --word-diff: вычеркнутое в [-…-], вписанное в {+…+}. Сначала «КОЛОС» и «СОКОЛ», потом все пять абзацев из сцены и правка первого из них целиком.
Правка абзаца о Лавлейс читается как работа редактора: «Скорее всего» стало «Обычно», «опечатка» — «считают опечаткой», три фразы в середине сжаты в одну. Таблица этого не понимает — она только нашла самую длинную цепочку уцелевших слов, а всё остальное объявила вычеркнутым или вписанным.
Хиршберг: ответ в линейной памяти
Для длины ответа таблица целиком не нужна: строка i считается только из строки i − 1, и хватает двух строк. Но путь назад идёт по всей таблице, и для восстановления самого ответа она, казалось бы, нужна вся. В 1975 году Дэниел Хиршберг подсчитал, во что это обходится: две строки по тысяче знаков — миллион клеток, мегабайт памяти, что тогда было непросто; две строки по десять тысяч — задача может просто не поместиться в оперативную память. И предложил способ найти сам ответ, храня лишь несколько строк.
Возьмём среднюю строку таблицы. Лучший путь где-то её пересекает. Посчитаем таблицу сверху до средней строки — получим для каждого столбца k длину общей части верхней половины a и первых k элементов b. И так же снизу: длину общей части нижней половины a и остатка b после k. Сумма двух чисел — длина лучшего пути через точку (середина, k), и там, где сумма наибольшая, лучший путь и пересекает середину. Теперь задача распалась на две вдвое меньшие по строкам: левый верхний прямоугольник и правый нижний.
Прямоугольники сжимаются к пути: всё, что дальше от него, отброшено после первого же деления. На каждом уровне рекурсии прямоугольники вместе занимают половину площади предыдущего уровня — строки делятся пополам, а столбцы просто распределяются между двумя частями. Площади складываются в mn + mn/2 + mn/4 + … < 2mn: клеток вдвое больше, чем в таблице, а памяти — несколько строк.
Абзац об AlphaGo по буквам — 508 и 665 знаков. Таблица — 337 820 клеток и почти 339 тысяч чисел в памяти. Хиршберг считает 674 942 клетки, ровно вдвое больше, но в памяти у него не больше 1998 чисел — три строки по 666, — и рекурсия глубиной 10. Ответ той же длины, 394 знака. Не обязательно тот же самый: из многих наибольших общих подпоследовательностей Хиршберг выбирает свою, по самому левому из лучших пересечений.
Тот же приём работает везде, где таблица — сетка путей: в редакционном расстоянии, в выравнивании генов, в diff Майерса, где его роль играет серединная змейка. Это разделяй и властвуй поверх динамики: динамика находит, где делить, а деление избавляет от хранения таблицы.
Сколько это стоит
| Что нужно | Время | Память |
|---|---|---|
| только длина | O(m · n) | O(min(m, n)) — две строки |
| длина и сам ответ, таблица | O(m · n) | O(m · n) |
| длина и ответ, Хиршберг | O(m · n), вдвое больше клеток | O(m + n) |
| совпадений мало, Хант и Шиманский | O((r + n) log n), r — число пар равных элементов | O(r + n) |
Замер на случайных строках ДНК одинаковой длины: таблица с ответом, две строки только для длины и Хиршберг.
Все три линии с наклоном 2: вдвое длиннее строки — вчетверо больше работы. В Python Хиршберг медленнее таблицы почти вдвое, как и обещает счёт клеток. В Go иначе: на строках по 4800 букв таблица из 23 миллионов чисел упирается в память, и Хиршберг обгоняет её вдвое, а две строки работают почти втрое быстрее таблицы — у них все данные лежат в кэше процессора.
Существенно быстрее квадрата в общем случае не получится, если верить сильной гипотезе об экспоненциальном времени: в 2015 году Амир Аббуд, Артурс Бачкурс и Вирджиния Василевска Уильямс и независимо Карл Брингманн и Марвин Кюннеманн показали, что алгоритм за O(n2 − ε) для наибольшей общей подпоследовательности опроверг бы эту гипотезу.
Когда совпадений мало
В файле большинство строк уникальны, и пар одинаковых строк в двух версиях намного меньше, чем клеток таблицы: почти всё время таблица тратит на клетки, где ничего не происходит. Первый diff в Unix, который Джеймс Хант и Дуглас Макилрой описали в отчёте Bell Laboratories в июле 1976 года, искал наибольшую общую подпоследовательность строк и смотрел только на «кандидатов» — совпадения в углах террас. Кандидатов на каждой строке файла обычно немного, и их место в текущем списке находит двоичный поиск. По словам авторов, на реальных файлах время и память растут примерно как сумма длин файлов, хотя в худшем случае — как произведение. Год спустя Хант и Томас Шиманский опубликовали этот приём как алгоритм за O((r + n) log n), где r — число пар одинаковых элементов.
Предельный случай особенно красив. Если в обеих последовательностях каждый элемент встречается по одному разу, выпишем для элементов первой их места во второй. Общая подпоследовательность — это набор элементов, места которых растут, то есть наибольшая возрастающая подпоследовательность, и лестница находит её за O(n log n) вместо квадрата. На этом стоит patience diff в git, и это вторая задача ниже: частотные словари двух половин «Войны и мира».
Три строки и больше
Для трёх последовательностей таблица становится кубом: клетка (i, j, k) — ответ для трёх начал, и формула та же: если три последних элемента равны, плюс один к клетке по диагонали, иначе максимум из трёх соседей. Для k строк длины n клеток nk, и уйти от этого, по-видимому, нельзя: в 1978 году Дэвид Майер доказал, что для произвольного числа строк задача NP-трудна, даже если алфавит из двух букв. Хочется посчитать общее у первых двух, а потом общее у результата и третьей, — но это ошибка, и задача о трёх редакциях её ловит на настоящем абзаце курса.
Сколько общего у двух случайных строк? Вацлав Хватал и Дэвид Санкофф в 1975 году доказали, что у двух случайных двоичных строк длины n длина наибольшей общей подпоследовательности в среднем растёт как γn с некоторой постоянной γ. Её точное значение до сих пор неизвестно: доказано лишь, что она между 0,79 и 0,83. Для сравнения, у наибольшей возрастающей подпоследовательности случайной перестановки ответ растёт как 2√n, и это доказано.
Где работает
- Сравнение версий. Первый diff искал наибольшую общую подпоследовательность строк; нынешние обычно ищут кратчайший сценарий правок алгоритмом Майерса, но это та же задача.
git diff --word-diffпоказывает правку по словам, в тех самых скобках[-…-]{+…+}, что печатает наш листинг. - Оценка машинного текста. ROUGE-L, одна из мер, которыми сравнивают машинный пересказ с написанным человеком, считает долю слов в их наибольшей общей подпоследовательности (Чин-Ю Лин, 2004). Порядок слов при этом учитывается, а пропуски не наказываются.
- Биология. Выравнивание генов и белков — та же таблица с весами за совпадения, замены и пропуски: Нидлман — Вунш и Смит — Уотерман.
- Не там, где ждёшь. Модуль
difflibиз стандартной библиотеки Python наибольшую общую подпоследовательность не ищет. Его документация прямо говорит, что он ищет самый длинный общий непрерывный кусок, потом рекурсивно разбирает то, что слева и справа, и не обещает минимальной правки: такие правки, по словам авторов, часто кажутся людям неестественными.
История
Задача выросла из нескольких наук сразу — из сравнения белков и из исправления строк, где в начале 1970-х её решали той же таблицей, что и редакционное расстояние. Самые известные работы о ней появились почти одновременно: Хиршберг защитил диссертацию о наибольшей общей подпоследовательности в 1975 году, в том же году Шиманский выпустил отчёт о её частном случае, а Хант и Макилрой ссылались на обоих, описывая diff. В статье 1975 года Хиршберг оценивал, что для строк по десять тысяч знаков его способу хватит чуть больше трёх минут и ста килобайт памяти — там, где таблице понадобилось бы сто миллионов клеток.
Задачи
Первая — о тексте, который правили дважды: что пережило обе правки. Подвох в том, что общее у трёх нельзя собрать из общего у двух. Во второй списки слишком длинные для таблицы, зато каждое слово встречается в них по разу.
Три редакции Два частотных словаряДанные: Абзацы базового курса legost.in до и после правки (история исходников)