Введение
Алгоритмическая задача на парах последовательностей
Самая длинная общая подпоследовательность (LCS) — это самая длинная подпоследовательность, общая для всех последовательностей в наборе последовательностей (часто всего двух последовательностей). Она отличается от самой длинной общей подстроки: в отличие от подстрок, подпоследовательности не обязаны занимать последовательные позиции в исходных последовательностях. Задача вычисления самой длинной общей подпоследовательности является классической задачей в информатике, основой программ сравнения данных, таких как утилита diff, и имеет применение в вычислительной лингвистике и биоинформатике. Она также широко используется системами контроля версий, такими как Git, для согласования множественных изменений, внесенных в репозиторий файлов. Например, рассмотрим последовательности (ABCD) и (ACBAD). У них есть пять общих подпоследовательностей длины 2: (AB), (AC), (AD), (BD) и (CD); две общие подпоследовательности длины 3: (ABD) и (ACD); и нет подпоследовательностей большей длины. Таким образом, (ABD) и (ACD) являются их самыми длинными общими подпоследовательностями.
Решение для двух последовательностей
Проблема LCS обладает оптимальной подструктурой: её можно разбить на более мелкие, простые подзадачи, которые, в свою очередь, также можно разбить на ещё более простые подзадачи, и так далее, пока решение не станет тривиальным. В частности, в LCS подзадачи перекрываются: решения задач высокого уровня часто используют решения задач более низкого уровня. Проблемы, обладающие этими двумя свойствами, эффективно решаются с помощью динамического программирования, при котором решения подзадач запоминаются, то есть сохраняются для последующего повторного использования.
Первое имущество
LCS(X^A, Y^A) = LCS(X, Y)^A для любых строк X, Y и любого символа A, где ^ обозначает конкатенацию строк. Это позволяет упростить вычисление LCS для двух последовательностей, заканчивающихся одним и тем же символом. Например, LCS("BANANA", "ATANA") = LCS("BANAN", "ATAN")^"A". Продолжая для остальных общих символов, LCS("BANANA", "ATANA") = LCS("BAN", "AT")^"ANA".
Определена функция LCS
Пусть две последовательности определены следующим образом: и . Префиксы последовательности — ; префиксы последовательности — . Пусть обозначает множество самых длинных общих подпоследовательностей префиксов и . Этот набор последовательностей задается следующим образом. Чтобы найти НОП (наибольшую общую подпоследовательность) для и , сравните и . Если они равны, то последовательность расширяется этим элементом. Если они не равны, то сохраняется самая длинная из двух последовательностей, и . (Если они имеют одинаковую длину, но не идентичны, то сохраняются обе.) Базовый случай, когда либо или пуста, — это пустая строка, "".
Оптимизация кода
Для повышения производительности алгоритма, описанного выше, можно применить несколько оптимизаций в реальных сценариях.
Сократить время сравнения
Большую часть времени работы наивного алгоритма занимает выполнение сравнений между элементами в последовательностях. Для текстовых последовательностей, таких как исходный код, желательно рассматривать строки как элементы последовательности, а не отдельные символы. Это может означать сравнение относительно длинных строк на каждом шаге алгоритма. Можно применить две оптимизации, которые помогут уменьшить время, затрачиваемое на эти сравнения.
Сократить строки до хэшей
Для уменьшения размера строк в последовательностях можно использовать хеш-функцию или контрольную сумму. То есть, для исходного кода, где средняя строка содержит 60 или более символов, хеш или контрольная сумма для этой строки может быть всего от 8 до 40 символов в длину. Кроме того, случайная природа хешей и контрольных сумм гарантирует более быстрое завершение сравнений, поскольку строки исходного кода редко изменяются в начале. Существует три основных недостатка этой оптимизации. Во-первых, требуется время для предварительного вычисления хешей для обеих последовательностей. Во-вторых, необходимо выделить дополнительную память для новых хешированных последовательностей. Однако, по сравнению с наивным алгоритмом, используемым здесь, оба этих недостатка относительно незначительны. Третий недостаток – это коллизии. Поскольку уникальность контрольной суммы или хеша не гарантируется, существует небольшая вероятность, что два различных элемента будут сведены к одному и тому же хешу. Это маловероятно в исходном коде, но возможно. Поэтому для этой оптимизации гораздо лучше подойдет криптографический хеш, поскольку его энтропия значительно выше, чем у простой контрольной суммы. Однако, преимущества могут не оправдать затрат на настройку и вычислительные ресурсы, необходимые для криптографического хеша, при небольших длинах последовательностей.
Уменьшить требуемое пространство
Если требуется только длина НОД, матрицу можно свести к матрице или к вектору, так как подход динамического программирования требует только текущего и предыдущего столбцов матрицы. Алгоритм Хиршберга позволяет построить саму оптимальную последовательность за то же квадратичное время и с теми же линейными ограничениями по памяти.
Уменьшить пропуск кэша
Чоудхури и Рамачандран разработали алгоритм со временем работы, квадратичным по времени и линейным по объему памяти, для нахождения длины НОД и соответствующей оптимальной последовательности, который на практике работает быстрее алгоритма Хиршберга благодаря более эффективному использованию кэша. Алгоритм обладает асимптотически оптимальной сложностью кэширования в идеальной модели кэша. Примечательно, что сам алгоритм не зависит от характеристик кэш-памяти. Для задач с ограниченным размером алфавита метод четырех русских можно использовать для уменьшения времени работы алгоритма динамического программирования на логарифмический множитель.
Поведение на случайных строках
Начиная с определенной даты, ряд исследователей изучали поведение длины самой длинной общей подпоследовательности, когда две заданные строки выбираются случайным образом из одного и того же алфавита. Когда размер алфавита постоянен, ожидаемая длина LCS пропорциональна длине обеих строк, а константы пропорциональности (зависящие от размера алфавита) известны как константы Хватала — Санкоффа. Их точные значения неизвестны, но доказаны верхние и нижние границы для их значений, и известно, что они растут обратно пропорционально квадратному корню размера алфавита. Показано, что упрощенные математические модели задачи поиска самой длинной общей подпоследовательности описываются распределением Трейси — Видома.