Как найти наибольшую общую последовательность

Нахождение максимальной общей подпоследовательности

В настоящей статье я хотел бы сделать обзор популярных алгоритмов для решения задачи нахождения максимальной общей подпоследовательности или LCS (longest common sequense). Так как акцент сделан на обучении, а не на реальном использовании, в качестве языка для реализации выбран Python, что позволит сократить количество кода и сконцентрироваться на основных идеях.

Определения

Последовательность представляет собой упорядоченный набор элементов. Строка — это частный случай последовательности, дальнейшие примеры будут для простоты рассматривать именно строки, но без изменений их можно использовать и для произвольного текста или чего-нибудь последовательного еще.
Пусть имеется последовательность x, состоящая из элементов x₁x₂…x_m и последовательность y, состоящая из элементов y₁y₂…y_n. z — подпоследовательность x в том случае, если существует строго возрастающий набор индексов элементов x, из которых получается z.
Общей подпоследовательностью для x и y считаем такую последовательность z, которая является одновременно подпоследовательностью x и подпоследовательностью y.
Максимальная общая подпоследовательность — это общая подпоследовательность с максимальной длинной. Далее по тексту будем использовать сокращение LCS.
В качестве примера, пусть x=HABRAHABR, y=HARBOUR, в этом случае LCS(x, y)=HARBR. Можно уже переходить непосредственно к алгоритму вычисления LCS, но, хорошо бы понять, для чего нам может это может понадобиться.

Применение на практике

Наиболее частое применение — использование в программах для сравнения файлов, например GNU diff. Имея найденную для двух текстов LCS, составить список элементарных изменений для превращения x в y или обратно задача тривиальная. В качестве бонуса, на основе длины общей подпоследовательности можно задать метрику для определения схожести двух последовательностей. Все, теперь точно можно переходить к делу.

Первый подход или народное творчество

Для начала пара наблюдений:

1. Если для последовательностей x и y нами уже вычислена LCS(x, y)=z, то, LCS для последовательностей полученных из x и y путем добавления одинакового элемента, будет состоять из z и этого добавленного элемента
2. Если мы добавим к последовательностям x и y по одному разному элементу, то для полученных таким образом xa и yb, LCS должна быть большая из двух: LCS(x,yb) или LCS(xa,y)

Этих наблюдений уже достаточно, чтобы реализовать рекурсию:

def LCS_RECURSIVE(x, y):
    if len(x) == 0 or len(y) == 0:
        return []
    if x[-1] == y[-1]:
        return LCS_RECURSIVE(x[:-1], y[:-1]) + [x[-1]]
    else:
        left = LCS_RECURSIVE(x[:-1], y)
        right = LCS_RECURSIVE(x, y[:-1])
        return left if len(left) > len(right) else right

Теперь можно подумать, что с этой реализацией не так. В наихудшем случае, когда между x и y нет одинаковых элементов LCS_RECURSIVE вызовется 2^{len(x)+len(y)} раз, при уровне рекурсии len(x)+len(y). Даже если закрыть глаза на производительность, код:

from uuid import uuid4
x = [uuid4().hex for _ in xrange(500)]
y = [uuid4().hex for _ in xrange(500)]
print LCS_RECURSIVE(x,y)

без дополнительного вызова sys.setrecursionlimit удачно не выполнится. Не самая удачная реализация.

Динамическое программирование или 64 кб хватит всем

Рассматриваемый алгоритм также известен как алгоритм Нидлмана—Вунша (Needleman-Wunsch).
Весь подход сводится к поэтапному заполнению матрицы, где строки представляют собой элементы x, а колонки элементы y. При заполнении действуют два правила, вытекающие из уже сделанных наблюдений:
1. Если элемент x_i равен y_j то в ячейке (i,j) записывается значение ячейки (i-1,j-1) с добавлением единицы
2. Если элемент x_i не равен y_j то в ячейку (i,j) записывается максимум из значений(i-1,j) и (i,j-1).
Заполнение происходит в двойном цикле по i и j с увеличением значений на единицу, таким образом на каждой итерации нужные на этом шаге значения ячеек уже вычислены:

def fill_dyn_matrix(x, y):
    L = [[0]*(len(y)+1) for _ in xrange(len(x)+1)]
    for x_i,x_elem in enumerate(x):
        for y_i,y_elem in enumerate(y):
            if x_elem == y_elem:
                L[x_i][y_i] = L[x_i-1][y_i-1] + 1
            else:
                L[x_i][y_i] = max((L[x_i][y_i-1],L[x_i-1][y_i]))
    return L

Иллюстрация происходящего:

Ячейки, в которых непосредственно происходило увеличение значения подсвечены. После заполнения матрицы, соединив эти ячейки, мы получим искомый LCS. Соединять при этом нужно двигаясь от максимальных индексов к минимальным, если ячейка подсвечена, то добавляем соответствующий элемент к LCS, если нет, то двигаемся вверх или влево в зависимости от того где находится большее значение в матрице:

def LCS_DYN(x, y):
    L = fill_dyn_matrix(x, y)
    LCS = []
    x_i,y_i = len(x)-1,len(y)-1
    while x_i >= 0 and y_i >= 0:
        if x[x_i] == y[y_i]:
            LCS.append(x[x_i])
            x_i, y_i = x_i-1, y_i-1
        elif L[x_i-1][y_i] > L[x_i][y_i-1]:
            x_i -= 1
        else:
            y_i -= 1
    LCS.reverse()
    return LCS

Сложность алогоритма — O(len(x)*len(y)), такая же оценка по памяти. Таким образом, если я захочу построчно сравнить два файла из 100000 строк, то нужно будет хранить в памяти матрицу из 10¹⁰ элементов. Т.е. реальное использование грозит получением MemoryError почти на ровном месте. Перед тем как перейти к следующему алгоритму заметим, что при заполнении матрицы L на каждой итерации по элементам x нам нужна только строка, полученная на предыщем ходу. Т.е. если бы задача ограничивалась только нахождением длины LCS без необходимости вычисления самой LCS, то можно было бы снизить использование памяти до O(len(y)), сохраняя одновременно только две строки матрицы L.

Борьба за место или Алгоритм Хишберга (Hirschberg)

Идея в основе этого алгоритма проста: если разделить входную последовательность x=x₁x₂…x_m на две произвольные части по любому граничному индексу i на xb=x₁x₂…x_i и xe=x_i+1x_i+2…x_m, то найдется способ аналогичного разбиения y (найдется такой индекс j, разбивающий y на yb=y₁y₂…y_j и ye=y_j+1y_j+2…y_n), такой, что LCS(x,y) = LCS(xb,yb) + LCS(xe,ye).
Для того, чтобы найти это разбиение y предлагается:

1. Заполнить динамическую матрицу L с помощью fill_dyn_matrix для xs и y. L1 приравняем последней строке вычисленной матрицы L
2. Заполнить матрицу L для *xe и *y (обратные последовательности для xe и y, в терминах Python: list(reversed(x)), list(reversed(y))). Приравняем *L2 последнюю строку вычисленной матрицы L, L2 это риверс от *L2
3. Принять j равным индексу, для которого сумма L1[j]+L2[j] максимальна

Это можно представить, как заполнение матрицы L с двух противоположных концов:

Заметим, что раз есть необходимость только в последней строке матрицы L, то при вычислении хранить всю матрицу не нужно. Немного изменив реализацию fill_dyn_matrix получим:

def lcs_length(x, y):
    curr = [0]*(1 + len(y))
    for x_elem in x:
        prev = curr[:]
        for y_i, y_elem in enumerate(y):
            if x_elem == y_elem:
                curr[y_i + 1] = prev[y_i] + 1
            else:
                curr[y_i + 1] = max(curr[y_i], prev[y_i + 1])
    return curr

Теперь непосредственно, о самом алгоритме. Он представляет собой классический divide and conquer: пока в последовательности x есть элементы, мы делим x пополам, находим подходящее разбиение для y и возвращаем сумму рекурсивных вызовов для пар последовательностей (xb,yb) и (xe,ye). Заметим, что в тривиальном случае, если x состоит из одного элемента и встречается в y мы просто возвращаем последовательность из этого единственного элемента x.

def LCS_HIRSHBERG(x, y):
    x_len = len(x)
    if x_len == 0:
        return []
    elif x_len == 1:
        if x[0] in y:
            return [x[0]]
        else:
            return []
    else:
        i = x_len // 2
        xb, xe = x[:i], x[i:]
        L1 = lcs_length(xb, y)
        L2 = reversed(lcs_length(xe[::-1], y[::-1]))
        SUM = (l1 + l2 for l1,l2 in itertools.izip(L1, L2))
        _, j = max((sum_val, sum_i) for sum_i, sum_val in enumerate(SUM))
        yb, ye = y[:j], y[j:]
        return LCS_HIRSHBERG(xb, yb) + LCS_HIRSHBERG(xe, ye)

Теперь требования по памяти у нас O(len(y)), время, необходимое для вычисления, удвоилось, но асимптотически по-прежнему O(len(x)len(y)).

Алгоритм Ханта-Шуманского (Hunt-Szymanski Algorithm)

Первое что нам потребуется это создание хэш таблицы matchlist, которая будет содержать индексы элементов второй последовательностей. Время необходимое для этого O(len(y)). Следующий код на питоне делает это:

y_matchlist = {}
for index, elem in enumerate(y):
    indexes = y_matchlist.setdefault(elem, [])
    indexes.append(index)
    y_matchlist[elem] = indexes

Для последовательности «HARBOUR» хэш будет следующим {‘A’: [1], ‘B’: [3], ‘H’: [0], ‘O’: [4], ‘R’: [2, 6], ‘U’: [5]}.

Далее, перебирая элементы последовательности x, заполняем массив THRESH соответсвующими индексами из заготовленного matchlist, таким образом, что значением k-го элемента THRESH должен быть индекс y_index, при условии что THRESH[k-1] < y_index и y_index < THRESH[k]. Таким образом, в любой момент времени массив THRESH отсортирован и для нахождения подходящего k мы можем использовать бинарный поиск. При обновлении элемента THRESH мы также добавляем соответствующий индексу y_index элемент последовательности к нашей LCS. Внести ясность может следующий код:

x_length, y_length = len(x), len(y)
min_length = min(x_length, y_length)
THRESH  = list(itertools.repeat(y_length,  min_length+1))
LINK_s1 = list(itertools.repeat(None,      min_length+1))
LINK_s2 = list(itertools.repeat(None,      min_length+1))
THRESH[0], t = -1, 0

for x_index,x_elem in enumerate(x):
   y_indexes = y_matchlist.get(x_elem, [])
   for y_index in reversed(y_indexes):               
       k_start = bisect.bisect_left(THRESH, y_index, 1, t)
       k_end   = bisect.bisect_right(THRESH, y_index, k_start, t)
       for k in xrange(k_start, k_end+2):
           if THRESH[k-1] < y_index and y_index < THRESH[k]:
               THRESH[k] = y_index
               LINK_x[k] = (x_index, LINK_x[k-1])
           if k > t:
               t = k

После этого нам остается только собрать из LINK_x саму последовательность.
Время работы этого алгоритма равно O((r + n) log n), где n — длина большей последовательности, а r — количество совпадений, в худшем случае при r = n*n, мы получаем время работы хуже чем в предыдущем варианте решения. Требования по памяти остаются порядка O(r+n).

Итого

Алгоритмов решающих данную проблему довольно много, асимптотически, самый эффективный алгоритм (Masek and Paterson) имеет оценку по времени O(n*n/log n). Учитывая общую небольшую эффективность при вычислениях LCS, на практике перед работой алгоритма выполняются простейшие подготовки, вроде отбрасывания одинаковых элементов в начале и в конце последовательностей и поиск тривиальных отличий между последовательностями. Также, существуют некоторые оптимизации с использованием битовых операций, не влияющие на асимптотику времени работы.
скачать весь код с примерами

Задача нахождения наибольшей общей подпоследовательности (англ. longest common subsequence, LCS) — задача поиска последовательности, которая является подпоследовательностью нескольких последовательностей (обычно двух). Часто задача определяется как поиск всех наибольших подпоследовательностей. Это классическая задача информатики, которая имеет приложения, в частности, в задаче сравнения текстовых файлов (утилита diff), а также в биоинформатике.

Подпоследовательность можно получить из некоторой конечной последовательности, если удалить из последней некоторое множество её элементов (возможно пустое). Например, BCDB является подпоследовательностью последовательности ABCDBAB. Будем говорить, что последовательность Z является общей подпоследовательностью последовательностей X и Y, если Z является подпоследовательностью как X, так и Y. Требуется для двух последовательностей X и Y найти общую подпоследовательность наибольшей длины. Заметим, что НОП может быть несколько.

Обратите внимание! Подпоследовательность отличается от подстроки. Например, если есть исходная последовательность “ABCDEF”, то “ACE” будет подпоследовательностью, но не подстрокой, а “ABC” будет как подпоследовательностью, так и подстрокой.

Решение задачи[править | править код]

Сравним два метода решения: полный перебор и динамическое программирование.

Полный перебор[править | править код]

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

Метод динамического программирования[править | править код]

		A	B	C	B
	0	0	0	0	0
D	0	← 0	← 0	← 0	← 0
C	0	← 0	← 0	↖ 1	← 1
B	0	← 0	↖ 1	← 1	↖ 2
A	0	↖ 1	← 1	← 1	↑ 2

Вначале найдём длину наибольшей подпоследовательности. Допустим, мы ищем решение для случая (n₁, n₂), где n₁, n₂ — длины первой и второй строк. Пусть уже существуют решения для всех подзадач (m₁, m₂), меньших заданной. Тогда задача (n₁, n₂) сводится к меньшим подзадачам следующим образом:

Теперь вернемся к задаче построения подпоследовательности. Для этого в существующий алгоритм добавим запоминание для каждой задачи той подзадачи, через которую она решается. Следующим действием, начиная с последнего элемента, поднимаемся к началу по направлениям, заданным первым алгоритмом, и записываем символы в каждой позиции. Это и будет ответом в данной задаче.

Время работы алгоритма будет .

См. также[править | править код]

• Алгоритмы на строках
• Наибольшая общая подстрока

Ссылки[править | править код]

• Нахождение наибольшей общей подпоследовательности. algolist.ru. Дата обращения: 15 августа 2013. Архивировано 24 августа 2013 года.

• Алгоритм поиска длины наибольшей общей подпоследовательности. coders.ask-ru.net.

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

Последовательность является подпоследовательностью (англ. subsequence) последовательности , если существует строго возрастающая последовательность индексов таких, что для всех выполняется соотношение .

Другими словами, подпоследовательность данной последовательности — это последовательность, из которой удалили ноль или больше элементов. Например, является подпоследовательностью последовательности , а соответствующая последовательность индексов имеет вид .

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

Последовательность является общей подпоследовательностью (англ. common subsequence) последовательностей и , если является подпоследовательностью как , так и .

Задача:

Пусть имеются последовательности и . Необходимо найти

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

Переберем все различные подпоследовательности обеих строк и сравним их. Тогда искомая гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.

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

Для решения данной задачи используем Принцип оптимальности на префиксе.

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

Теорема:

Пусть имеются последовательности и , а — их . Если , то и — Если , то из следует, что — Если , то из следует, что —

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

Если бы выполнялось , то к можно было бы добавить элемент , и тогда получилась бы общая подпоследовательность длины , что противоречит предположению, что — . Значит, выполняется . Значит, — общая подпоследовательность и . Докажем от противного, что — : тогда есть общая подпоследовательность , длина которой больше . Добавив к элемент , получим , длина которой больше (т.е. больше длины ), что приводит к противоречию. Если , то — общая подпоследовательность и . Пусть существует их общая подпоследовательность , длина которой превышает . Она также является общей подпоследовательностью и , что противоречит предположению о том, что (длины ) — . Аналогично второму случаю.

Решение

Обозначим как префиксов данных последовательностей, заканчивающихся в элементах с номерами и соответственно. Получается следующее рекуррентное соотношение:

Очевидно, что сложность алгоритма составит , где и — длины последовательностей.

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

Для каждой пары элементов помимо длины соответствующих префиксов хранятся и номера последних элементов, участвующих в этой .Таким образом, посчитав ответ, можно восстановить всю наибольшую общую подпоследовательность.

Псевдокод

, — данные последовательности; — для префикса длины последовательности и префикса длины последовательности ; — пара индексов элемента таблицы, соответствующего оптимальному решению вспомогательной задачи, выбранной при вычислении .

  // подсчёт таблиц
int LCS(x: vector, y: vector):
   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)

Оптимизация для вычисления только длины

Заметим, что для вычисления нужны только -ая и -ая строчки матрицы . Тогда можно использовать лишь элементов таблицы:

 int LCS2(x: vector, y: vector):
   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]

Также можно заметить, что от -ой строчки нужны только элементы с -го столбца. В этом случае можно использовать лишь элементов таблицы:

 int LCS3(x: vector, y: vector):
   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]

Длина кратчайшей общей суперпоследовательности

Для двух подпоследовательностей и длина кратчайшей общей суперпоследовательности равна

^[1]

Решение для случая k строк

Найдем решение для 3 строк.

Задача:

Пусть имеются последовательности , и . Необходимо найти

Наивное решение подсчёта нескольких строк при помощи последовательного нахождения двух строк и уменьшением набора строк на единицу, не срабатывает. Это доказывается следующим контрпримером.
Даны три последовательности:

Подсчитаем

Это неверно, так как

Теорема:

Пусть имеются последовательности , и , а — их . Если , то и — Если , то из следует, что — Если , то из следует, что — Если , то из следует, что —

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

Доказательство аналогично доказательству для двух последовательностей.

Решение

Обозначим как наибольшую общую подпоследовательность префиксов данных последовательностей, заканчивающихся в элементах с номерами , и соответственно. Получается следующее рекуррентное соотношение:

Очевидно, что сложность алгоритма составит , где , и — длины последовательностей.

Аналогичным образом задача решается для строк. Заполняется -мерная динамика.

Алгоритм Хиршберга

Задача:

Пусть имеются последовательности и . Необходимо найти за время и памяти.

Алгоритм

Не теряя общности, будем считать, что . Тогда разобьем последовательность на две равные части и . Найдем для и всех префиксов последовательности , аналогично — для развернутых последовательностей и . Стоит отметить, что для нахождения на всех префиксах достаточно одного квадратичного прохода, так как -ый элемент последней строки результирующей матрицы есть не что иное, как первой последовательности и префикса второй длины . Затем выберем такой индекс , что . Запустим алгоритм рекурсивно для пар
и . Будем продолжать до тех пор, пока в не останется ровно элемент, тогда достаточно проверить, входит ли он текущую часть , если входит, то добавим этот символ в ответ, если нет — вернем пустую строку. Таким образом, в результате работы алгоритма соберем последовательность, которая будет являться искомой.

Псевдокод

В данном примере — последовательности, — вектор ответа. — функция, возвращающая последнюю строку матрицы , для определения ответа на всех префиксах. Важно отметить, что для ее вычисления необходимо и достаточно хранить лишь две соседние строки матрицы в любой момент времени. Так как вопрос оптимальности используемой памяти является важным местом данного алгоритма, то передачу различных отрезков последовательностей стоит воспринимать, как скрытую передачу границ для хранящихся глобально данных.

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[y.size() - (j + 1)] > max 
        max = f[j] + s[y.size() - (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()])

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

Осталось понять, что алгоритм находит нужную подпоследовательность. Не теряя общности, будем считать, что единственная, так как нам не важно какую из равных по длине подпоследовательностей выбирать. Тогда рассмотрим разделение на две части ,
часть символов LCS (возможно нулевая) попадет в первую половину, оставшаяся — во вторую. Пусть последний символ из LCS в первой половине, тогда наш алгоритм выберет соответствующий ему в качестве точки разделения. То есть символы из , которые связаны
со второй половиной , лежат правее , в противном случае, либо не состоит в паре с , либо не последний символ из в первой половине. Заметим, что если первая половина не содержит , то
точки разбиения не будет, для симметричного случая со второй половиной точкой разбиения будет , которая включается в первую половину. Таким образом, мы свели поиск исходной к поиску двух независимых частей. Когда в останется символ, то возможны два варинта, либо он входит в , либо нет, в чем мы убеждаемся линейным поиском, случай, когда последний не входит в , возникает из-за того, что на каком-то шаге, вся подпоследовательность оказалась в одной из половин .

Асимптотика

Рассмотрим временные затраты алгоритма. Рекурсия представима в виде бинарного дерева высоты не более , так как она основана на разделении первой последовательности на две равные части на каждом шаге алгоритма.
Оценим время выполнения для произвольной глубины такого дерева и просуммируем результат по всем возможным значениям парметра. На глубине находится вершин с частью последовательности размера
и частью длины , где сумма семейства равна . Таким образом, получаем:

• На глубине h:

• Сумммируем по глубинам:

• Итоговая асимптотика алгоритма:

Проанализируем затраты на память. Три глобальные последовательности (две исходные и одна для ответа), к которым мы обращаемся внутри алгоритма, требуют памяти. Дополнительно на каждом шаге рекурсии вызываются функции , которые суммарно требуют , где — длина части в текущий момент, так как для нахождения достаточно двух строк матрицы . Вспомогательные массивы удаляются перед рекурсивным вызовом, таким образом, общие затраты равны сумме размеров массивов на одной глубине рекурсии, то есть:

• На глубине h:

• Итого:

См. также

• Задача о наибольшей возрастающей подпоследовательности
• Наибольшая общая возрастающая подпоследовательность
• Задача о наибольшей общей палиндромной подпоследовательности

Примечания

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

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 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)

Калькулятор ниже решает задачу нахождения наибольшей общей подпоследовательности. Задача решается методом динамического программирования, с использованием итерационного алгоритма, или алгоритма снизу-вверх. В результате заполняется матрица решений подзадач нахождения длин подпоследовательностей, который затем используется для формирования наибольшей общей подпоследовательности. Калькулятор выводит подпоследовательность, ее длину и матрицу решений. Подробнее о задаче и алгоритме ее решения можно почитать под калькулятором.

Наибольшая общая подпоследовательность

Подпоследовательность это последовательность, которую можно получить из исходной последовательности после удаления из нее некоторого множества элементов (в том числе пустое). Следует отличать подпоследовательность от подстроки. Например, если наша исходная последовательность ABCDEF, то ACE это подпоследовательность, полученная удалением элементов B, D, и F, а ABC – это подстрока (которая в том числе является и подпоследовательностью). В-общем, все подстроки являются подпоследовательностями, но не все подпоследовательности – подстроками.

Задача нахождения наибольшей общей подпоследовательности – это задача нахождения наибольшей подпоследовательности, содержащейся во всех последовательностях заданного множества. Часто наибольшую общую подпоследовательность ищут только в двух последовательностях, например, ищут наибольшую общую подпоследовательность между короткой строкой и длинной строкой. То есть по факту хотят узнать, появляются ли буквы короткой строки в том же порядке, но, возможно, на разном расстоянии, в длинной строке. Задача является классической задачей информатики, алгоритмы ее решения относятся к строковым алгоритмам, а практически она применяется для сравнения данных, например, в биоинформатике и вычислительной лингвистике.

Поиск наибольшей общей последовательности

Рассмотрим итерационный алгоритм поиска наибольшей общей последовательности между двумя строками. Получить такую последовательность проще всего сформировав матрицу решений задачи поиска длины общей подпоследовательности.

Алгоритм заполнения матрицы решений

Примечание: Будем считать что символы в строке нумеруются с индекса 0, как в большинстве языков программирования.

1. Сформируем пустую матрицу размером m+1 строк на n+1 столбцов, где m – длина первой строки, n – длина второй строки.
2. Обойдем все элементы данной матрицы, начиная с нижнего правого угла, перемещаясь сначала справа налево (индекс j), потом, по достижении индекса 0, снизу вверх (индекс i).
3. Для каждого элемента с индексом i,j вычислим его значение по следующему правилу
   • если текущий индекс строки i равен m или текущий индекс столбца j равен n, присвоим элементу значение 0
   • если символ с индексом i первой строки равен символу с индексом j второй строки, присвоим элементу значение 1 + значение элемента с индексом i+1, j+1 (значение элемента на одну позицию ниже и правее текущего)
   • если символы не равны, присвоим элементу максимальное из значений соседей справа и снизу.

Пройдя таким образом все элементы, в элементе с индексом 0,0 получим длину максимальной общей подпоследовательности. Используя полученную матрицу, можно сформировать саму подпоследовательность.

Алгоритм формирования наибольшей общей подпоследовательности по матрице решений

1. Начнем с элемента 0,0
2. Для текущего элемента проверим, равен ли символ с индексом i первой строки символу с индексом j второй строки
   • если они равны, добавим этот символ в подпоследовательность, увеличим оба индекса на 1, переставив текущий элемент сразу правее и ниже.
   • если они не равны, проверим соседей снизу и справа и переставим текущий элемент на максимальный из них, то есть сместимся правее или ниже
3. Остановимся по достижении конца любой строки.

Калькулятор выше позволяет вывести матрицу решений, чтобы можно было проследить работу алгоритма.

Остается только заметить, что вычислительная сложность такого алгоритма O(mn). Существуют более эффективные алгоритмы, скорость которых зависит от дополнительных условий, например, числа совпадений между последовательностями или мощности алфавита, используемого в последовательностях.