Задача о наименьшей суперпоследовательности

Определение:

Последовательность $Z = \left \langle z_1, z_2, \dots, z_k \right \rangle$ является суперпоследовательностью (англ. supersequence) последовательности $X = \left \langle x_1, x_2, \dots, x_n \right \rangle$, если $X$ — подпоследовательность $Z$ , то есть существует строго возрастающая последовательность $\left \langle i_1, i_2, \dots, i_n \right \rangle$ индексов $Z$ таких, что для всех $j = 1, 2, \dots, n$ выполняется соотношение $z_{i_j} = x_j$, при этом $k \geqslant n$.

Определение:

Последовательность $Z$ является общей суперпоследовательностью (англ. common supersequence) последовательностей $X$ и $Y$, если $Z$ является суперпоследовательностью как для $X$, так для и $Y$.

Задача:

Пусть имеются последовательности $X = \left \langle x_1, x_2, \dots, x_n \right \rangle$ и $Y = \left \langle y_1, y_2, \dots, y_m \right \rangle$. Необходимо найти $SCS(X,Y)$, где $SCS(X, Y)$ — длина наименьшей общей суперпоследовательности последовательностей $X$ и $Y$

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

Пусть даны две последовательности длин $n$ и $m$ соответственно. Заметим, что если приписать к одной из данных последовательностей другую, то полученная последовательность будет их суперпоследовательностью с длиной $n + m$. Запомним все элементы обеих последовательностей и из них построим все возможные последовательности. Тогда искомая $SCS$ гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длин исходных последовательностей.

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

Решение

Обозначим за $scs[i][j]$ длину наименьшей общей суперпоследовательности для префиксов данных последовательностей $x[1 \dots n]$ и $y[1 \dots m]$, заканчивающихся в элементах с номерами $i$ и $j$ соответственно. Будем считать ответ методом динамического программирования на префиксе. Наименьшая общая суперпоследовательность $x[1 \dots i]$ и $y[1 \dots j]$ должна содержать каждый символ обеих последовательностей, поэтому если $j = 0$, то $SCS$ это просто последовательность $x[1 \dots i]$. Аналогичен случай, когда $i = 0$. Если $i \gt 0$ и $j \gt 0$, то возможны два случая. Если $x[i] \neq y[j]$, то $SCS$ должна включать оба этих элемента. Значит нужно выбрать минимальный из ответов для префиксов, включающих один элемент и не включающих второй, а именно минимум из ответов для меньших подзадач: $scs[i - 1][j]$ и $scs[i][j - 1]$. Если же $x[i] = y[j]$, то $SCS$ для последовательностей $x[1 \dots i]$ и $y[1 \dots j]$ должна заканчиваться этим элементом, так как он общий для них. Поэтому в этом случае $scs[i][j] = scs[i - 1][j - 1] + 1$. Получается следующее рекуррентное соотношение:

$scs[i][j] = \begin{cases} i, & j = 0 \\ j, & i = 0 \\ 1 + scs[i - 1][j - 1], & x[i] = y[j] \\ 1 + min(scs[i][j - 1],\ scs[i - 1][j]), & x[i] \neq y[j] \end{cases}$

Cложность алгоритма составит $O(mn)$, где $m$ и $n$ — длины последовательностей.

Восстановление ответа

Для восстановления ответа заведем массив $prev[0 \dots n][0\dots m]$, где $prev[i][j]$ будет равняться:

$prev[i][j] = \begin{cases} 1, & x[i] = y[j] \\ 2, & x[i] \neq y[j], scs[i - 1][j] \gt scs[i][j - 1] \\ 3, & x[i] \neq y[j], scs[i - 1][j] \leqslant scs[i][j - 1] \\ \end{cases}$

По этим данным можно узнать, какой символ был добавлен в наименьшую общую суперпоследовательность.

Псевдокод

$x, y$ — данные последовательности; $scs[i][j]$ — $SCS$ для префикса длины $i$ последовательности $x$ и префикса длины $j$ последовательности $y$; $prev[i][j]$ — массив для восстановления ответа.

// Подсчет динамики 
fun SCS(x: int[], y: int[]):  
   n = x.size
   m = y.size
   
   // инициализация массивов динамики 
   scs = [][]
   pref = [][]
    
   // случай равенства одного из индексов 0 
   for i = 0 to n
     scs[i][0] = i
   for j = 0 to m
     scs[0][j] = j
   
   for i = 1 to n
     for j = 1 to m
       // случай равенства элементов 
       if x[i] == y[j]
         scs[i][j] = 1 + scs[i - 1][j - 1]
         prev[i][j] = 1
       
       // случай неравенства элементов 
       else
         if scs[i - 1][j] > scs[i][j - 1]
           scs[i][j] = 1 + scs[i][j - 1]
           prev[i][j] = 2
         else
           scs[i][j] = 1 + scs[i - 1][j]
           prev[i][j] = 3

// вывод SCS 
fun printSCS(n: int, m: int):
   i = n
   j = m
   ans = [] // массив ответа 
   
   while i > 0 and j > 0
     if prev[i][j] == 1
       ans.append(x[i])
       i -= 1
       j -= 1
     else
       if prev[i][j] == 2
         ans.append(y[j])
         j -= 1
       else
         ans.append(x[i])
         i -= 1
   
   // добавляем оставшиеся символы первой последовательности 
   while i > 0 
     ans.append(x[i])
     i -= 1
   // добавляем оставшиеся символы второй последовательности 
   while j > 0
     ans.append(y[j]) 
     j -= 1
   
   reverse(ans) // разворачиваем последовательность, так как шли с конца 
   return ans

Связь с наибольшей общей подпоследовательностью

Теорема:

$|LCS(X, Y)| + |SCS(X, Y)| = n + m$, где $|LCS(X, Y)|$ — длина наибольшей общей подпоследовательности, $|SCS(X, Y)|$ — длина наименьшей общей суперпоследовательности, $n$ и $m$ — длины последовательностей $X$ и $Y$ соответственно.

Доказательство:

$\triangleright$

Пусть $X = \left \langle x_1, x_2, \dots, x_n \right \rangle$, $Y = \left \langle y_1, y_2, \dots, x_m \right \rangle$. Обозначим за $S$ их $SCS$ и будем ее строить. Так как $S$ являетcя суперпоследовательностью $X$, то можно представить $S$ так: $S = \dots x_1 \dots x_2 \dots x_i \dots x_n \dots$ Мы должны на место некоторых пропусков поставить элементы $Y$, так чтобы суммарная длина $S$ была минимальна, и $S$ являлась суперпоследовательностью $Y$. Рассмотрим любую общую подпоследовательность $X$ и $Y$. Заметим, что она уже находятся в $S$, а значит все её элементы не нужно добавлять. Поэтому мы добавим не меньше, чем $m - |LCS(X, Y)| элементов$. Длину $SCS(X, Y)$ нужно минимизировать, значит имеет место равенство: $|SCS(X,Y)| = n + (m - |LCS(X, Y)|)$. Поэтому: $|LCS(X, Y)| + |SCS(X, Y)| = n + m$

$\triangleleft$

См. также

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

Источники информации

• Википедия — Shortest common supersequence problem