Учебники

DAA — самая длинная общая подпоследовательность

Июль 31, 2018

Самая длинная общая проблема подпоследовательности — найти самую длинную последовательность, которая существует в обеих заданных строках.

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

Рассмотрим последовательность S = <s 1 , s 2 , s 3 , s 4 ,…, s n >.

Последовательность Z = <z 1 , z 2 , z 3 , z 4 ,…, z m > над S называется подпоследовательностью S, если и только если она может быть получена из удаления S некоторых элементов.

Общая подпоследовательность

Предположим, что X и Y две последовательности над конечным множеством элементов. Можно сказать, что Z является общей подпоследовательностью X и Y , если Z является подпоследовательностью как X, так и Y.

Самая длинная общая подпоследовательность

Если задан набор последовательностей, самая длинная общая проблема подпоследовательности состоит в том, чтобы найти общую подпоследовательность всех последовательностей, которая имеет максимальную длину.

Самая длинная общая проблема подпоследовательности — это классическая проблема информатики, основа программ сравнения данных, таких как diff-утилита, и применяется в биоинформатике. Он также широко используется системами контроля версий, такими как SVN и Git, для согласования нескольких изменений, внесенных в коллекцию файлов с контролем версий.

Наивный метод

Пусть X — последовательность длины m, а Y — последовательность длины n . Проверьте для каждой подпоследовательности X , является ли она подпоследовательностью Y , и верните самую длинную общую найденную подпоследовательность.

Есть 2 m подпоследовательностей X. Проверка последовательности, является ли она подпоследовательностью Y, занимает O (n) времени. Таким образом, наивный алгоритм занял бы O (n2 m ) времени.

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

Пусть X = <x 1 , x 2 , x 3 ,…, x m > и Y = <y 1 , y 2 , y 3 ,…, y n > — последовательности. Для вычисления длины элемента используется следующий алгоритм.

В этой процедуре таблица C [m, n] вычисляется в главном порядке строк, а другая таблица B [m, n] вычисляется для построения оптимального решения. 

Algorithm: LCS-Length-Table-Formulation (X, Y)
m := length(X) 
n := length(Y) 
for i = 1 to m do 
   C[i, 0] := 0 
for j = 1 to n do 
   C[0, j] := 0 
for i = 1 to m do 
   for j = 1 to n do 
      if x i = y j 
         C[i, j] := C[i - 1, j - 1] + 1 
         B[i, j] := ‘D’ 
      else 
         if C[i -1, j] ≥ C[i, j -1] 
            C[i, j] := C[i - 1, j] + 1 
            B[i, j] := ‘U’ 
         else 
         C[i, j] := C[i, j - 1]
         B[i, j] := ‘L’ 
return C and B


Algorithm: Print-LCS (B, X, i, j)
if i = 0 and j = 0 
   return  
if B[i, j] = ‘D’ 
   Print-LCS(B, X, i-1, j-1) 
   Print(x i ) 
else if B[i, j] = ‘U’ 
   Print-LCS(B, X, i-1, j) 
else 
   Print-LCS(B, X, i, j-1)

Этот алгоритм выведет самую длинную общую подпоследовательность X и Y.

Анализ

Чтобы заполнить таблицу, внешний цикл for повторяется m раз, а внутренний цикл for повторяется n раз. Следовательно, сложность алгоритма составляет O (m, n) , где m и n — длина двух строк.

пример

В этом примере у нас есть две строки X = BACDB и Y = BDCB, чтобы найти самую длинную общую подпоследовательность.

Следуя алгоритму LCS-Length-Table-Formulation (как указано выше), мы рассчитали таблицу C (показана слева) и таблицу B (показаны справа).

В таблице B вместо «D», «L» и «U» мы используем диагональную стрелку, стрелку влево и стрелку вверх соответственно. После генерации таблицы B LCS определяется функцией LCS-Print. Результат BCB.

43
Share: