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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (LCS3 дает WA если сравнивать x[i] и y[i], нужно сравнивать x[i] и y[j])
(Добавлена постановка задачи алгоритма Хиршберга и его описание)
Строка 187: Строка 187:
  
 
Аналогичным образом задача решается для <tex>k</tex> строк. Заполняется <tex>k</tex>-мерная динамика.
 
Аналогичным образом задача решается для <tex>k</tex> строк. Заполняется <tex>k</tex>-мерная динамика.
 +
 +
== Алгоритм Хиршберга ==
 +
 +
{{Задача
 +
|definition = Пусть имеются последовательности <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>LCS(X,Y)</tex> за время <tex> O(nm) </tex> и <tex> O(\min (n, m)) </tex> памяти.
 +
}}
 +
 +
=== Алгоритм ===
 +
 +
Не теряя общности, будем считать, что <tex> m \ge n </tex>. Тогда разобьем последовательность <tex> X </tex> на две равные части <tex> x^1 \left [0 \dots \frac {m} {2} \right ] </tex> и <tex> x^2  \left [\frac {m} {2} + 1 \dots m \right ] </tex>. Найдем <tex> LCS </tex> для  <tex> x^1 </tex> и всех префиксов
 +
последовательности <tex>Y</tex>, аналогично - для развернутых последовательностей <tex> x^2 </tex> и <tex> Y </tex>. Стоит отметить, что для нахождения <tex> LCS </tex> на всех префиксах достаточно одного квадратичного прохода, так как <tex>i</tex>-ый элемент последней строки результирующей матрицы есть не что иное, как <tex> LCS </tex> первой последовательности и префикса второй длины <tex>i</tex>. Затем выберем такой индекс <tex> j </tex>, что <tex> \left | LCS(x^1, y \left [0 \dots j \right ]) + LCS(reverse(x^2), reverse(y \left [j \dots n \right ])) \right | = max </tex> . Запустим алгоритм рекурсивно для пар
 +
<tex>(x^1, y \left [0 \dots j \right ])</tex> и <tex>(x^2, y \left [j \dots n \right ])</tex>. Будем продолжать до тех пор, пока в <tex>X</tex> не останется ровно 1 элемент, тогда достаточно проверить, входит ли он текущую часть <tex>Y</tex>, если входит, то вернем этот символ, если нет - вернем пустую строку.
 +
Таким образом ответом будет конкатенация всех вызовов функции.
  
 
== См. также ==  
 
== См. также ==  

Версия 21:00, 7 мая 2019

Определение:
Последовательность [math] Z = \left \langle z_1, z_2, \dots, z_k \right \rangle [/math] является подпоследовательностью (англ. subsequence) последовательности [math] X = \left \langle x_1, x_2, \dots, x_m \right \rangle [/math], если существует строго возрастающая последовательность [math] \left \langle i_1, i_2, \dots, i_k \right \rangle [/math] индексов [math] X [/math] таких, что для всех [math] j = 1, 2, \dots, 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, \dots, x_m \right \rangle [/math] и [math] Y = \left \langle y_1, y_2, \dots, y_n \right \rangle [/math]. Необходимо найти [math]LCS(X,Y)[/math]

Наивное решение

Переберем все различные подпоследовательности обеих строк и сравним их. Тогда искомая [math]LCS[/math] гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.

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

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

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

Теорема:
Пусть имеются последовательности [math] X = \left \langle x_1, x_2, \dots, x_m \right \rangle [/math] и [math] Y = \left \langle y_1, y_2, \dots, y_n \right \rangle [/math], а [math] Z = \left \langle z_1, z_2, \dots, z_k \right \rangle [/math] — их [math]LCS[/math].
  1. Если [math] x_m = y_n [/math], то [math] z_k = x_m = y_n [/math] и [math] Z_{k - 1} [/math] — [math]LCS(X_{m - 1},Y_{n - 1})[/math]
  2. Если [math] x_m \neq y_n [/math], то из [math] z_k \neq x_m [/math] следует, что [math] Z [/math] — [math]LCS(X_{m - 1},Y)[/math]
  3. Если [math] x_m \neq y_n [/math], то из [math] z_k \neq y_n [/math] следует, что [math] Z [/math] — [math]LCS(X,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]LCS[/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]LCS[/math]: тогда есть общая подпоследовательность [math] W [/math], длина которой больше [math] k - 1 [/math]. Добавив к [math] W [/math] элемент [math] x_m = y_n [/math], получим [math]LCS(X,Y)[/math], длина которой больше [math] k [/math] (т.е. больше длины [math] Z [/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]LCS(X,Y)[/math].
  3. Аналогично второму случаю.
[math]\triangleleft[/math]

Решение

Обозначим как [math] lcs[i][j] [/math] [math]LCS[/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]LCS[/math] соответствующих префиксов хранятся и номера последних элементов, участвующих в этой [math]LCS[/math].Таким образом, посчитав ответ, можно восстановить всю наибольшую общую подпоследовательность.

Псевдокод

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

  // подсчёт таблиц
int LCS(x: int, y: int):
   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 lcs[i - 1][j] >= lcs[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)
 
  // вывод LCS, вызывается как printLCS(m, n)
 int printLCS(i: int, j: int):
   if i == 0 or j == 0  // пришли к началу LCS
     return
   if prev[i][j] == pair(i - 1, j - 1)  // если пришли в lcs[i][j] из lcs[i - 1][j - 1], то x[i] == y[j], надо вывести этот элемент
     printLCS(i - 1, j - 1)
     print x[i]
   else
     if prev[i][j] == pair(i - 1, j)
       printLCS(i - 1, j)
     else
       printLCS(i, j - 1)

Оптимизация для вычисления только длины [math]LCS[/math]

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

 int LCS2(x: int, y: int):
   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]

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

 int LCS3(x: int, y: int):
   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[j]
         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]

Длина кратчайшей общей суперпоследовательности

Для двух подпоследовательностей [math]X_{m}[/math] и [math]Y_{n}[/math] длина кратчайшей общей суперпоследовательности равна [math] |SCS(X,Y)| = n + m - |LCS(X,Y)| [/math] [1]

Решение для случая k строк

Найдем решение для 3 строк.

Задача:
Пусть имеются последовательности [math] X = \left \langle x_1, x_2, \dots, x_m \right \rangle [/math], [math] Y = \left \langle y_1, y_2, \dots, y_n \right \rangle [/math] и [math]Z = \left \langle z_1, z_2, \dots, z_k \right \rangle[/math]. Необходимо найти [math]LCS(X,Y,Z)[/math]

Наивное решение подсчёта [math]LCS[/math] нескольких строк при помощи последовательного нахождения [math]LCS[/math] двух строк и уменьшением набора строк на единицу, не срабатывает. Это доказывается следующим контрпримером. Даны три последовательности:

[math]X = \left \langle A, B, C, D, E\right \rangle [/math]

[math]Y = \left \langle D, E, A, B, C\right \rangle [/math]

[math]Z = \left \langle D, E, F, G, H\right \rangle [/math]

Подсчитаем [math]V = LCS(X,Y) = \left \langle A, B, C \right \rangle[/math]

[math]LCS(Z,V) = \emptyset[/math]

Это неверно, так как [math]LCS(X,Y,Z) = \left \langle D, E \right \rangle[/math]

Теорема:
Пусть имеются последовательности [math] X = \left \langle x_1, x_2, \dots, x_m \right \rangle [/math], [math] Y = \left \langle y_1, y_2, \dots, y_n \right \rangle [/math] и [math] Z = \left \langle z_1, z_2, \dots, z_k \right \rangle [/math], а [math] V = \left \langle v_1, v_2, \dots, v_h \right \rangle[/math] — их [math]LCS[/math].
  1. Если [math]z_k = x_m = y_n[/math], то [math]z_k = x_m = y_n = v_h[/math] и [math] V_{h - 1} [/math] — [math]LCS(X_{m - 1},Y_{n - 1},Z_{k - 1})[/math]
  2. Если [math]z_k \neq x_m \neq y_n[/math], то из [math]z_k \neq v_h[/math] следует, что [math]V[/math] — [math]LCS(X_m,Y_n,Z_{k - 1})[/math]
  3. Если [math]z_k \neq x_m \neq y_n[/math], то из [math]y_n \neq v_h[/math] следует, что [math]V[/math] — [math]LCS(X_m,Y_{n - 1},Z_k)[/math]
  4. Если [math]z_k \neq x_m \neq y_n[/math], то из [math]x_m \neq v_h[/math] следует, что [math]V[/math] — [math]LCS(X_{m - 1},Y_n,Z_k)[/math]
Доказательство:
[math]\triangleright[/math]
Доказательство аналогично доказательству для двух последовательностей.
[math]\triangleleft[/math]

Решение

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

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

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

Аналогичным образом задача решается для [math]k[/math] строк. Заполняется [math]k[/math]-мерная динамика.

Алгоритм Хиршберга

Задача:
Пусть имеются последовательности [math] X = \left \langle x_1, x_2, \dots, x_m \right \rangle [/math] и [math] Y = \left \langle y_1, y_2, \dots, y_n \right \rangle [/math]. Необходимо найти [math]LCS(X,Y)[/math] за время [math] O(nm) [/math] и [math] O(\min (n, m)) [/math] памяти.


Алгоритм

Не теряя общности, будем считать, что [math] m \ge n [/math]. Тогда разобьем последовательность [math] X [/math] на две равные части [math] x^1 \left [0 \dots \frac {m} {2} \right ] [/math] и [math] x^2 \left [\frac {m} {2} + 1 \dots m \right ] [/math]. Найдем [math] LCS [/math] для [math] x^1 [/math] и всех префиксов последовательности [math]Y[/math], аналогично - для развернутых последовательностей [math] x^2 [/math] и [math] Y [/math]. Стоит отметить, что для нахождения [math] LCS [/math] на всех префиксах достаточно одного квадратичного прохода, так как [math]i[/math]-ый элемент последней строки результирующей матрицы есть не что иное, как [math] LCS [/math] первой последовательности и префикса второй длины [math]i[/math]. Затем выберем такой индекс [math] j [/math], что [math] \left | LCS(x^1, y \left [0 \dots j \right ]) + LCS(reverse(x^2), reverse(y \left [j \dots n \right ])) \right | = max [/math] . Запустим алгоритм рекурсивно для пар [math](x^1, y \left [0 \dots j \right ])[/math] и [math](x^2, y \left [j \dots n \right ])[/math]. Будем продолжать до тех пор, пока в [math]X[/math] не останется ровно 1 элемент, тогда достаточно проверить, входит ли он текущую часть [math]Y[/math], если входит, то вернем этот символ, если нет - вернем пустую строку. Таким образом ответом будет конкатенация всех вызовов функции.

См. также

Примечания

  1. ↑ Wikipedia — Longest common subsequence problem

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

  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Задача_о_наибольшей_общей_подпоследовательности&oldid=71162»