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

Материал из Викиконспекты
Перейти к: навигация, поиск
(поменял разделы местами в алгоритме Хиршберга)
(не показано 30 промежуточных версий 6 участников)
Строка 1: Строка 1:
Задача нахождения '''наибольшей общей подпоследовательности''' (''longest common subsequence, LCS'') — это задача поиска последовательности, которая является самой длинной подпоследовательностью нескольких последовательностей (обычно двух).
 
 
== Определения ==
 
 
{{Определение
 
{{Определение
 
|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, \dots, z_k \right \rangle </tex> является '''подпоследовательностью''' (англ. ''subsequence'') последовательности <tex> X = \left \langle x_1, x_2, \dots, x_m \right \rangle </tex>, если существует строго возрастающая последовательность <tex> \left \langle i_1, i_2, \dots, i_k \right \rangle </tex> индексов <tex> X </tex> таких, что для всех <tex> j = 1, 2, \dots, 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>.
 +
}}
 +
{{Задача
 +
|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> 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>LCS</tex> гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.
 
 
== Наивная идея решения ==
 
Переберем все различные подпоследовательности обеих строк и сравним их. Тогда искомая НОП гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.
 
  
 
== Динамическое программирование ==
 
== Динамическое программирование ==
  
Данная задача решается с использованием принципа оптимальности на префиксе.
+
Для решения данной задачи используем [[Динамическое программирование#Принцип оптимальности на префиксе | Принцип оптимальности на префиксе]].
  
 
=== Доказательство оптимальности ===
 
=== Доказательство оптимальности ===
 
{{
 
{{
 
Теорема|statement=
 
Теорема|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 = \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> X_{m - 1} </tex> и <tex> Y_{n - 1} </tex>
+
# Если <tex> x_m = y_n </tex>, то <tex> z_k = x_m = y_n </tex> и <tex> Z_{k - 1} </tex> — <tex>LCS(X_{m - 1},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 x_m </tex> следует, что <tex> Z </tex> — <tex>LCS(X_{m - 1},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>
+
# Если <tex> x_m \neq y_n </tex>, то из <tex> z_k \neq y_n </tex> следует, что <tex> Z </tex> — <tex>LCS(X,Y_{n - 1})</tex>
  
 
|proof=
 
|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 = 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(X,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> 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(X,Y)</tex>.
 
# Аналогично второму случаю.
 
# Аналогично второму случаю.
 
}}
 
}}
  
 
=== Решение ===
 
=== Решение ===
Обозначим как <tex> lcs[i][j] </tex> НОП префиксов данных последовательностей, заканчивающихся в элементах с номерами <tex> i </tex> и <tex> j </tex> соответственно. Получается следующее рекуррентное соотношение:
+
Обозначим как <tex> lcs[i][j] </tex>  <tex>LCS</tex> префиксов данных последовательностей, заканчивающихся в элементах с номерами <tex> i </tex> и <tex> j </tex> соответственно. Получается следующее рекуррентное соотношение:
  
 
<tex>
 
<tex>
Строка 44: Строка 42:
 
  0, & i = 0\text{ or }j = 0 \\
 
  0, & i = 0\text{ or }j = 0 \\
 
  lcs[i - 1][j - 1] + 1, & x[i] = y[j] \\
 
  lcs[i - 1][j - 1] + 1, & x[i] = y[j] \\
  max(lcs[i][j - 1], lcs[i - 1][j]), & x[i] \neq y[j]
+
  \max(lcs[i][j - 1],\ lcs[i - 1][j]), & x[i] \neq y[j]
 
\end{cases}
 
\end{cases}
 
</tex>
 
</tex>
Строка 51: Строка 49:
  
 
=== Построение подпоследовательности ===
 
=== Построение подпоследовательности ===
Для каждой пары элементов помимо длины НОП соответствующих префиксов хранятся и номера последних элементов, участвующих в этой НОП.Таким образом, посчитав ответ, можно восстановить всю наибольшую общую подпоследовательность.
+
Для каждой пары элементов помимо длины <tex>LCS</tex> соответствующих префиксов хранятся и номера последних элементов, участвующих в этой <tex>LCS</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>.
+
<tex> x </tex>, <tex> y </tex> — данные последовательности; <tex> lcs[i][j] </tex> — <tex>LCS</tex> для префикса длины <tex> i </tex> последовательности <tex> x </tex> и префикса длины <tex> j </tex> последовательности <tex> y </tex>; <tex> prev[i][j] </tex> — пара индексов элемента таблицы, соответствующего оптимальному решению вспомогательной задачи, выбранной при вычислении <tex> lcs[i][j] </tex>.
  
  // подсчёт таблиц
+
  ''<font color="green">// подсчёт таблиц</font>''
  LCS(x, y)
+
'''int''' LCS(x: '''int''', y: '''int'''):
 
     m = length(x)
 
     m = length(x)
 
     n = length(y)
 
     n = length(y)
     for i = 1 to m
+
     '''for''' i = 1 '''to''' m
 
       lcs[i][0] = 0
 
       lcs[i][0] = 0
     for j = 0 to n
+
     '''for''' j = 0 '''to''' n
 
       lcs[0][j] = 0
 
       lcs[0][j] = 0
     for i = 1 to m
+
     '''for''' i = 1 '''to''' m
       for j = 1 to n
+
       '''for''' j = 1 '''to''' n
         if x[i] == y[j]
+
         '''if''' x[i] == y[j]
 
           lcs[i][j] = lcs[i - 1][j - 1] + 1
 
           lcs[i][j] = lcs[i - 1][j - 1] + 1
 
           prev[i][j] = pair(i - 1, j - 1)
 
           prev[i][j] = pair(i - 1, j - 1)
         else
+
         '''else'''
           if a[i - 1][j] >= a[i][j - 1]
+
           '''if''' lcs[i - 1][j] >= lcs[i][j - 1]
 
             lcs[i][j] = lcs[i - 1][j]
 
             lcs[i][j] = lcs[i - 1][j]
 
             prev[i][j] = pair(i - 1, j)
 
             prev[i][j] = pair(i - 1, j)
           else
+
           '''else'''
 
             lcs[i][j] = lcs[i][j - 1]
 
             lcs[i][j] = lcs[i][j - 1]
 
             prev[i][j] = pair(i, j - 1)
 
             prev[i][j] = pair(i, j - 1)
 
    
 
    
  // вывод НОП, вызывается как printLCS(prev, x, m, n)
+
  ''<font color="green">// вывод LCS, вызывается как printLCS(m, n)</font>''
   printLCS(prev, x, i, j)
+
   '''int''' printLCS(i: '''int''', j: '''int'''):
     if i == 0 or j == 0 // пришли к началу НОП
+
     '''if''' i == 0 '''or''' j == 0 ''<font color="green">// пришли к началу LCS</font>''
       return
+
       '''return'''
     if prev[i][j] == pair(i - 1, j - 1) // если пришли в lcs[i][j] из lcs[i - 1][j - 1], то x[i] == y[j], надо вывести этот элемент
+
     '''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)
+
       printLCS(i - 1, j - 1)
 
       print x[i]
 
       print x[i]
     else
+
     '''else'''
       if prev[i][j] == pair(i - 1, j)
+
       '''if''' prev[i][j] == pair(i - 1, j)
         printLCS(prev, x, i - 1, j)
+
         printLCS(i - 1, j)
       else
+
       '''else'''
         printLCS(prev, x, i, j - 1)
+
         printLCS(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> элементов таблицы:
 
Заметим, что для вычисления <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)
+
   '''int''' LCS2(x: '''int''', y: '''int'''):
     if length(x) < length(y) // в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y
+
     '''if''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>''
 
       swap(x, y)
 
       swap(x, y)
 
     m = length(x)
 
     m = length(x)
 
     n = length(y)
 
     n = length(y)
     for j = 0 to n
+
     '''for''' j = 0 '''to''' n
 
       lcs[0][j] = 0
 
       lcs[0][j] = 0
 
       lcs[1][j] = 0
 
       lcs[1][j] = 0
     for i = 1 to m
+
     '''for''' i = 1 '''to''' m
 
       lcs[1][0] = 0
 
       lcs[1][0] = 0
       for j = 1 to n
+
       '''for''' j = 1 '''to''' n
         lcs[0][j] = lcs[1][j] // элемент, который был в a[1][j], теперь в предыдущей строчке
+
         lcs[0][j] = lcs[1][j] ''<font color="green">// элемент, который был в a[1][j], теперь в предыдущей строчке</font>''
         if x[i] == y[i]
+
         '''if''' x[i] == y[j]
 
           lcs[1][j] = lcs[0][j - 1] + 1
 
           lcs[1][j] = lcs[0][j - 1] + 1
         else
+
         '''else'''
           if lcs[0][j] >= lcs[1][j - 1]
+
           '''if''' lcs[0][j] >= lcs[1][j - 1]
 
             lcs[1][j] = lcs[0][j]
 
             lcs[1][j] = lcs[0][j]
           else
+
           '''else'''
 
             lcs[1][j] = lcs[1][j - 1]
 
             lcs[1][j] = lcs[1][j - 1]
     // ответ — lcs[1][n]
+
     ''<font color="green">// ответ — lcs[1][n]</font>''
  
 
Также можно заметить, что от <tex> (i - 1) </tex>-ой строчки нужны только элементы с <tex> (j - 1) </tex>-го столбца. В этом случае можно использовать лишь <tex> min(m, n) </tex> элементов таблицы:
 
Также можно заметить, что от <tex> (i - 1) </tex>-ой строчки нужны только элементы с <tex> (j - 1) </tex>-го столбца. В этом случае можно использовать лишь <tex> min(m, n) </tex> элементов таблицы:
  
   LCS3(x, y)
+
   '''int''' LCS3(x: '''int''', y: '''int'''):
     if length(x) < length(y) // в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y
+
     '''if''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>''
 
       swap(x, y)
 
       swap(x, y)
 
     m = length(x)
 
     m = length(x)
 
     n = length(y)
 
     n = length(y)
     for j = 0 to n
+
     '''for''' j = 0 '''to''' n
 
       lcs[j] = 0
 
       lcs[j] = 0
     d = 0 // d — дополнительная переменная, в ней хранится lcs[i - 1][j - 1]
+
     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[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]
+
          ''// в lcs[0], lcs[1], …, lcs[j - 1] хранятся lcs[i][0], lcs[i][1], …, lcs[i][j - 1]</font>''
     for i = 1 to m
+
     '''for''' i = 1 '''to''' m
       for j = 1 to n
+
       '''for''' j = 1 '''to''' n
 
         tmp = lcs[j]
 
         tmp = lcs[j]
         if x[i] == y[i]
+
         '''if''' x[i] == y[j]
 
           lcs[j] = d + 1
 
           lcs[j] = d + 1
         else
+
         '''else'''
           if lcs[j] >= lcs[j - 1]
+
           '''if''' lcs[j] >= lcs[j - 1]
             lcs[j] = lcs[j] // в lcs[j] и так хранится lcs[i - 1][j]
+
             lcs[j] = lcs[j] ''<font color="green">// в lcs[j] и так хранится lcs[i - 1][j]</font>''
           else
+
           '''else'''
 
             lcs[j] = lcs[j - 1]
 
             lcs[j] = lcs[j - 1]
 
         d = tmp
 
         d = tmp
    // ответ — lcs[n]
+
    ''<font color="green">// ответ — lcs[n]</font>''
 +
 
 +
== Длина кратчайшей общей суперпоследовательности ==
 +
Для двух подпоследовательностей <tex>X_{m}</tex> и <tex>Y_{n}</tex> длина кратчайшей общей суперпоследовательности равна 
 +
<tex>
 +
|SCS(X,Y)| = n + m - |LCS(X,Y)|
 +
</tex>
 +
<ref>[http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Relation_to_other_problems Wikipedia {{---}} Longest common subsequence problem]</ref>
 +
 
 +
== Решение для случая k строк ==
 +
Найдем решение для 3 строк.
 +
{{Задача
 +
|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>Z = \left \langle z_1, z_2, \dots, z_k \right \rangle</tex>. Необходимо найти <tex>LCS(X,Y,Z)</tex>
 +
}}
 +
Наивное решение подсчёта <tex>LCS</tex> нескольких строк при помощи последовательного нахождения <tex>LCS</tex> двух строк и уменьшением набора строк на единицу, не срабатывает. Это доказывается следующим контрпримером.
 +
Даны три последовательности:
 +
 
 +
<tex>X = \left \langle A, B, C, D, E\right \rangle </tex>
 +
 
 +
<tex>Y = \left \langle D, E, A, B, C\right \rangle </tex>
 +
 
 +
<tex>Z = \left \langle D, E, F, G, H\right \rangle </tex>
 +
 
 +
Подсчитаем <tex>V = LCS(X,Y) = \left \langle A, B, C \right \rangle</tex>
 +
 
 +
<tex>LCS(Z,V) = \emptyset</tex>
 +
 
 +
Это неверно, так как <tex>LCS(X,Y,Z) = \left \langle D, E \right \rangle</tex>
 +
 
 +
{{Теорема
 +
|statement = Пусть имеются последовательности <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> V = \left \langle v_1, v_2, \dots, v_h \right \rangle</tex> — их <tex>LCS</tex>.
 +
# Если <tex>z_k = x_m = y_n</tex>, то <tex>z_k = x_m = y_n = v_h</tex> и <tex> V_{h - 1} </tex> — <tex>LCS(X_{m - 1},Y_{n - 1},Z_{k - 1})</tex>
 +
# Если <tex>z_k \neq x_m \neq y_n</tex>, то из <tex>z_k \neq v_h</tex> следует, что <tex>V</tex> — <tex>LCS(X_m,Y_n,Z_{k - 1})</tex>
 +
# Если <tex>z_k \neq x_m \neq y_n</tex>, то из <tex>y_n \neq v_h</tex> следует, что <tex>V</tex> — <tex>LCS(X_m,Y_{n - 1},Z_k)</tex>
 +
# Если <tex>z_k \neq x_m \neq y_n</tex>, то из <tex>x_m \neq v_h</tex> следует, что <tex>V</tex> — <tex>LCS(X_{m - 1},Y_n,Z_k)</tex>
 +
|proof = Доказательство аналогично доказательству для двух последовательностей.
 +
}}
 +
===Решение===
 +
Обозначим как <tex> lcs[i][j][l]  </tex>  наибольшую общую подпоследовательность префиксов данных последовательностей, заканчивающихся в элементах с номерами <tex> i </tex>, <tex> j </tex> и <tex> l </tex> соответственно. Получается следующее рекуррентное соотношение:
 +
 
 +
<tex>
 +
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}
 +
</tex>
 +
 
 +
Очевидно, что сложность алгоритма составит <tex> O(mnk) </tex>, где <tex> m </tex>, <tex> n </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(n + m) </tex> памяти.
 +
}}
 +
 
 +
=== Алгоритм ===
 +
 
 +
Не теряя общности, будем считать, что <tex> m \geqslant n </tex>. Тогда разобьем последовательность <tex> X </tex> на две равные части <tex dpi="200"> x_1 \left [0 \dots \frac {m} {2} \right ] </tex> и <tex dpi="200"> 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 + 1 \dots n \right ])) \right | = max</tex>. Запустим алгоритм рекурсивно для пар
 +
<tex>(x_1, y \left [0 \dots j \right ])</tex> и <tex>(x_2, y \left [j + 1 \dots n \right ])</tex>. Будем продолжать до тех пор, пока в <tex>X</tex> не останется ровно <tex>1</tex> элемент, тогда достаточно проверить, входит ли он текущую часть <tex>Y</tex>, если входит, то добавим этот символ в ответ, если нет — вернем пустую строку. Таким образом, в результате работы алгоритма соберем последовательность, которая будет являться искомой.
 +
 
 +
=== Псевдокод ===
 +
 
 +
В данном примере <tex> x, y </tex> — последовательности, <tex> ans </tex> вектор ответа. <tex> LCS </tex> — функция, возвращающая последнюю строку матрицы <tex> lcs </tex>, для определения ответа на всех префиксах. Важно отметить, что для ее вычисления необходимо и достаточно хранить лишь две соседние строки матрицы <tex> lcs </tex> в любой момент времени. Так как вопрос оптимальности используемой памяти является важным местом данного алгоритма, то передачу различных отрезков последовательностей стоит воспринимать, как скрытую передачу границ для хранящихся глобально данных.
 +
 
 +
'''void''' hirschberg(x: '''vector''', y: '''vector'''):
 +
    '''if''' y.size() <= 0
 +
      return 
 +
    '''if''' x.size() == 1
 +
      '''if''' y.contains(x[0])
 +
        ans.push(x[0]) ''<font color="green"> // сохранение очередного элемента lcs </font>''
 +
      return
 +
    mid = x.size() / 2
 +
    f[] = LCS(x[0 .. mid], y)
 +
    s[] = LCS(reverse(x[mid + 1 .. x.size()]), reverse(y))
 +
    ''<font color="green">// s[i] хранит lcs для второй половины x и суффикса y[i..y.size()] ''
 +
    ''// это позволяет использовать общий индекс в качестве точки разделения</font>''
 +
    max = s[0]
 +
    it_max = -1
 +
    '''for''' j = 0 '''to''' y.size()
 +
      '''if''' f[j] + s[j + 1] > max
 +
        max = f[j] + s[j + 1]
 +
        it_max = j
 +
    '''if''' f[y.size() - 1] > max
 +
      it_max = y.size() - 1
 +
    hirschberg(x[0 .. mid], y[0 .. it_max])
 +
    hirschberg(x[mid + 1 .. x.size()], y[it_max + 1 .. y.size()])
 +
 
 +
=== Доказательство корректности ===
 +
 
 +
Осталось понять, что алгоритм находит нужную подпоследовательность. Не теряя общности, будем считать, что <tex> lcs </tex> единственная, так как нам не важно какую из равных по длине подпоследовательностей выбирать. Тогда рассмотрим разделение на две части <tex>X</tex>,
 +
часть символов LCS (возможно нулевая) попадет в первую половину, оставшаяся — во вторую. Пусть <tex> x_i </tex> последний символ из LCS в первой половине, тогда наш алгоритм выберет соответствующий ему <tex> y_i </tex> в качестве точки разделения. То есть символы из <tex> y </tex>, которые связаны
 +
со второй половиной <tex> x </tex>, лежат правее <tex> y_i </tex>, в противном случае, либо <tex> y_i </tex> не состоит в паре с <tex> x_i </tex>, либо <tex> x_i </tex> не последний символ из <tex> lcs </tex> в первой половине. Заметим, что если первая половина не содержит <tex> lcs </tex>, то
 +
точки разбиения не будет, для симметричного случая со второй половиной точкой разбиения будет <tex> y_i </tex>, которая включается в первую половину. Таким образом, мы свели поиск исходной <tex> lcs </tex> к поиску двух независимых частей. Когда в <tex> X </tex> останется <tex>1</tex> символ, то возможны два варинта, либо он входит в <tex> lcs </tex>, либо нет, в чем мы убеждаемся линейным поиском, случай, когда последний <tex> x </tex> не входит в <tex> lcs </tex>, возникает из-за того, что на каком-то шаге, вся подпоследовательность оказалась в одной из половин <tex> X </tex>.
 +
 
 +
=== Асимптотика ===
 +
 
 +
Рассмотрим временные затраты алгоритма. Рекурсия представима в виде бинарного дерева высоты не более <tex> \log (m) </tex>, так как она основана на разделении первой последовательности на две равные части на каждом шаге алгоритма.
 +
Оценим время выполнения для произвольной глубины такого дерева и просуммируем результат по всем возможным значениям парметра. На глубине <tex> h </tex> находится <tex> 2^h </tex> вершин с частью последовательности <tex> x </tex> размера  <tex dpi = "200">\displaystyle\frac{m}{2^h} </tex>
 +
и частью <tex> y </tex> длины <tex> k_i </tex>, где сумма семейства <tex> k_i </tex> равна <tex> n </tex>. Таким образом, получаем:
 +
 
 +
* На глубине h: <tex dpi = "200">{\displaystyle \sum_{i = 0}^{2^h - 1} \limits\frac{m}{2^h} k_i = \frac{m}{2^h} \sum_{i = 0}^{2^h - 1} \limits k_i = \frac{mn}{2^h}}</tex>
 +
 
 +
* Сумммируем по глубинам: <tex dpi = "200">{\displaystyle \sum_{i = 0}^{\log m}\limits\frac{mn}{2^i} = mn \sum_{i = 0}^{\log m}\limits \frac{1}{2^i} < mn \sum_{i = 0}^{\infty}\limits \frac{1}{2^i} = 2mn} </tex>
 +
 
 +
* Итоговая асимптотика алгоритма: <tex> O(mn) </tex>
 +
 
 +
 
 +
Проанализируем затраты на память. Три глобальные последовательности (две исходные и одна для ответа), к которым мы обращаемся внутри алгоритма, требуют <tex> m + n + \min (m, n) </tex> памяти. Дополнительно на каждом шаге рекурсии вызываются <tex>2</tex> функции <tex> LCS </tex>, которые суммарно требуют <tex> 4k_i </tex>, где <tex> k_i </tex> — длина части <tex> y </tex> в текущий момент, так как для нахождения <tex> LCS </tex> достаточно двух строк матрицы <tex> lcs </tex>. Вспомогательные массивы удаляются перед рекурсивным вызовом, таким образом, общие затраты равны сумме размеров массивов на одной глубине рекурсии, то есть:
 +
 
 +
* На глубине h: <tex dpi = "200">{\displaystyle\sum_{i = 0}^{2^h - 1}\limits 4 k_i = 4 \sum_{i = 0}^{2^h - 1}\limits k_i = 4n} </tex>
 +
 
 +
* Итого: <tex dpi = "200">{n + m + \min(m, n) + 4n = O(n + m)}</tex>
 +
 
 +
 
 +
== См. также ==
 +
*[[Задача о наибольшей возрастающей подпоследовательности]]
 +
*[[Наибольшая общая возрастающая подпоследовательность]]
 +
*[[Задача о наибольшей общей палиндромной подпоследовательности]]
 +
 
 +
== Примечания ==
 +
<references />
  
 
== Список литературы ==
 
== Список литературы ==
Т. Кормен, Ч. Лейзерсон, Р. Риверст, К. Штайн, «Алгоритмы: построение и анализ», 2-е изд., стр 418—425
+
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
 +
* Hirschberg, D.S.: A linear space algorithm for computing maximal common subsequences. Commun. ACM 18, 341–343 (1975)
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Динамическое программирование]]
 
[[Категория:Динамическое программирование]]

Версия 19:57, 18 мая 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(n + m) [/math] памяти.


Алгоритм

Не теряя общности, будем считать, что [math] m \geqslant 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 + 1 \dots n \right ])) \right | = max[/math]. Запустим алгоритм рекурсивно для пар [math](x_1, y \left [0 \dots j \right ])[/math] и [math](x_2, y \left [j + 1 \dots n \right ])[/math]. Будем продолжать до тех пор, пока в [math]X[/math] не останется ровно [math]1[/math] элемент, тогда достаточно проверить, входит ли он текущую часть [math]Y[/math], если входит, то добавим этот символ в ответ, если нет — вернем пустую строку. Таким образом, в результате работы алгоритма соберем последовательность, которая будет являться искомой.

Псевдокод

В данном примере [math] x, y [/math] — последовательности, [math] ans [/math] — вектор ответа. [math] LCS [/math] — функция, возвращающая последнюю строку матрицы [math] lcs [/math], для определения ответа на всех префиксах. Важно отметить, что для ее вычисления необходимо и достаточно хранить лишь две соседние строки матрицы [math] lcs [/math] в любой момент времени. Так как вопрос оптимальности используемой памяти является важным местом данного алгоритма, то передачу различных отрезков последовательностей стоит воспринимать, как скрытую передачу границ для хранящихся глобально данных.

void hirschberg(x: vector, y: vector):
   if y.size() <= 0
     return  
   if x.size() == 1
     if y.contains(x[0]) 
       ans.push(x[0])  // сохранение очередного элемента lcs 
     return
   mid = x.size() / 2
   f[] = LCS(x[0 .. mid], y)
   s[] = LCS(reverse(x[mid + 1 .. x.size()]), reverse(y)) 
   // s[i] хранит lcs для второй половины x и суффикса y[i..y.size()] 
   // это позволяет использовать общий индекс в качестве точки разделения
   max = s[0] 
   it_max = -1
   for j = 0 to y.size()
     if f[j] + s[j + 1] > max 
        max = f[j] + s[j + 1]
        it_max = j
   if f[y.size() - 1] > max
     it_max = y.size() - 1
   hirschberg(x[0 .. mid], y[0 .. it_max])
   hirschberg(x[mid + 1 .. x.size()], y[it_max + 1 .. y.size()])

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

Осталось понять, что алгоритм находит нужную подпоследовательность. Не теряя общности, будем считать, что [math] lcs [/math] единственная, так как нам не важно какую из равных по длине подпоследовательностей выбирать. Тогда рассмотрим разделение на две части [math]X[/math], часть символов LCS (возможно нулевая) попадет в первую половину, оставшаяся — во вторую. Пусть [math] x_i [/math] последний символ из LCS в первой половине, тогда наш алгоритм выберет соответствующий ему [math] y_i [/math] в качестве точки разделения. То есть символы из [math] y [/math], которые связаны со второй половиной [math] x [/math], лежат правее [math] y_i [/math], в противном случае, либо [math] y_i [/math] не состоит в паре с [math] x_i [/math], либо [math] x_i [/math] не последний символ из [math] lcs [/math] в первой половине. Заметим, что если первая половина не содержит [math] lcs [/math], то точки разбиения не будет, для симметричного случая со второй половиной точкой разбиения будет [math] y_i [/math], которая включается в первую половину. Таким образом, мы свели поиск исходной [math] lcs [/math] к поиску двух независимых частей. Когда в [math] X [/math] останется [math]1[/math] символ, то возможны два варинта, либо он входит в [math] lcs [/math], либо нет, в чем мы убеждаемся линейным поиском, случай, когда последний [math] x [/math] не входит в [math] lcs [/math], возникает из-за того, что на каком-то шаге, вся подпоследовательность оказалась в одной из половин [math] X [/math].

Асимптотика

Рассмотрим временные затраты алгоритма. Рекурсия представима в виде бинарного дерева высоты не более [math] \log (m) [/math], так как она основана на разделении первой последовательности на две равные части на каждом шаге алгоритма. Оценим время выполнения для произвольной глубины такого дерева и просуммируем результат по всем возможным значениям парметра. На глубине [math] h [/math] находится [math] 2^h [/math] вершин с частью последовательности [math] x [/math] размера [math]\displaystyle\frac{m}{2^h} [/math] и частью [math] y [/math] длины [math] k_i [/math], где сумма семейства [math] k_i [/math] равна [math] n [/math]. Таким образом, получаем:

  • На глубине h: [math]{\displaystyle \sum_{i = 0}^{2^h - 1} \limits\frac{m}{2^h} k_i = \frac{m}{2^h} \sum_{i = 0}^{2^h - 1} \limits k_i = \frac{mn}{2^h}}[/math]
  • Сумммируем по глубинам: [math]{\displaystyle \sum_{i = 0}^{\log m}\limits\frac{mn}{2^i} = mn \sum_{i = 0}^{\log m}\limits \frac{1}{2^i} \lt mn \sum_{i = 0}^{\infty}\limits \frac{1}{2^i} = 2mn} [/math]
  • Итоговая асимптотика алгоритма: [math] O(mn) [/math]


Проанализируем затраты на память. Три глобальные последовательности (две исходные и одна для ответа), к которым мы обращаемся внутри алгоритма, требуют [math] m + n + \min (m, n) [/math] памяти. Дополнительно на каждом шаге рекурсии вызываются [math]2[/math] функции [math] LCS [/math], которые суммарно требуют [math] 4k_i [/math], где [math] k_i [/math] — длина части [math] y [/math] в текущий момент, так как для нахождения [math] LCS [/math] достаточно двух строк матрицы [math] lcs [/math]. Вспомогательные массивы удаляются перед рекурсивным вызовом, таким образом, общие затраты равны сумме размеров массивов на одной глубине рекурсии, то есть:

  • На глубине h: [math]{\displaystyle\sum_{i = 0}^{2^h - 1}\limits 4 k_i = 4 \sum_{i = 0}^{2^h - 1}\limits k_i = 4n} [/math]
  • Итого: [math]{n + m + \min(m, n) + 4n = O(n + m)}[/math]


См. также

Примечания

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

  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
  • Hirschberg, D.S.: A linear space algorithm for computing maximal common subsequences. Commun. ACM 18, 341–343 (1975)