Задача о наибольшей общей подпоследовательности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 4: Строка 4:
 
{{Определение
 
{{Определение
 
|definition=
 
|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 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>.
+
Другими словами, подпоследовательность данной последовательности — это последовательность, из которой удалили ноль или больше элементов. Например, <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=
 
|definition=
Последовательность <tex> z </tex> является '''общей подпоследовательностью''' (common subsequence) последовательностей <tex> x </tex> и <tex> y </tex>, если <tex> z </tex> является подпоследовательностью как <tex> x </tex>, так и <tex> y </tex>.
+
Последовательность <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> максимальной длины. Заметим, что таких подпоследовательностей может быть несколько.
+
Даны две последовательности: <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> максимальной длины. Заметим, что таких подпоследовательностей может быть несколько.
  
 
== Наивная идея решения ==
 
== Наивная идея решения ==
Строка 18: Строка 18:
  
 
== Динамическое программирование ==
 
== Динамическое программирование ==
 +
 +
Данная задача решается с использованием принципа оптимальности на префиксе.
 +
 +
=== Доказательство оптимальности ===
 +
{{
 +
Теорема|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> — их НОП.
 +
 +
1) Если <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>
 +
 +
2) Если <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>
 +
 +
3) Если <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=
 +
1) Если бы выполнялось <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> Z </tex>). Добавив к <tex> W </tex> элемент <tex> x_m = y_n </tex>, получим НОП, длина которой больше <tex> k </tex>, что приводит к противоречию.
 +
 +
2) Если <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>/
 +
 +
3) Аналогично второму случаю.
 +
}}
 +
 
=== Решение ===
 
=== Решение ===
Данная задача решается с использованием принципа оптимальности на префиксе. Обозначим как <tex> lcs[i][j] </tex> НОП префиксов данных последовательностей, заканчивающихся в элементах с номерами <tex> i </tex> и <tex> j </tex> соответственно. Получается следующее рекуррентное соотношение:
+
Обозначим как <tex> lcs[i][j] </tex> НОП префиксов данных последовательностей, заканчивающихся в элементах с номерами <tex> i </tex> и <tex> j </tex> соответственно. Получается следующее рекуррентное соотношение:
  
 
<tex>
 
<tex>
Строка 31: Строка 53:
  
 
Очевидно, что сложность алгоритма составит <tex> O(mn) </tex>, где <tex> m </tex> и <tex> n </tex> — длины последовательностей.
 
Очевидно, что сложность алгоритма составит <tex> O(mn) </tex>, где <tex> m </tex> и <tex> n </tex> — длины последовательностей.
 
=== Доказательство оптимальности ===
 
База: при <tex> i = 0 </tex> или <tex> j = 0 </tex> длина одной из последовательностей равна нулю, поэтому и их НОП тоже нулевой длины.
 
 
Переходы: предположим, что некоторое значение <tex> lcs[i][j] </tex> посчитано неверно. Однако, в случае различия соответствующих символов, они не могут одновременно участвовать в НОП, а значит ответ действительно равен формуле для случая с различными символами. В случае же равенства, ответ не может быть больше, чем <tex> lcs[i - 1][j - 1] + 1 </tex>, так как тогда неверно посчитано значение <tex> lcs[i - 1][j - 1] + 1 </tex>.
 
  
 
=== Построение подпоследовательности ===
 
=== Построение подпоследовательности ===

Версия 03:37, 13 января 2012

Задача нахождения наибольшей общей подпоследовательности (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] 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] Z = \left \langle z_1, z_2, ..., z_k \right \rangle [/math] — их НОП.

1) Если [math] x_m = y_n [/math], то [math] z_k = x_m = y_n [/math] и [math] Z_{k - 1} [/math] — НОП [math] X_{m - 1} [/math] и [math] Y_{n - 1} [/math]

2) Если [math] x_m \neq y_n [/math], то из [math] z_k \neq x_m [/math] следует, что [math] Z [/math] — НОП [math] X_{m - 1} [/math] и [math] Y [/math]

3) Если [math] x_m \neq y_n [/math], то из [math] z_k \neq y_n [/math] следует, что [math] Z [/math] — НОП [math] X [/math] и [math] Y_{n - 1} [/math]
Доказательство:
[math]\triangleright[/math]

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

2) Если [math] z_k \neq x_m [/math], то [math] Z [/math] — общая подпоследовательность [math] X_{m - 1} [/math] и [math] Y [/math]. Пусть существует их общая подпоследовательность [math] W [/math], длина которой превышает [math] k [/math]. Она также является общей подпоследовательностью [math] X [/math] и [math] Y [/math], что противоречит предположению о том, что [math] Z [/math] (длины [math] k [/math]) — НОП [math] X [/math] и [math] Y [/math]/

3) Аналогично второму случаю.
[math]\triangleleft[/math]

Решение

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

[math] 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} [/math]

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

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

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

Псевдокод

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

 // подсчёт таблиц
 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[i]
         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)

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

Заметим, что для вычисления [math] lcs[i][j] [/math] нужны только [math] i [/math]-ая и [math] (i-1) [/math]-ая строчки матрицы [math] lcs [/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
     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[i]
         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]

Также можно заметить, что от [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
     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