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

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

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

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

Вторая последовательность

Рассчитать

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

 

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

 

Показать матрицу решения

Матрица решения

 

Числовая матрица решения

 

 Ссылка  Сохранить  Виджет

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

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