Как найти подпоследовательность для последовательности

1. Подпоследовательность.

   Начать изучение
   

2. Существование частичного предела у ограниченной последовательности.

   Начать изучение
   

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

Пусть задана последовательность ({x_{n}}). Рассмотрим строго возрастающую последовательность ({n_k}) натуральных чисел, то есть такую, что
$$
n_{1} < n_{2} < ldots < n_{k} ldotsnonumber
$$

Тогда последовательность ({y_{k}}), где (y_{k}=x_{n_k}) при (kinmathbb{N}) называется подпоследовательностью последовательности ({x_n}) и обозначается ({x_{n_{k}}}). Например, последовательность нечетных натуральных чисел 1, 3, 5, 7, 9, …, взятых в порядке возрастания, является подпоследовательностью последовательности натуральных чисел 1, 2, 3, …, а последовательность 3, 5, 1, 9, 11, 7, … уже не является подпоследовательностью последовательности натуральных чисел.

Согласно определению подпоследовательность ({x_{n_{k}}}) образована из членов исходной последовательности ({x_{n}}), причем порядок следования членов в подпоследовательности такой же, как и в данной последовательности ({x_{n}}). В записи ({x_{n_k}}) число k означает порядковый номер члена последовательности (x_{n_{1}},x_{n_{2}},ldots) а (n_{k}) — номер этого члена в исходной последовательности. Поэтому (n_kgeq k), откуда следует, что (n_{k}rightarrowinfty) при (krightarrowinfty).

Введем теперь понятие частичного предела. Пусть ({x_{n_{k}}}) — подпоследовательность последовательности ({x_{n}}), и пусть существует конечный или бесконечный (displaystyle lim_{krightarrowinfty}x_{n_{k}}=a). Тогда a называют частичным пределом последовательности ({x_n}). Например, последовательность ({(-1)^{n}}) имеет два частичных предела, а именно -1 и 1. Последовательность ({1+(-1)^nn}) имеет два частичных предела, а именно 0 и (+infty).

Если ({x_{n}}) — ограниченная последовательность, a L — множество всех ее частичных пределов, то числа (sup L) и (inf L) называют соответственно верхним и нижним пределом этой последовательности и обозначают соответственно символами (displaystyle varlimsup_{nrightarrowinfty}x_{n}) и (displaystyle varliminf_{nrightarrowinfty}x_{n}).

Например, для последовательности 1, 2, 3, 1, 2, 3, 1, 2, 3, … имеем (displaystyle varlimsup_{nrightarrowinfty}x_{n}=3, varliminf_{nrightarrowinfty}x_{n}=1).

Существование частичного предела у ограниченной последовательности.

Задача нахождения наибольшей общей подпоследовательности (англ. 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.

From Wikipedia, the free encyclopedia

In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence is a subsequence of obtained after removal of elements and The relation of one sequence being the subsequence of another is a preorder.

Subsequences can contain consecutive elements which were not consecutive in the original sequence. A subsequence which consists of a consecutive run of elements from the original sequence, such as from is a substring. The substring is a refinement of the subsequence.

The list of all subsequences for the word “apple” would be “a“, “ap“, “al“, “ae“, “app“, “apl“, “ape“, “ale“, “appl“, “appe“, “aple“, “apple“, “p“, “pp“, “pl“, “pe“, “ppl“, “ppe“, “ple“, “pple“, “l“, “le“, “e“, “” (empty string).

Common subsequence[edit]

Given two sequences and a sequence is said to be a common subsequence of and if is a subsequence of both and For example, if

then is said to be a common subsequence of and

This would not be the longest common subsequence, since only has length 3, and the common subsequence has length 4. The longest common subsequence of and is

Applications[edit]

Subsequences have applications to computer science,^[1] especially in the discipline of bioinformatics, where computers are used to compare, analyze, and store DNA, RNA, and protein sequences.

Take two sequences of DNA containing 37 elements, say:

SEQ₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

SEQ₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

The longest common subsequence of sequences 1 and 2 is:

LCS_(SEQ1,SEQ2) = CGTTCGGCTATGCTTCTACTTATTCTA

This can be illustrated by highlighting the 27 elements of the longest common subsequence into the initial sequences:

SEQ₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

SEQ₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

Another way to show this is to align the two sequences, that is, to position elements of the longest common subsequence in a same column (indicated by the vertical bar) and to introduce a special character (here, a dash) for padding of arisen empty subsequences:

SEQ₁ = ACGGTGTCGTGCTAT-G–C-TGATGCTGA–CT-T-ATATG-CTA-

        | || ||| ||||| |  | |  | || |  || | || |  |||

SEQ₂ = -C-GT-TCG-GCTATCGTACGT–T-CT-ATTCTATGAT-T-TCTAA

Subsequences are used to determine how similar the two strands of DNA are, using the DNA bases: adenine, guanine, cytosine and thymine.

Theorems[edit]

See also[edit]

• Subsequential limit – The limit of some subsequence
• Limit superior and limit inferior – Bounds of a sequence
• Longest increasing subsequence problem – algorithm to find the longest increasing subsequence in an array of numbers

Notes[edit]

This article incorporates material from subsequence on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

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

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

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

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

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

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

Решение

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

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

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

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

Псевдокод

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

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