Наибольшая общая подпоследовательность (LCS)
Когда вы сравниваете две версии файла, неизменившиеся строки образуют общую подпоследовательность обеих версий. Найдя самую длинную из них, вы точно узнаете, что было добавлено, а что удалено. Та же идея помогает выравнивать цепочки ДНК и подсказывать исправления опечаток, а решается задача одной из самых изящных таблиц в информатике.
Задача
Подпоследовательность слова сохраняет некоторые его буквы в исходном порядке: ACE — подпоследовательность ABCDE, а EA — нет. Общая подпоследовательность двух слов — это подпоследовательность каждого из них, и задача состоит в том, чтобы найти самую длинную. У слова длины n есть 2ⁿ подпоследовательностей, поэтому перебрать их все безнадежно, как только букв больше нескольких.
Таблица
Пусть len[i][j] — длина наибольшей общей подпоследовательности первых i букв одного слова и первых j букв другого. У пустого слова нет ничего общего с другими, поэтому первая строка и первый столбец равны 0. Если буква i равна букве j, то len[i][j] = len[i − 1][j − 1] + 1: совпадение продолжает то, что было до него. Если нет, len[i][j] — большее из len[i − 1][j] и len[i][j − 1]: отбросьте одну из двух букв и оставьте лучший результат.
Пример
Сравним ABCBDAB с BDCABA. Первая буква второго слова, B, совпадает с B в строке 2; C в третьем столбце совпадает со строкой 3, и так далее, и каждое совпадение прибавляет единицу к клетке слева сверху. Правая нижняя клетка в итоге равна 4. Обратный ход оттуда дает BCBA, но BCAB и BDAB такой же длины: наибольшая общая подпоследовательность не обязательно единственна.
Как прочитать ответ
Начните с правой нижней клетки. Если буквы ее строки и столбца совпадают, эта буква входит в ответ: запишите ее и сделайте шаг по диагонали влево вверх. Иначе перейдите к соседней клетке сверху или слева, у которой значение больше, потому что именно оттуда клетка получила свое значение. Остановитесь на первой строке или первом столбце. Записанные буквы в обратном порядке и есть подпоследовательность.
История и применение
Табличный метод около 1970 года независимо друг от друга нашли несколько человек, среди них Роберт Вагнер и Майкл Фишер, чья статья 1974 года решила тесно связанную задачу о редакционном расстоянии. В 1975 году Дэн Хиршберг показал, как найти подпоследовательность, используя гораздо меньше памяти, а в 1976 году Джеймс Хант и Дуглас Макилрой построили программу Unix diff на наибольших общих подпоследовательностях строк. Биологи применяют ту же идею, добавив оценки, для выравнивания последовательностей ДНК и белков.
Попробуйте сами
Откройте приложение и нажмите Шаг. Две сравниваемые буквы подсвечиваются в заголовках; при совпадении считывается синяя клетка слева сверху, при несовпадении — две синие клетки сверху и слева. Когда таблица заполнена, оранжевый путь поднимается обратно от угла, а буквы ответа появляются под таблицей.
Часто задаваемые вопросы
Сколько времени и памяти нужно алгоритму LCS?
O(m·n) времени для слов длиной m и n. Чтобы прочитать ответ, полная таблица требует и O(m·n) памяти; в 1975 году Дэн Хиршберг показал, как найти саму подпоследовательность, используя всего O(min(m, n)) памяти.
Как diff использует наибольшую общую подпоследовательность?
Он считает каждую строку файла одним символом и находит наибольшую общую подпоследовательность строк двух файлов. Строки из этой подпоследовательности не изменились; остальные строки старого файла были удалены, а остальные строки нового файла — добавлены.
А если слов три или больше?
Таблица получает по измерению на каждое слово, поэтому для трех слов длины n нужно n³ клеток. Для произвольного числа слов задача NP-трудна.
Как LCS связана с редакционным расстоянием?
Если разрешены только вставки и удаления, редакционное расстояние между двумя словами равно их суммарной длине минус удвоенная длина их наибольшей общей подпоследовательности. Если разрешить еще и замены, получится расстояние Левенштейна, которое вычисляется очень похожей таблицей.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробовать наибольшую общую подпоследовательность