среда, 16 марта 2011 г.

Построение наибольшей общей подпоследовательности (LCS) на основе наибольшей возрастающей подпоследовательности (LIS)

[Все алгоритмы нахождения LCS]

Данный алгоритм относится к разряду “быстрых” алгоритмов, которые находят LCS двух строк. В среднем случае время работы O(n*log(h)), но в худшем случае все такие “быстрые” алгоритмы вырождаются в O(n*n*log(h)).

Перед тем, как продолжить настоятельно рекомендую ознакомится со статьей. Первоисточник это статьи здесь.

А теперь по пунктам остановимся на основных моментах.

1) Путь П – это набор из n не обязательно различных целых чисел.

2) Increasing subsequence (IS) of П (Возрастающая подпоследовательность последовательности П) – это набор чисел из П, которые строго увеличиваются при прохождении слева направо.
Пример: 
П = (5,3,4,4,9,6,2,1,8,7,10). 
IS = (3,4,6,8,10), (5,9,10) 

3) Longest increasing subsequence(LIS) of П (Наибольшая возрастающая подпоследовательность последовательности П) – это возрастающая подпоследовательность последовательности П, которая имеет максимальную длину.

4) Decreasing subsequence (DS) of П – невозрастающая подпоследовательность последовательности П при проходе слева направо.
Пример: DS = (5,4,4,2,1)

5) Cover(Покрытие) – множество непересекающихся DS последовательности П, которое содержит все элементы П. Размер покрытия равен количеству DS в покрытии. 
Пример: 
П = (5,3,4,9,6,2,1,8,7)
cover = (5,3,2,1), (4), (9,6), (8,7)

6) Smallest cover (SC) (Наименьшее покрытие) – это покрытие минимального размера

7) Лемма.
Если I – это IS последовательности П, длина которой равна размеру покрытия С последовательности П, тогда I – это LIS последовательности П, а C – SC.
Доказательство леммы смотрите в статье

8) Если П = (5,3,4,9,6,2,1,8,7,10), тогда
D1 = (5,3,2,1),
D2 = (4),
D3 = (9,6),
D4 = (8,7),
D5 = (10),
где D1..D5 – это DS последовательности П, образующие SC.

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

9) Лобовая реализация построения SC будет иметь сложность O(N*N). Такая ситуация может возникнуть, если исходная последовательность П является IS.

Сейчас рассмотрим алго со сложностью O(N*log(N)).
П = (5,3,4,9,6,2,1,8,7)

i

П[i]

Хвосты DS
(значение хвоста, номер DS)

DS

1 5 (5,1) D1=(5)
2 3 (3,1) D1=(5,3)
3 4 (3,1),(4,2) D1=(5,3)     D2=(4)
4 9 (3,1), (4,2), (9,3) D1=(5,3)     D2=(4) D3=(9)
5 6 (3,1), (4,2), (6,3) D1=(5,3)     D2=(4) D3=(9,6)
6 2 (2,1), (4,2), (6,3) D1=(5,3,2)   D2=(4) D3=(9,6)
7 1 (1,1), (4,2), (6,3) D1=(5,3,2,1) D2=(4) D3=(9,6)
8 8 (1,1), (4,2), (6,3), (8,4) D1=(5,3,2,1) D2=(4) D3=(9,6) D4=(8)
9 7 (1,1), (4,2), (6,3), (7,4) D1=(5,3,2,1) D2=(4) D3=(9,6) D4=(8,7)


Можно заметить что значения хвостов DS представляют собой IS, поэтому при добавлении нового элемента П[i] номер DS, к которому он относится можно не линейно а за O(log(N)), для этого можно использовать модификацию бинарного поиска(lower_bound)

10) Плавно переходим к исходной задаче.
Пусть S1 = “abacx” и S2 = “baabca”.
r(i) – количество вхождений символа S1[i] в строку S2
Тогда:
r(1) = 3, r(2) = 2, r(3) = 3, r(4) = 1, r(5) = 0.
11) Пусть list(x) – список позиций символа x из строки S1 в строке S2 в порядке убывания. Т.е.
list(a) = (6,3,2)
list(b) = (4,1)
list(c) = (5)
list(x) = (empty)

12) Пусть П(S1,S2) – последовательность, полученная путем конкатенации списков list(S1[i]), где i = 1..n.
Для рассматриваемого примера
П(S1, S2) = (6,3,2,4,1,6,3,2,5)

13) Для получения LCS(S1,S2) необходимо найти LIS(П(S1,S2)) из п.12. Элементы, попавшие в этот LIS соответствуют номерам элементов в S2, образующих LCS(S1, S2).

Пример:
LIS = (1,2,5), LCS = bac
LIS = (3,4,6), LCS = aba


Демонстрационное решение: здесь

вторник, 15 марта 2011 г.

Поиск наибольшей общей подпоследовательности(LCS) с помощью динамического программирования

[Все алгоритмы нахождения LCS]
Очень простой и понятный алгоритм, основанный на двумерном ДП.
Сложность по памяти и времени O(n*m).

Рассмотрим две строчки: A = “bedcadb” и B = “abcdede”. 
1) Буквы строчки A напишем перед строками матрицы, а элементы строчки B над столбцами матрицы.
2) Матрица будет иметь нулевые столбец и строку, состоящие из нулей.
3) Саму матрицу давайте назовем L.
4) В элементе матрицы L[i][j] будет хранится длина наибольшей общей подпоследовательности для префиксов A[1..i] и B[1..j].
Из п.4 делаем вывод, что нумерация букв в строках с единицы.
Префикс A[1..i] – это первые i символов строки A.

Для начала давайте заполним матрицу L по этим 4 принципам:

Разберем элемент L[3][4]. В данном случае рассматриваются два префикса: “bed” и “abcd”. Чисто интуитивно можно догадаться, что lcs для этих двух строк будет “bd”, поэтому в самом элементе храним 2. Все остальные элементы можно заполнить интуитивно.

Вот как раз на этом моменте выключаем интуицию(в рамках разумного) и начинаем искать “научный” принцип заполнения этой матрицы.

В ходе Ваших рассуждений должны появится следующие рекуррентные формулы:
             
           | L[i-1][j-1] + 1, если a[i] == b[j]
L[i][j] = < 
           | max(L[i-1][j],L[i][j-1]), иначе
Результирующая длина lcs для полных строк a и b находится в элементе L[7][7].

Теперь давайте научимся восстанавливать lcs по данной матрице. Эту задачу я поручаю на самостоятельное изучение. Если все таки эта задача вызовет затруднения, оставляю в качестве подсказки этот рисунок.

Оранжевая lcs: bed
Желтая    lcs: bcd
Затем тренируемся на задачах:
1) Найти длину LCS
2) По матрице восстановить саму LCS

Демонстрационное решение: здесь

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

Для упрощения длины обоих строк одинаковые.

* Алгоритм Нудельмана-Вунша – O(n*n)

* Реализация LCS на основе LIS(Наибольшая возрастающая подпоследовательность) – O(n*n*log(h), в среднем O(n*log(h))

* Алгоритм Эллисона-Дикса – O(n*n/32) 

обозначения:
n – длина строки,
h – количество общих буквенных пар. Т.е. если в первой строке есть 3, а во второй - 2 буквы ‘a’, то количество общих буквенных пар для ‘a’ равно 6.