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

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

Для лучшего понимания определим, как относится эти понятия друг к другу. Если брать в качестве последовательностей простейший вариант – строки, как набор символов, то задача становится более наглядной. Например, для строки “ABCDEF” подпоследовательностями (ПП) являются не только очевидные “ABCD”, “BC”, “DEF” и так далее, но также и “ACF”, “BCE”, то есть подпоследовательность должна содержать элементы в том же порядке, но не обязана быть непрерывным куском из последовательности. Так любая строка длины N (N>1) будет иметь 2^N (экспоненциальный рост) подпоследовательностей, в том числе N*(N+1) (квадратичный рост) непрерывных.

Например, строки “SEQUENCE” и “SUCCESS” имеют НОПП “SUCE” длиной 4.

Простейшее решение

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

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

Алгоритм с использованием рекурсии

Итак, имеются две последовательности A[0..na-1] и B[0..nb-1], соответственно, с длинами na и nb. Пусть D(A[0..na-1], B[0..nb-1]) будет длиной их НОПП.

Рассмотрим крайние элементы последовательностей. Например, если последний элемент в них одинаков, то его можно включать в найденную ПП, увеличив тем самым длину НОПП на 1. Затем исключаем этот элемент из рассмотрения, как уже найденный, и анализируем укороченные на этот элемент последовательности.

Пример: D(“ACD”, “ABD”) = 1 + D(“AC”, “AB”)
Т.е. если A[na-1] == B[nb-1], то D(A[0..na-1], B[0..nb-1]) = 1 + D(A[0..na-2], B[0..nb-2])

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

Пример: D(“AC”, “A”) = max( D(“A”,”A”), D(“AC”, “”).
Т.е. если A[na-1] != B[nb-1], то D(A[0..na-1], B[0..nb-1]) = max(D(A[0..na-2], B[0..nb-1]), D(A[0..na-1], B[0..nb-2]))

Учитывая, что длина нулевой последовательности также нулевая, то есть D(A[0..0], B[0..n]) = 0 и D(A[0..n], B[0..0]) = 0, можно составить программу нахождения длины НОПП.

Реализация рекурсивного алгоритма на Python:

# -*- coding: utf-8 -*-
# Простейшая реализация алгоритма поиска
# длины наибольшей общей подпоследовательности

def nopp(A, B, na, nb):
   if na == 0 or nb == 0:
      return 0;
   elif A[na-1] == B[nb-1]:
      return 1 + nopp(A, B, na-1, nb-1);
   else:
      return max(nopp(A, B, na, nb-1), nopp(A, B, na-1, nb));

# Тест
A = u"SEQUENCE"
B = u"SUCCESS"
print "NOPP('" + A + "','" + B + "')=" + str(nopp(A , B, len(A), len(B)))

Результат работы программы:
NOPP('SEQUENCE','SUCCESS')=4

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

Алгоритм с запоминанием

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

                       D("ABCD", "BDFG")
                      /                 \
        D("ABC", "BDFG")               D("ABCD", "BDF")
         /           \                   /          \
D("AB", "BDFG")  D("ABC", "BDF")  D("ABC", "BDF")  D("ABCD", "BD")

Видно, что вычисление D(“ABC”, “BDF”) происходит дважды, а, если раскрыть рекурсии глубже, то будет заметно, что повторных вычислений очень много. Чтобы избежать многократной обработки одних и тех же подстрок, нужно запоминать промежуточные результаты.

Реализация алгоритма с запоминанием на Python:

# -*- coding: utf-8 -*-
# Алгоритм поиска длины НОПП с запоминанием

def nopp(A , B):
   na = len(A)
   nb = len(B)

   # Массив для промежуточных вычислений
   # D[i][j] = D(A[0..i], B[0..j])
   D = [[None]*(nb+1) for i in xrange(na+1)]

   for i in range(na+1):
       for j in range(nb+1):
           if i == 0 or j == 0 :
               D[i][j] = 0
           elif A[i-1] == B[j-1]:
               D[i][j] = 1 + D[i-1][j-1]
           else:
               D[i][j] = max(D[i-1][j] , D[i][j-1])

   return D[na][nb]

# Тест
A = "SEQUENCE"
B = "SUCCESS"
print "NOPP('" + A + "','" + B + "')=" + str(nopp(A , B))

Сложность такого алгоритма оценивается как O(n^2). Существует также более быстрая реализация алгоритма поиска НОПП, O(n Log n), о чем мы расскажем в следующих статьях.

Читайте также: