16
правок
Изменения
Нет описания правки
== Определения ==
{{Определение
|definition=
Последовательность <tex> Z </tex> является '''общей подпоследовательностью''' (англ. ''common subsequence'') последовательностей <tex> X </tex> и <tex> Y </tex>, если <tex> Z </tex> является подпоследовательностью как <tex> X </tex>, так и <tex> Y </tex>.
}}
{{Задача
|definition=
Найти '''наибольшую общую подпоследовательность''' (англ. ''longest common subsequence, <tex>LCS</tex>''), которая является самой длинной подпоследовательностью нескольких последовательностей (обычно двух).
}}
== Наивное решение ==
Переберем все различные подпоследовательности обеих строк и сравним их. Тогда искомая <tex>LCS</tex> гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.
== Динамическое программирование ==
Данная задача решается с использованием [[Принцип_оптимальности_на_префиксе | принципа оптимальности на префиксе]].
=== Доказательство оптимальности ===
Пусть имеются последовательности <tex> X = \left \langle x_1, x_2, \dots, x_m \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, \dots, y_n \right \rangle </tex>, а <tex> Z = \left \langle z_1, z_2, \dots, z_k \right \rangle </tex> — их <tex>LCS</tex>.
# Если <tex> x_m = y_n </tex>, то <tex> z_k = x_m = y_n </tex> и <tex> Z_{k - 1} </tex> — <tex>LCS</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>LCS</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>LCS</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>LCS</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>LCS</tex>: тогда есть общая подпоследовательность <tex> W </tex>, длина которой больше <tex> k - 1 </tex>. Добавив к <tex> W </tex> элемент <tex> x_m = y_n </tex>, получим <tex>LCS</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>LCS</tex> <tex> (X </tex> и <tex> ,Y )</tex>.
# Аналогично второму случаю.
}}
=== Построение подпоследовательности ===
Для каждой пары элементов помимо длины <tex>LCS</tex> соответствующих префиксов хранятся и номера последних элементов, участвующих в этой <tex>LCS</tex>.Таким образом, посчитав ответ, можно восстановить всю наибольшую общую подпоследовательность.
=== Псевдокод ===
''<font color="green">// подсчёт таблиц</font>''
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, j - 1)
''<font color="green">// вывод LCS, вызывается как printLCS(prev, x, m, n)</font>'' '''int''' printLCS(prev, x, i, j: '''int'''): '''if''' i == 0 '''or ''' j == 0 ''<font color="green">// пришли к началу LCS</font>''
'''return'''
'''if''' prev[i][j] == pair(i - 1, j - 1) ''<font color="green">// если пришли в lcs[i][j] из lcs[i - 1][j - 1], то x[i] == y[j], надо вывести этот элемент</font>''
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</tex> ==
Заметим, что для вычисления <tex> lcs[i][j] </tex> нужны только <tex> i </tex>-ая и <tex> (i-1) </tex>-ая строчки матрицы <tex> lcs </tex>. Тогда можно использовать лишь <tex> 2 \cdot min(m, n) </tex> элементов таблицы:
'''int''' LCS2(x, y: '''int'''):
'''if''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>''
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] ''<font color="green">// элемент, который был в a[1][j], теперь в предыдущей строчке</font>''
'''if''' x[i] == y[j]
Также можно заметить, что от <tex> (i - 1) </tex>-ой строчки нужны только элементы с <tex> (j - 1) </tex>-го столбца. В этом случае можно использовать лишь <tex> min(m, n) </tex> элементов таблицы:
'''int''' LCS3(x, y: '''int'''):
'''if''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>''
swap(x, y)
m = length(x)
n = length(y)
'''for''' j = 0 '''to ''' n
lcs[j] = 0
d = 0 ''<font color="green">// 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]</font>''
'''for''' i = 1 '''to ''' m '''for''' j = 1 '''to ''' n
tmp = lcs[j]
'''if''' x[i] == y[i]
''<font color="green">// ответ — lcs[n]</font>''
== Длинна Длина кратчайшей общей суперпоследовательности ==Для двух подпоследовательностей <tex> X = \left \langle x_1, x_2, \dots, x_m \right \rangle X_{m - 1}</tex> и <tex> Y = \left \langle y_1, y_2, \dots, y_n \right \rangle Y_{n - 1}</tex> длинна длина кратчайшая общей суперпоследовательности равна
<tex>
|SCS(X,Y)| = n + m - |LCS(X,Y)|
