Наибольшая общая подпоследовательность

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Задача нахождения наибольшей общей подпоследовательности (англ. longest common subsequence, LCS) — задача поиска последовательности, которая является подпоследовательностью нескольких последовательностей (обычно двух). Часто задача определяется как поиск всех наибольших подпоследовательностей. Это классическая задача информатики, которая имеет приложения, в частности, в задаче сравнения текстовых файлов (утилита diff), а также в биоинформатике.

Подпоследовательность можно получить из некоторой конечной последовательности, если удалить из последней некоторое множество её элементов (возможно пустое). Например, BCDB является подпоследовательностью последовательности ABCDBAB. Будем говорить, что последовательность Z является общей подпоследовательностью последовательностей X и Y, если Z является подпоследовательностью как X, так и Y. Требуется для двух последовательностей X и Y найти общую подпоследовательность наибольшей длины. Заметим, что НОП может быть несколько.

Решение задачи[править | править вики-текст]

Сравним два метода решения: полный перебор и динамическое программирование.

Полный перебор[править | править вики-текст]

Существуют разные подходы при решении данной задачи при полном переборе — можно перебирать варианты подпоследовательности, варианты вычеркивания из данных последовательностей и т. д. Однако в любом случае, время работы программы будет экспонентой от длины строки.

Метод динамического программирования[править | править вики-текст]

A B C B
0 0 0 0 0
D   0 0 0 0 0
C   0 0 0 1 1
B   0 0 1 1 2
A   0 1 1 1 2

Вначале найдём длину наибольшей подпоследовательности. Допустим, мы ищем решение для случая (n1, n2), где n1, n2 — длины первой и второй строк. Пусть уже существуют решения для всех подзадач (m1, m2), меньших заданной. Тогда задача (n1, n2) сводится к меньшим подзадачам следующим образом:

 f(n_1, n_2) = \left \{ 
\begin{array}{ll}
 0, & n_1 = 0 \or n_2 = 0 \\
 f(n_1 - 1, n_2 - 1) + 1, & s[n_1] = s[n_2] \\
 max(f(n_1 - 1, n_2), f(n_1, n_2 - 1)), & s[n_1] \neq s[n_2]
 \end{array}
 \right.

Теперь вернемся к задаче построения подпоследовательности. Для этого в существующий алгоритм добавим запоминание для каждой задачи той подзадачи, через которую она решается. Следующим действием, начиная с последнего элемента, поднимаемся к началу по направлениям, заданным первым алгоритмом, и записываем символы в каждой позиции. Это и будет ответом в данной задаче.

Время работы алгоритма будет \mathrm{O}\,(n_1 \cdot n_2).

См. также[править | править вики-текст]

Нахождение наибольшей общей подпоследовательности (рус.). algolist.ru. Проверено 15 августа 2013. Архивировано из первоисточника 24 августа 2013.