Самая длинная общая проблема подпоследовательности — найти самую длинную последовательность, которая существует в обеих заданных строках.
подпоследовательности
Рассмотрим последовательность 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.