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

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

В настоящей статье я хотел бы сделать обзор популярных алгоритмов для решения задачи нахождения максимальной общей подпоследовательности или 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” будет как подпоследовательностью, так и подстрокой.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение

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

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

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

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

Псевдокод

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

  // подсчёт таблиц
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)

���������� ����� ���������������������

����������:

������������ ������

���� ��� ������������������ �������� (������������ ��������).
���������� ����� ���������� ����� ��������������������� (longest common subsequence),
�� ���� �������� ��������� ���������� ��������� �� ���� �������������������,
����� ��� ����� ����������� � ����� ������������ �����.

������:

S1 = A B D E F F E K A B C D

S2 = G A B C E K E E A

���������� ����� ��������������������� ����

LCS(S1, S2) = A B E E A

���� �������

���� ������� ����������� � ���, ��� �� ���������� ���������
�������� ������� L, � ������� � ������ (i, j) ��������� �����
���������� ����� ������������������ ��� S1[1..i] � S2[1..j],
��� S1[1..i] — ������ i ��������� ������������������ S1,
S2[1..j] — ������ j ��������� ������������������ S2.
�� ����

L[i,j] = Length ( LCS (S1[1..i], S2[1..j]) )

����� ��������� ������ ������� � ������ ������� ���� �������.
�����, �������� �� �������� ������ ���� (� � �������� ����� �������) � ���������
����������� ��������, ��������������� ��������� ��� �������.
����� � ������ ������ ���� — ����� ������� ������������������.

����� ����� �� ����������� ������� ����� ������������ ���� ��
���������� ����� ����������������������.

��� �� ��

#include <stdio.h>
#define N 1000
#define max(a,b) ((a>b) ? a : b)
int L[N][N];

int main()
{
    char a[N];
    char b[N];
    int i, j, n, m;
    int yes = 0;
    
    scanf("%s", a);
    scanf("%s", b);
    n = strlen(a);
    m = strlen(b);

    for( j = 0; j < m ; j++ )
    {
       if( b[j] == a[0] ) yes = 1;
       L[0][j] = yes;
    }
    yes = 0;
    for(i = 0; i < n; i++)
    {
       if( a[i] == b[0] ) yes = 1;
       L[i][0] = yes;
    }
    
    for(i = 1; i < n; i++)
    {
       for(j = 1; j < m ; j++)
       {
   
          if( a[i] == b[j] )
             L[i][j] = L[i-1][j-1] + 1;
          else 
             L[i][j] = max( L[i-1][j], L[i][j-1] );
       }
    }
    
    printf( "%dn",  L[n-1][m-1] );
    return 0;
}

������ ��� ���������������� �������

• ��� �� ������� L ������������ ������������ ����� ��������������������� (���� �� ������������)?
• �������� ���������, ������� ���������� ����� ��������� ���������� ����� ����������������������.
• �������� ����������� �������� � �������������, ��� �������� �������������������
  � ������� ������������ �� ����������� (��� ������ �� ������������������� � �����������).
• �������� ���������, ��� ����� ����� ����� ������� ���������������������.
  ����� ������� ��������������������� ����� �� ������ ������� �����, �� ��� � ����� ������ �������� ��������������������� �� �������. �� ���� ����� ��������������� ����� ����� �� ����� ��������������������� �, ��� ����� ����� Score(�) ����
  
  • Score(�) = Length(�) – w*(L1 – L2)
    • Length(�) — ����� ���������������������
    • w — �����������, ������������ �������� ������
    • L1 � L2 — ����� ��������������� ��������, �� ������� ��������������������� ����� ������ � ������ ��������������������� � �����.

— ArtemVoroztsov – 23 Oct 2004

Подпоследовательность
получается из данной последовательности,
если удалить некоторые её элементы
(сама последовательность также считается
своей подпоследовательностью). Формально:
последовательность
Z=(z₁,z_2,…,z_n)
называется
подпоследовательностью
(subsequence)
последовательности Х=(x₁,x₂,…,x_n),
если существует строго возрастающая
последовательность из индексов
(i₁,i₂,…,i_k),
для которой z_j=x_i
при всех j=1,2,..,k.
Например,
Z=(В,
С, D,
В) является
подпоследовательностью последовательности
Х=(A,
В, С, В, D,
A,
В),
соответствующая последовательность
индексов ecть
(2,3,5,7).
(Отметим, что говоря о последовательностях,
мы-
в отличием
курсов математического анализа- имеем
в виду конечные последовательности).

Будем
говорить, что последовательность
Z
является
общей подпоследовательностыо
(common
subsequence)
последовательностей Х
и Y,
если
Z
является подпоследовательностью как
Х,
так и Y.
Пример: Х=(А,
В,
C, В, D,
A,
B),
Y
= (В,
D,C,
A,
В, A),
Z=
(В, С, A).
Последовательность
Z
в этом примере- не самая длинная из общих
подпоследовательностей Х
и Y
(последовательность (В,
С, В, А)
длиннее). Последовательность (В,
С, В, А) будет
наибольшей обшей подпоследовательностью
для X
и Y,
поскольку общих подпоследователыюстей
длины
5 у них нет.
Наибольших общих подпоследовательностей
может быть несколько. Например, (В,
D,
А, В)
— другая
наибольшая общая подпоследовательность
Х
и Y.

Задача
о наибольшей общей подпоследовательности
(сокращенно НОП; по-английски LCS
=
longest–common–subsequence)
состоит в том, чтобы найти общую
подпоследовательность наибольшей длины
для двух данных последовательностей Х
и Y.
В этом разделе мы покажем, как решить
эту задачу с помощью динамического
программирования.

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

Если
решать задачу о НОП «в лоб», перебирая
все подпоследовательности последовательности
Х
и проверяя для каждой из них, не будет
ли она подпоследовательностью
последовательности Y,
то алгоритм будет работать экспоненциальное
время, поскольку последовательность
длины т
имеет
2^m
подпоследовательностей (столько же,
сколько подмножеств у множества
{1,
2,.. ,m}).

Однако
задача о НОП обладает свойством
оптимальности для подзадач, как показывает
теорема
1 (см. ниже).
Подходящее множество подзадач-
множество
пар префиксов двух данных последовательностей.
Пусть Х=
(x₁,x₂,…,x_m)-
некоторая последовательность. Её
префикс
(prefix)
длины i–
это
последовательность Х_i
=(x₁,x₂,…,x_i)
(при i
от
0 до m).
Например, если Х
=(А, В,
С, В,
D,
А, В), то Х₄
= (А, В,
С, В), а X₀
– пустая
последовательность.

Теорема
1
(о строении НОП).
Пусть
Z=(z₁,z₂,…,z_k)
—
одна из
наибольших общих подпоследовательностей
для Х
=
(x₁,x₂,…,x_m)
и У
= (у1,y2,…,y_n).
Тогда:

1)
если x_т
⁼
y_n,
то z_k
= x_m
=y_n
и Z_k-1
является НОП для X_m-1
и Y_n-1

2)
если
x_m≠y_n
и z_k≠x_m
, то
Z является
НОП для Х_т-1
и
Y;

3)
если
x_m≠y_n
и z_k≠y_n
, то
Z является
НОП для Х_т
и Y_n-1

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

1.
Если z_k≠x_m,
то мы можем дописать x_т
= y_n
в конец
последовательности
Z
и получить общую подпоследовательность
длины k
+ 1,
что противоречит условию. Стало быть,
z_k
= x_m-1
= y_n.
Если у последовательностей X_m-1
и
Y_n-1
есть более длинная (чем Z_k-1)
общая подпоследовательность, то мы
можем дописать к ней x_m
=y_n
и получить
общую подпоследовательность для Х
и У, более длинную, чем Z,
чего быть не может.

2.
Коль скоро z_k≠x_m
последовательность
Z
является общей подпоследовательностью
для Х_m-1
и Y.
Так как Z—
НОП для Х и
Y,
то она тем более является НОП для Х_m-1
и Y.

3.
Аналогично
2.

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

Рекуррентная
формула

Теорема
16.1 показывает,
что нахождение НОП последовательностей
X=(x₁,x₂,…,x_m)
и Y=(y₁,y₂,…,y_n)
сводится к
решению либо одной, либо двух
подзадач.
Если x_m
= y_n
, то достаточно
найти НОП последовательностей X_m-1.
и
Y_n-1
и дописать к ней в конце x_m=y_n.
Если же
x_m≠y_n,
то надо решить две подзадачи: найти НОП
для X_m-1
и Y,
а затем найти НОП для Х
и Y_n-1.
Более длинная из них и будет служить
НОП для Х
и Y.

Теперь
сразу видно, что возникает перекрытие
подзадач. Действительно, чтобы найти
НОП Х
и Y,
нам может понадобиться найти НОП Х_m-1
и Y,
а
также НОП
Х
и
Y_n-1;
каждая из этих задач содержит подзадачу
нахождения НОП для Х_m-1
и Y_n-1.
Аналогичные перекрытия будут встречаться
и далее.

Как
и в задаче перемножения последовательности
матриц, мы начнём с рекуррентного
соотношения для стоимости оптимального
решения. Пусть c[i,j],
обозначает длину НОП для последовательностей
X_i
и Y_j.
Если i
или j
равны нулю, то одна из двух последовательностей
пуста, так что c[i,j]=
0. Сказанное
выше можно записать так:

(5)

Вычисление длины
НОП

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

float
x[t],y[r];

double
LCS_Length(float x[], float y[]);

{m=t;

n=r;

for
(i=1;i<=m;i++)

{c[i,0]=0};

for
(j=0;j<=n;j++)

{c[0,j]=0};

for
(i=1;i<=m;i++)

{for (j=1;j<=n;j++)

{if
(x[i]=y[j])

{c[i][j]=c[i-1][j-1]+1;

cout<<“b[i][j]=^”}

else
{if (c[i-1][j]>=c[i-1][j-1]+1;

cout<<“b[i][j]=^|”}

else
{c[i][j]=c[i][j-1];

cout<<“b[i][j]=<-“;}}}

return
c,b;

}

На
рис.3
показана работа lcs-length
для
X=(A,B,C,B,D,A,B)
и Y=
(B,D,C,A,B,A).
Алгоритм
lcs-length
требует
времени 0(mn):
на каждую клетку требуется
0(1)
шагов.

Рис.
3. Таблицы
c
и b,
созданные алгоритмом
lcs-length
при Х=(А,
В,С, B,
D,
А, В) и Y
=(В, D,
С, A,
В, A).
В клетке с координатами (i,j)
записаны число с[i,j]
и стрелка b[i,j].
Число
4 в правой
нижней клетке есть длина НОП. При i,j
> 0 значение
c[i,j]
определяется
тем, равны ли x_i
и у_j,
и вычисленными ранее значениями c[i-1,j],
c[i,j–
1] и
c[i–l,j–l].
Путь по стрелкам, ведущий из с[7,6],
заштрихован. Каждая косая стрелка на
этом пути соответствует элементу НОП
(эти элементы выделены).

Улучшение
алгоритма

После
того, как алгоритм разработан, нередко
удаётся сделать его более экономным. В
нашем примере можно обойтись без таблицы
b.
В самом деле каждое из чисел c[i,j]
зависит от c[i–1,j],
c[i,j-1]
и с[i-1,j-1].
Зная c[i,j]
мы можем за время
0(1)
выяснить, какая из этих трёх записей
использовалась. Тем самым можно найти
НОП за время 0(т+п)
с помощью
одной только таблицы с.
При этом мы экономим 0(mn)
памяти. (Впрочем, асимптотика не меняется:
объём таблицы c
есть также 0(mn).)

Если
нас интересует только длина наибольшей
общей подпоследовательности, то столько
памяти не нужно: вычисление c[i,j]
затрагивает только две строки с номерами
i
и i-1
(это не предел экономии: можно обойтись
памятью на одну строку таблицы с
плюс ещё чуть-чуть).
При этом, однако, саму подпоследовательность
найти (за время 0(m+n))
не удаётся.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #