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

2013-12-03T17:29:39Z

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

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

== Определения ==
{{Определение
|definition=
Последовательность <tex> Z = \left \langle z_1, z_2, ..., z_k \right \rangle </tex> является '''подпоследовательностью''' (subsequence) последовательности <tex> X = \left \langle x_1, x_2, ..., x_m \right \rangle </tex>, если существует строго возрастающая последовательность <tex> \left \langle i_1, i_2, ..., i_k \right \rangle </tex> индексов <tex> X </tex> таких, что для всех <tex> j = 1, 2, ..., k </tex> выполняется соотношение <tex> x_{i_j} = z_j </tex>.
}}
Другими словами, подпоследовательность данной последовательности — это последовательность, из которой удалили ноль или больше элементов. Например, <tex> Z = \left \langle B, C, D, B \right \rangle </tex> является подпоследовательностью последовательности <tex> X = \left \langle A, B, C, B, D, A, B \right \rangle </tex>, а соответствующая последовательность индексов имеет вид <tex> \left \langle 2, 3, 5, 7 \right \rangle </tex>.
{{Определение
|definition=
Последовательность <tex> Z </tex> является '''общей подпоследовательностью''' (common subsequence) последовательностей <tex> X </tex> и <tex> Y </tex>, если <tex> Z </tex> является подпоследовательностью как <tex> X </tex>, так и <tex> Y </tex>.
}}
== Постановка задачи ==
Даны две последовательности: <tex> X = \left \langle x_1, x_2, ..., x_m \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, ..., y_n \right \rangle </tex>. Требуется найти общую подпоследовательность <tex> X </tex> и <tex> Y </tex> максимальной длины. Заметим, что таких подпоследовательностей может быть несколько.

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

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

Данная задача решается с использованием принципа оптимальности на префиксе.

=== Доказательство оптимальности ===
{{
Теорема|statement=
Пусть имеются последовательности <tex> X = \left \langle x_1, x_2, ..., x_m \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, ..., y_n \right \rangle </tex>, а <tex> Z = \left \langle z_1, z_2, ..., z_k \right \rangle </tex> — их НОП.

# Если <tex> x_m = y_n </tex>, то <tex> z_k = x_m = y_n </tex> и <tex> Z_{k - 1} </tex> — НОП <tex> X_{m - 1} </tex> и <tex> Y_{n - 1} </tex>
# Если <tex> x_m \neq y_n </tex>, то из <tex> z_k \neq x_m </tex> следует, что <tex> Z </tex> — НОП <tex> X_{m - 1} </tex> и <tex> Y </tex>
# Если <tex> x_m \neq y_n </tex>, то из <tex> z_k \neq y_n </tex> следует, что <tex> Z </tex> — НОП <tex> X </tex> и <tex> Y_{n - 1} </tex>

|proof=
# Если бы выполнялось <tex> z_k \neq x_m </tex>, то к <tex> Z </tex> можно было бы добавить элемент <tex> x_m = y_n </tex>, и тогда получилась бы общая подпоследовательность длины <tex> k + 1 </tex>, что противоречит предположению, что <tex> Z </tex> — НОП. Значит, выполняется <tex> z_k = x_m = y_n </tex>. Значит, <tex> Z_{k - 1} </tex> — общая подпоследовательность <tex> X_{m - 1} </tex> и <tex> Y_{n - 1} </tex>. Докажем от противного, что <tex> Z_{k - 1} </tex> — НОП: тогда есть общая подпоследовательность <tex> W </tex>, длина которой больше <tex> k - 1 </tex>. Добавив к <tex> W </tex> элемент <tex> x_m = y_n </tex>, получим НОП <tex> X </tex> и <tex> Y </tex>, длина которой больше <tex> k </tex> (т.е. больше длины <tex> Z </tex>), что приводит к противоречию.
# Если <tex> z_k \neq x_m </tex>, то <tex> Z </tex> — общая подпоследовательность <tex> X_{m - 1} </tex> и <tex> Y </tex>. Пусть существует их общая подпоследовательность <tex> W </tex>, длина которой превышает <tex> k </tex>. Она также является общей подпоследовательностью <tex> X </tex> и <tex> Y </tex>, что противоречит предположению о том, что <tex> Z </tex> (длины <tex> k </tex>) — НОП <tex> X </tex> и <tex> Y </tex>.
# Аналогично второму случаю.
}}

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

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

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

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

=== Псевдокод ===
<tex> x </tex>, <tex> y </tex> — данные последовательности; <tex> lcs[i][j] </tex> — НОП для префикса длины <tex> i </tex> последовательности <tex> x </tex> и префикса длины <tex> j </tex> последовательности <tex> y </tex>; <tex> prev[i][j] </tex> — пара индексов элемента таблицы, соответствующего оптимальному решению вспомогательной задачи, выбранной при вычислении <tex> lcs[i][j] </tex>.

// подсчёт таблиц
LCS(x, y)
m = length(x)
n = length(y)
for i = 1 to m
lcs[i][0] = 0
for j = 0 to n
lcs[0][j] = 0
for i = 1 to m
for j = 1 to n
if x[i] == y[j]
lcs[i][j] = lcs[i - 1][j - 1] + 1
prev[i][j] = pair(i - 1, j - 1)
else
if a[i - 1][j] >= a[i][j - 1]
lcs[i][j] = lcs[i - 1][j]
prev[i][j] = pair(i - 1, j)
else
lcs[i][j] = lcs[i][j - 1]
prev[i][j] = pair(i, j - 1)

// вывод НОП, вызывается как printLCS(prev, x, m, n)
printLCS(prev, x, i, j)
if i == 0 or j == 0 // пришли к началу НОП
return
if prev[i][j] == pair(i - 1, j - 1) // если пришли в lcs[i][j] из lcs[i - 1][j - 1], то x[i] == y[j], надо вывести этот элемент
printLCS(prev, x, i - 1, j - 1)
print x[i]
else
if prev[i][j] == pair(i - 1, j)
printLCS(prev, x, i - 1, j)
else
printLCS(prev, x, i, j - 1)

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

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
lcs[0][j] = 0
lcs[1][j] = 0
for i = 1 to m
lcs[1][0] = 0
for j = 1 to n
lcs[0][j] = lcs[1][j] // элемент, который был в a[1][j], теперь в предыдущей строчке
if x[i] == y[j]
lcs[1][j] = lcs[0][j - 1] + 1
else
if lcs[0][j] >= lcs[1][j - 1]
lcs[1][j] = lcs[0][j]
else
lcs[1][j] = lcs[1][j - 1]
// ответ — lcs[1][n]

Также можно заметить, что от <tex> (i - 1) </tex>-ой строчки нужны только элементы с <tex> (j - 1) </tex>-го столбца. В этом случае можно использовать лишь <tex> min(m, n) </tex> элементов таблицы:

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
lcs[j] = 0
d = 0 // d — дополнительная переменная, в ней хранится lcs[i - 1][j - 1]
// в lcs[j], lcs[j + 1], …, lcs[n] хранятся lcs[i - 1][j], lcs[i - 1][j + 1], …, lcs[i - 1][n]
// в lcs[0], lcs[1], …, lcs[j - 1] хранятся lcs[i][0], lcs[i][1], …, lcs[i][j - 1]
for i = 1 to m
for j = 1 to n
tmp = lcs[j]
if x[i] == y[i]
lcs[j] = d + 1
else
if lcs[j] >= lcs[j - 1]
lcs[j] = lcs[j] // в lcs[j] и так хранится lcs[i - 1][j]
else
lcs[j] = lcs[j - 1]
d = tmp
// ответ — lcs[n]

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

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

Викиконспекты - Вклад участника [ru]

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