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

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

Последовательность [math] Z = \left \langle z_1, z_2, \dots, z_k \right \rangle [/math] является суперпоследовательностью (англ. supersequence) последовательности [math] X = \left \langle x_1, x_2, \dots, x_n \right \rangle [/math], если существует строго возрастающая последовательность [math] \left \langle i_1, i_2, \dots, i_m \right \rangle [/math] индексов [math] Z [/math] таких, что для всех [math] j = 1, 2, \dots, m [/math] выполняется соотношение [math] z_{i_j} = x_j [/math].

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

Последовательность [math] Z [/math] является общей суперпоследовательностью (англ. common supersequence) последовательностей [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_n \right \rangle [/math] и [math] Y = \left \langle y_1, y_2, \dots, y_m \right \rangle [/math]. Необходимо найти [math]SCS(X,Y)[/math]

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

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

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

Решение

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

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

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

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

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

[math] 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] \leq scs[i][j - 1] \\ \end{cases} [/math]

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

Псевдокод

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

fun SCS(x: int, y: int):    // аналог void 
   n = x.size
   m = y.size
   for i = 1 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 - 1][j]
           prev[i][j] = 2
         else
           scs[i][j] = 1 + scs[i][j - 1]
           prev[i][j] = 3
 
fun printLCS(n: int, m: int): // вывод SCS
   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(x[i])
         i -= 1
       else
         ans.append(y[j])
         j -= 1
   while i > 0 // добавляем оставшиеся символы первой последовательности 
     ans.append(x[i])
     i -= 1
   while j > 0
     ans.append(y[j]) // добавляем оставшиеся символы второй последовательности 
     j -= 1
   reverse(ans) // разворачиваем последовательность, так как шли с конца 
   return ans

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

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

См. также

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

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

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