Задача о наибольшей общей подпоследовательности

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

Определения

Определение:

Последовательность [math] Z = \left \langle z_1, z_2, ..., z_k \right \rangle [/math] является подпоследовательностью (subsequence) последовательности [math] X = \left \langle x_1, x_2, ..., x_m \right \rangle [/math], если существует строго возрастающая последовательность [math] \left \langle i_1, i_2, ..., i_k \right \rangle [/math] индексов [math] X [/math] таких, что для всех [math] j = 1, 2, ..., k [/math] выполняется соотношение [math] x_{i_j} = z_j [/math].

Другими словами, подпоследовательность данной последовательности — это последовательность, из которой удалили ноль или больше элементов. Например, [math] Z = \left \langle B, C, D, B \right \rangle [/math] является подпоследовательностью последовательности [math] X = \left \langle A, B, C, B, D, A, B \right \rangle [/math], а соответствующая последовательность индексов имеет вид [math] \left \langle 2, 3, 5, 7 \right \rangle [/math].

Определение:

Последовательность [math] Z [/math] является общей подпоследовательностью (common subsequence) последовательностей [math] X [/math] и [math] Y [/math], если [math] Z [/math] является подпоследовательностью как [math] X [/math], так и [math] Y [/math].

Постановка задачи

Даны две последовательности: [math] X = \left \langle x_1, x_2, ..., x_m \right \rangle [/math] и [math] Y = \left \langle y_1, y_2, ..., y_n \right \rangle [/math]. Требуется найти общую подпоследовательность [math] X [/math] и [math] Y [/math] максимальной длины. Заметим, что таких подпоследовательностей может быть несколько.

Наивная идея решения

Переберем все различные подпоследовательности обеих строк и сравним их. Мы гарантированно найдем искомую НОП, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.

Динамическое программирование

Решение

Обозначим как [math] a[i][j] [/math] НОП префиксов данных последовательностей, заканчивающихся в элементах с номерами [math] i [/math] и [math] j [/math] соответственно. Получаем следующее рекуррентное соотношение:

[math] a[i][j] = \begin{cases} 0, & i = 0\text{ or }j = 0 \\ a[i - 1][j - 1] + 1, & x[i] = y[j] \\ max(a[i][j - 1], a[i - 1][j]), & x[i] \neq y[j] \end{cases} [/math]

Очевидно, что сложность алгоритма составит [math] O(mn) [/math], где [math] m [/math] и [math] n [/math] — длины последовательностей.

Доказательство оптимальности

База: при [math] i = 0 [/math] или [math] j = 0 [/math] длина одной из последовательностей равна нулю, поэтому и их НОП тоже нулевой длины.

Переходы: предположим, что некоторое значение [math] a[i][j] [/math] посчитано неверно. Однако, в случае различия соответствующих символов, они не могут одновременно участвовать в НОП, а значит ответ действительно равен формуле для случая с различными символами. В случае же равенства, ответ не может быть больше, чем [math] a[i - 1][j - 1] + 1 [/math], так как тогда неверно посчитано значение [math] a[i - 1][j - 1] + 1 [/math].

Построение подпоследовательности

Для каждой пары элементов будем хранить не только длину НОП соответствующих префиксов, но и номера последних элементов, участвующих в этой НОП.Таким образом, посчитав ответ, мы сможем восстановить всю наибольшую общую подпоследовательность.

Псевдокод

X, Y — данные последовательности; a[i][j] — НОП для префикса длины i последовательности X и префикса длины j последовательности Y; b[i][j] — пара индексов элемента таблицы, соответствующего оптимальному решению вспомогательной задачи, выбранной при вычислении a[i][j].

 // подсчёт таблиц
 LCS(X, Y)
   m = length(X)
   n = length(Y)
   for i = 1 to m
     a[i][0] = 0
   for j = 0 to n
     a[0][j] = 0
   for i = 1 to m
     for j = 1 to n
       if x[i] = y[i]
         a[i][j] = a[i - 1][j - 1] + 1
         b[i][j] = pair(i - 1, j - 1)
       else
         if a[i - 1][j] >= a[i][j - 1]
           a[i][j] = a[i - 1][j]
           b[i][j] = pair(i - 1, j)
         else
           a[i][j] = a[i][j - 1]
           b[i][j] = pair(i, j - 1)
 
 // вывод НОП
 PrintLCS(b, X, i, j)
   if i = 0 or j = 0 // пришли к началу НОП
     return
   if b[i][j] = pair(i - 1, j - 1) // если пришли в a[i][j] из a[i - 1][j - 1], то X[i] = Y[j], надо вывести этот элемент
     PrintLCS(b, X, i - 1, j - 1)
     print X[i]
   else
     if b[i][j] = pair(i - 1, j)
       PrintLCS(b, X, i - 1, j)
     else
       PrintLCS(b, X, i, j - 1)

Оптимизация для вычисления только длины НОП

Заметим, что для вычисления [math] a[i][j] [/math] нужны только [math] i [/math]-ая и [math] (i-1) [/math]-ая строчки матрицы [math] a [/math]. Тогда можно использовать лишь [math] 2 \cdot min(m, n) [/math] элементов таблицы:

 LCS2(X, Y)
   if length(X) < length(Y) // в таблице будет length(Y) столбцов, и если length(X) меньше, выгоднее поменять местами X и Y
     swap(X, Y)
   m = length(X)
   n = length(Y)
   for j = 0 to n
     a[0][j] = 0
     a[1][j] = 0
   for i = 1 to m
     a[1][0] = 0
     for j = 1 to n
       a[0][j] = a[1][j] // элемент, который был в a[1][j], теперь в предыдущей строчке
       if x[i] = y[i]
         a[1][j] = a[0][j - 1] + 1
       else
         if a[0][j] >= a[1][j - 1]
           a[1][j] = a[0][j]
         else
           a[1][j] = a[1][j - 1]
   // ответ — a[1][n]

Приглядевшись повнимательнее, заметим, что от [math] (i - 1) [/math]-ой строчки нам нужны только элементы с [math] (j - 1) [/math]-го столбца. В этом случае можно использовать лишь [math] min(m, n) [/math] элементов таблицы:

 LCS3(X, Y)
   if length(X) < length(Y) // в таблице будет length(Y) столбцов, и если length(X) меньше, выгоднее поменять местами X и Y
     swap(X, Y)
   m = length(X)
   n = length(Y)
   for j = 0 to n
     a[j] = 0
   d = 0 // d — дополнительная переменная, в ней хранится a[i - 1][j - 1]
   // в a[j], a[j + 1], …, a[n] хранятся a[i - 1][j], a[i - 1][j + 1], …, a[i - 1][n]
   // в a[0], a[1], …, a[j - 1] хранятся a[i][0], a[i][1], …, a[i][j - 1]
   for i = 1 to m
     for j = 1 to n
       tmp = a[j]
       if x[i] = y[i]
         a[j] = d + 1
       else
         if a[j] >= a[j - 1]
           a[j] = a[j] // в a[j] и так хранится a[i - 1][j]
         else
           a[j] = a[j - 1]
       d = tmp
   // ответ — a[n]

Список литературы

Т. Кормен, Ч. Лейзерсон, Р. Риверст, К. Штайн, «Алгоритмы: построение и анализ», 2-е изд., стр 418—425