Самая длинная общая проблема подпоследовательности - Longest common subsequence problem

Не путать с самая длинная общая проблема с подстрокой.

Сравнение двух ревизий файла примера на основе их самой длинной общей подпоследовательности (черный)

В самая длинная общая подпоследовательность (LCS) проблема проблема поиска самого длинного подпоследовательность общий для всех последовательностей в наборе последовательностей (часто только двух последовательностях). Он отличается от самая длинная общая проблема с подстрокой: в отличие от подстрок, подпоследовательности не обязаны занимать последовательные позиции в исходных последовательностях. Самая длинная общая проблема подпоследовательности - классическая Информатика проблема, основа сравнение данных такие программы, как разница полезность, и имеет приложения в компьютерная лингвистика и биоинформатика. Он также широко используется системы контроля версий Такие как Git за примирение несколько изменений, внесенных в коллекцию файлов с контролируемой редакцией.

Например, рассмотрим последовательности (ABCD) и (ACBAD). У них есть 5 общих подпоследовательностей длины 2: (AB), (AC), (AD), (BD) и (CD); 2 общих подпоследовательности длины 3: (ABD) и (ACD); и больше не общие подпоследовательности. Итак, (ABD) и (ACD) - их самые длинные общие подпоследовательности.

Сложность

Для общего случая произвольного числа входных последовательностей проблема заключается в NP-жесткий.^[1] Когда количество последовательностей постоянно, задача решается за полиномиальное время с помощью динамическое программирование.

Данный ${\displaystyle N}$ последовательности длин ${\displaystyle n_{1},...,n_{N}}$, наивный поиск проверит каждый из ${\displaystyle 2^{n_{1}}}$ подпоследовательности первой последовательности, чтобы определить, являются ли они также подпоследовательностями остальных последовательностей; каждая подпоследовательность может быть протестирована во времени, линейном по длине оставшихся последовательностей, поэтому время для этого алгоритма будет

${\displaystyle O\left(2^{n_{1}}\sum _{i>1}n_{i}\right).}$

В случае двух последовательностей п и м элементов, время работы подхода динамического программирования составляет О (п × м).^[2] Для произвольного числа входных последовательностей подход динамического программирования дает решение в

${\displaystyle O\left(N\prod _{i=1}^{N}n_{i}\right).}$

Существуют методы меньшей сложности,^[3]которые часто зависят от длины LCS, размера алфавита или того и другого.

LCS не обязательно уникален; в худшем случае количество общих подпоследовательностей экспоненциально зависит от длины входных данных, поэтому алгоритмическая сложность должна быть как минимум экспоненциальной.^[4]

Решение для двух последовательностей

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

Префиксы

Префикс S_п из S определяется как первый п персонажи S.^[5] Например, префиксы S = (AGCA) являются

S₀ = ()

S₁ = (А)

S₂ = (AG)

S₃ = (АРУ)

S₄ = (AGCA).

Определите функцию LCS(Икс, Y) как самые длинные подпоследовательности, общие для Икс и Y. У этой функции есть два интересных свойства.

Первая недвижимость

Предположим, что обе последовательности заканчиваются одним и тем же элементом. Тогда их LCS - это LCS последовательности с исключением последнего элемента с добавленным общим последним элементом.

Например, LCS ((BANANA), (ATANA)) = LCS ((BANAN), (ATAN)) ^ (A), где ^ обозначает конкатенацию строк. Продолжая для остальных общих элементов, LCS ((BANANA), (ATANA)) = LCS ((BAN), (AT)) ^ (ANA).

В общем, для любых последовательностей Икс и Y длины п и м, если обозначить их элементы Икс₁ к Икс_п и у₁ к у_м и их префиксы Икс₁ к Икс_п-1 и Y₁ к Y_м-1, тогда:

Если: Икс_п=у_м

тогда: LCS(Икс_п, Y_м) = LCS( Икс_п-1, Y_м-1) ^ Икс_п. Обратите внимание, что LCS для Икс_п и Y_м включает определение LCS более коротких последовательностей, Икс_п-1 и Y_м-1.

Вторая собственность

Предположим, что две последовательности X и Y не заканчиваются одним и тем же символом. Тогда LCS X и Y длиннее LCS (X_п, Y_м-1) и LCS (X_п-1, Y_м).

Чтобы понять это свойство, рассмотрим две следующие последовательности:

последовательность X: (ABCDEFG) (n элементов)
последовательность Y: (BCDGK) (m элементов)

LCS этих двух последовательностей либо заканчивается G (последним элементом последовательности X), либо нет.

Случай 1: LCS заканчивается буквой G
Тогда он не может заканчиваться на K. Таким образом, не повредит удалить K из последовательности Y: если бы K был в LCS, это был бы его последний символ; как следствие, K отсутствует в LCS. Итак, LCS (X_п, Y_м) = LCS (X_п, Y_м-1).

Случай 2: LCS не заканчивается на G
Затем мы можем удалить G из последовательности X (по той же причине, что и выше). Итак, LCS (X_п, Y_м) = LCS (X_п-1, Y_м).

В любом случае LCS, который мы ищем, является одним из LCS (X_п, Y_м-1) или LCS (X_п-1, Y_м). Эти две последние LCS являются общими подпоследовательностями для X и Y. LCS (X, Y) - самая длинная. Таким образом, его значение - самая длинная последовательность LCS (X_п, Y_м-1) и LCS (X_п-1, Y_м).

LCS функция определена

Пусть две последовательности определены следующим образом: ${\displaystyle X=(x_{1}x_{2}\cdots x_{m})}$ и ${\displaystyle Y=(y_{1}y_{2}\cdots y_{n})}$. Префиксы ${\displaystyle X}$ находятся ${\displaystyle X_{1,2,\dots ,m}}$; префиксы ${\displaystyle Y}$ находятся ${\displaystyle Y_{1,2,\dots ,n}}$. Позволять ${\displaystyle {\mathit {LCS}}(X_{i},Y_{j})}$ представляют собой набор наиболее длинной общей подпоследовательности префиксов ${\displaystyle X_{i}}$ и ${\displaystyle Y_{j}}$. Этот набор последовательностей определяется следующим.

${\displaystyle {\mathit {LCS}}(X_{i},Y_{j})={\begin{cases}\emptyset &{\mbox{if }}i=0{\mbox{ or }}j=0\\{\mathit {LCS}}(X_{i-1},Y_{j-1}){\hat {}}x_{i}&{\mbox{if }}i,j>0{\mbox{ and }}x_{i}=y_{j}\\\operatorname {\max } \{{\mathit {LCS}}(X_{i},Y_{j-1}),{\mathit {LCS}}(X_{i-1},Y_{j})\}&{\mbox{if }}i,j>0{\mbox{ and }}x_{i}\neq y_{j}.\end{cases}}}$

Чтобы найти LCS ${\displaystyle X_{i}}$ и ${\displaystyle Y_{j}}$, сравнивать ${\displaystyle x_{i}}$ и ${\displaystyle y_{j}}$. Если они равны, то последовательность ${\displaystyle {\mathit {LCS}}(X_{i-1},Y_{j-1})}$ расширяется этим элементом, ${\displaystyle x_{i}}$. Если они не равны, то более длинная из двух последовательностей, ${\displaystyle {\mathit {LCS}}(X_{i},Y_{j-1})}$, и ${\displaystyle {\mathit {LCS}}(X_{i-1},Y_{j})}$, сохраняется. (Если они одинаковой длины, но не идентичны, то сохраняются оба.

Пример работы

Самая длинная подпоследовательность, общая для р = (GAC) и C = (AGCAT) будет найдено. Поскольку LCS функция использует "нулевой" элемент, удобно определить нулевые префиксы, которые пусты для этих последовательностей: р₀ = Ø; и C₀ = Ø. Все префиксы помещаются в таблицу с C в первом ряду (делая его cзаголовок столбца) и р в первом столбце (что делает его рзаголовок вл).

Струны LCS

	Ø	А	грамм	C	А	Т
Ø	Ø	Ø	Ø	Ø	Ø	Ø
грамм	Ø
А	Ø
C	Ø

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

LCS(р₁, C₁) определяется путем сравнения первых элементов в каждой последовательности. G и A не совпадают, поэтому эта LCS получает (используя «второе свойство») самую длинную из двух последовательностей, LCS(р₁, C₀) и LCS(р₀, C₁). Согласно таблице, оба они пусты, поэтому LCS(р₁, C₁) также пусто, как показано в таблице ниже. Стрелки указывают, что последовательность исходит из ячейки выше, LCS(р₀, C₁) и ячейку слева, LCS(р₁, C₀).

LCS(р₁, C₂) определяется путем сравнения G и G. Они совпадают, поэтому G добавляется к верхней левой последовательности, LCS(р₀, C₁), что есть (Ø), что дает (ØG), то есть (G).

За LCS(р₁, C₃), G и C не совпадают. Последовательность выше пуста; один слева содержит один элемент G. Выбрав самый длинный из них, LCS(р₁, C₃) является (G). Стрелка указывает влево, поскольку это самая длинная из двух последовательностей.

LCS(р₁, C₄), аналогично, есть (G).

LCS(р₁, C₅), также есть (G).

Ряд "G" завершен

	Ø	А	грамм	C	А	Т
Ø	Ø	Ø	Ø	Ø	Ø	Ø
грамм	Ø	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$Ø	${\displaystyle {\overset {\nwarrow }{\ }}}$(ГРАММ)	${\displaystyle {\overset {\ }{\leftarrow }}}$(ГРАММ)	${\displaystyle {\overset {\ }{\leftarrow }}}$(ГРАММ)	${\displaystyle {\overset {\ }{\leftarrow }}}$(ГРАММ)
А	Ø
C	Ø

За LCS(р₂, C₁), A сравнивается с A. Два элемента совпадают, поэтому A добавляется к Ø, давая (A).

За LCS(р₂, C₂), A и G не совпадают, поэтому самый длинный из LCS(р₁, C₂), которая есть (G), и LCS(р₂, C₁), то есть (A). В этом случае каждый из них содержит по одному элементу, поэтому данной LCS даны две подпоследовательности: (A) и (G).

За LCS(р₂, C₃), A не соответствует C. LCS(р₂, C₂) содержит последовательности (A) и (G); LCS (р₁, C₃) есть (G), который уже содержится в LCS(р₂, C₂). В результате LCS(р₂, C₃) также содержит две подпоследовательности (A) и (G).

За LCS(р₂, C₄), A соответствует A, которое добавляется в верхнюю левую ячейку, давая (GA).

За LCS(р₂, C₅), A не совпадает с T. Сравнивая две последовательности, (GA) и (G), самая длинная из них (GA), поэтому LCS(р₂, C₅) есть (GA).

Завершенные ряды "G" и "A"

	Ø	А	грамм	C	А	Т
Ø	Ø	Ø	Ø	Ø	Ø	Ø
грамм	Ø	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$Ø	${\displaystyle {\overset {\nwarrow }{\ }}}$(ГРАММ)	${\displaystyle {\overset {\ }{\leftarrow }}}$(ГРАММ)	${\displaystyle {\overset {\ }{\leftarrow }}}$(ГРАММ)	${\displaystyle {\overset {\ }{\leftarrow }}}$(ГРАММ)
А	Ø	${\displaystyle {\overset {\nwarrow }{\ }}}$(А)	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$(А) и (G)	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$(А) и (G)	${\displaystyle {\overset {\nwarrow }{\ }}}$(GA)	${\displaystyle {\overset {\ }{\leftarrow }}}$(GA)
C	Ø

За LCS(р₃, C₁), C и A не совпадают, поэтому LCS(р₃, C₁) получает самую длинную из двух последовательностей (A).

За LCS(р₃, C₂), C и G не совпадают. Обе LCS(р₃, C₁) и LCS(р₂, C₂) имеют один элемент. В результате LCS(р₃, C₂) содержит две подпоследовательности (A) и (G).

За LCS(р₃, C₃), C и C совпадают, поэтому C добавляется к LCS(р₂, C₂), который содержит две подпоследовательности (A) и (G), что дает (AC) и (GC).

За LCS(р₃, C₄), C и A не совпадают. Объединение LCS(р₃, C₃), который содержит (AC) и (GC), и LCS(р₂, C₄), который содержит (GA), дает всего три последовательности: (AC), (GC) и (GA).

Наконец, для LCS(р₃, C₅), C и T не совпадают. В результате LCS(р₃, C₅) также содержит три последовательности: (AC), (GC) и (GA).

Заполненная таблица LCS

	Ø	А	грамм	C	А	Т
Ø	Ø	Ø	Ø	Ø	Ø	Ø
грамм	Ø	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$Ø	${\displaystyle {\overset {\nwarrow }{\ }}}$(ГРАММ)	${\displaystyle {\overset {\ }{\leftarrow }}}$(ГРАММ)	${\displaystyle {\overset {\ }{\leftarrow }}}$(ГРАММ)	${\displaystyle {\overset {\ }{\leftarrow }}}$(ГРАММ)
А	Ø	${\displaystyle {\overset {\nwarrow }{\ }}}$(А)	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$(А) и (G)	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$(А) и (G)	${\displaystyle {\overset {\nwarrow }{\ }}}$(GA)	${\displaystyle {\overset {\ }{\leftarrow }}}$(GA)
C	Ø	${\displaystyle {\overset {\ \uparrow }{\ }}}$(А)	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$(А) и (G)	${\displaystyle {\overset {\nwarrow }{\ }}}$(AC) и (GC)	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$(AC) и (GC) и (GA)	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$(AC) и (GC) и (GA)

В конечном итоге последняя ячейка содержит все самые длинные подпоследовательности, общие для (AGCAT) и (GAC); это (AC), (GC) и (GA). В таблице также показаны самые длинные общие подпоследовательности для каждой возможной пары префиксов. Например, для (AGC) и (GA) самые длинные общие подпоследовательности - это (A) и (G).

Подход с отслеживанием

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

Сохранение длины, а не последовательностей

	Ø	А	грамм	C	А	Т
Ø	0	0	0	0	0	0
грамм	0	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$0	${\displaystyle {\overset {\nwarrow }{\ }}}$1	${\displaystyle {\overset {\ }{\leftarrow }}}$1	${\displaystyle {\overset {\ }{\leftarrow }}}$1	${\displaystyle {\overset {\ }{\leftarrow }}}$1
А	0	${\displaystyle {\overset {\nwarrow }{\ }}}$1	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$1	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$1	${\displaystyle {\overset {\nwarrow }{\ }}}$2	${\displaystyle {\overset {\ }{\leftarrow }}}$2
C	0	${\displaystyle {\overset {\ \uparrow }{\ }}}$1	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$1	${\displaystyle {\overset {\nwarrow }{\ }}}$2	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$2	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$2

Фактические подпоследовательности выводятся с помощью процедуры «трассировки», которая следует по стрелкам назад, начиная с последней ячейки в таблице. Когда длина уменьшается, последовательности должны иметь общий элемент. Если в ячейке показаны две стрелки, возможно несколько путей. Ниже приведена таблица для такого анализа с номерами, выделенными в ячейках, где длина собирается уменьшиться. Жирные числа обозначают последовательность (GA).^[6]

Пример трассировки

	Ø	А	грамм	C	А	Т
Ø	0	0	0	0	0	0
грамм	0	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$0	${\displaystyle {\overset {\nwarrow }{\ }}}$1	${\displaystyle {\overset {\ }{\leftarrow }}}$1	${\displaystyle {\overset {\ }{\leftarrow }}}$1	${\displaystyle {\overset {\ }{\leftarrow }}}$1
А	0	${\displaystyle {\overset {\nwarrow }{\ }}}$1	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$1	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$1	${\displaystyle {\overset {\nwarrow }{\ }}}$2	${\displaystyle {\overset {\ }{\leftarrow }}}$2
C	0	${\displaystyle {\overset {\ \uparrow }{\ }}}$1	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$1	${\displaystyle {\overset {\nwarrow }{\ }}}$2	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$2	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$2

Отношение к другим проблемам

Для двух струн ${\displaystyle X_{1\dots m}}$ и ${\displaystyle Y_{1\dots n}}$, длина кратчайшая общая суперпоследовательность связана с длиной LCS соотношением^[3]

${\displaystyle \left|SCS(X,Y)\right|=n+m-\left|LCS(X,Y)\right|.}$

В редактировать расстояние когда разрешены только вставка и удаление (без замены) или когда стоимость замены в два раза больше стоимости вставки или удаления, составляет:

${\displaystyle d'(X,Y)=n+m-2\cdot \left|LCS(X,Y)\right|.}$

Код для решения динамического программирования

Вычисление длины LCS

Функция ниже принимает в качестве входных последовательностей X [1..m] и Д [1..n], вычисляет LCS между X [1..i] и Y [1..j] для всех 1 ≤ я ≤ м и 1 ≤ j ≤ n, и хранит его в C [i, j]. C [m, n] будет содержать длину LCS Икс и Y.

функция LCSLength (X [1..m], Y [1..n]) C = массив (0..m, 0..n) за i: = 0..m C [i, 0] = 0 за j: = 0..n C [0, j] = 0 за i: = 1..m за j: = 1..n если X [i] = Y [j] // i-1 и j-1 при чтении X и Y с нуля C [i, j]: = C [i-1, j-1] + 1 еще                C [i, j]: = max (C [i, j-1], C [i-1, j]) возвращаться C [m, n]

В качестве альтернативы, мемоизация может быть использован.

Пример на C #

статический int[,] LcsLength(нить а, нить б){    int[,] C = новый int[а.Длина + 1, б.Длина + 1]; // (a, b). Длина + 1    за (int я = 0; я < а.Длина; я++)        C[я, 0] = 0;    за (int j = 0; j < б.Длина; j++)        C[0, j] = 0;    за (int я = 1; я <= а.Длина; я++)        за (int j = 1; j <= б.Длина; j++)        {            если (а[я - 1] == б[j - 1])// i-1, j-1                C[я, j] = C[я - 1, j - 1] + 1;            еще                C[я, j] = Математика.Максимум(C[я, j - 1], C[я - 1, j]);        }    возвращаться C;}

Чтение LCS

Следующая функция отступления выбор, сделанный при вычислении C стол. Если последние символы в префиксах равны, они должны быть в LCS. Если нет, проверьте, что дало наибольшую потерю LCS. ${\displaystyle x_{i}}$ и ${\displaystyle y_{j}}$, и сделайте тот же выбор. Просто выберите один, если они одинаковой длины. Вызов функции с помощью я = м и j = n.

функция возврат (C [0..m, 0..n], X [1..m], Y [1..n], i, j) если я = 0 или же j = 0 возвращаться ""    если  X [i] = Y [j] возвращаться backtrack (C, X, Y, i-1, j-1) + X [i] если C [i, j-1]> C [i-1, j] возвращаться возврат (C, X, Y, i, j-1) возвращаться возврат (C, X, Y, i-1, j)

Пример на C #

нить Возврат(int[,] C, char[] aStr, char[] bStr, int Икс, int у){    если (Икс == 0 | у == 0)        возвращаться "";    если (aStr[Икс - 1] == bStr[у - 1]) // х-1, у-1        возвращаться отступать(C, aStr, bStr, Икс - 1, у - 1) + aStr[Икс - 1]; // х-1    если (C[Икс, у - 1] > C[Икс - 1, у])        возвращаться отступать(C, aStr, bStr, Икс, у - 1);    возвращаться отступать(C, aStr, bStr, Икс - 1, у);}

Чтение всех LCS

При выборе ${\displaystyle x_{i}}$ и ${\displaystyle y_{j}}$ даст одинаково длинный результат, считайте обе полученные подпоследовательности. Это возвращается как набор этой функцией. Обратите внимание, что эта функция не является полиномиальной, так как она может ветвиться почти на каждом шаге, если строки похожи.

функция backtrackAll (C [0..m, 0..n], X [1..m], Y [1..n], i, j) если я = 0 или же j = 0 возвращаться {""}    если X [i] = Y [j] возвращаться {Z + X [я] для всех Z в backtrackAll (C, X, Y, i-1, j-1)} R: = {}    если C [i, j-1] ≥ C [i-1, j] R: = backtrackAll (C, X, Y, i, j-1) если C [i-1, j] ≥ C [i, j-1] R: = R ∪ backtrackAll (C, X, Y, i-1, j) возвращаться р

Распечатать разницу

Эта функция вернется через матрицу C и распечатает разница между двумя последовательностями. Обратите внимание, что вы получите другой ответ, если обменяете ≥ и <, с > и ≤ ниже.

функция printDiff (C [0..m, 0..n], X [1..m], Y [1..n], i, j) если я> = 0 и j> = 0 и X [i] = Y [j] printDiff (C, X, Y, i-1, j-1) print "" + X [i] иначе если j> 0 и (я = 0 или же C [i, j-1] ≥ C [i-1, j]) printDiff (C, X, Y, i, j-1) print "+" + Y [j] иначе если я> 0 и (j = 0 или же C [i, j-1] еще        Распечатать ""

Пример

Позволять ${\displaystyle X}$ быть "XMJYAUZ" и ${\displaystyle Y}$ быть "MZJAWXU». Самая длинная общая подпоследовательность между ${\displaystyle X}$ и ${\displaystyle Y}$ является "MJAU». Стол C показанный ниже, который генерируется функцией LCSLength, показывает длины самых длинных общих подпоследовательностей между префиксами ${\displaystyle X}$ и ${\displaystyle Y}$. В ${\displaystyle i}$й ряд и ${\displaystyle j}$-й столбец показывает длину LCS между ${\displaystyle X_{1..i}}$ и ${\displaystyle Y_{1..j}}$.

		0	1	2	3	4	5	6	7
		Ø	M	Z	J	А	W	Икс	U
0	Ø	0	0	0	0	0	0	0	0
1	Икс	0	0	0	0	0	0	1	1
2	M	0	1	1	1	1	1	1	1
3	J	0	1	1	2	2	2	2	2
4	Y	0	1	1	2	2	2	2	2
5	А	0	1	1	2	3	3	3	3
6	U	0	1	1	2	3	3	3	4
7	Z	0	1	2	2	3	3	3	4

В выделил числа показывают путь к функции отступать будет следовать из нижнего правого в верхний левый угол при чтении LCS. Если текущие символы в ${\displaystyle X}$ и ${\displaystyle Y}$ равны, они являются частью LCS, и мы идем как вверх, так и влево (показано на смелый). Если нет, мы идем вверх или влево, в зависимости от того, в какой ячейке номер больше. Это соответствует либо переходу LCS между ${\displaystyle X_{1..i-1}}$ и ${\displaystyle Y_{1..j}}$, или же ${\displaystyle X_{1..i}}$ и ${\displaystyle Y_{1..j-1}}$.

Оптимизация кода

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

Уменьшите набор проблем

Матрица C в наивном алгоритме растет квадратично с длинами последовательностей. Для двух последовательностей из 100 элементов потребуется матрица из 10 000 элементов и необходимо выполнить 10 000 сравнений. В большинстве реальных случаев, особенно при различиях в исходном коде и исправлениях, начало и конец файлов редко меняются, и почти наверняка не оба одновременно. Если в середине последовательности изменились только несколько элементов, можно удалить начало и конец. Это снижает не только требования к памяти для матрицы, но и количество сравнений, которые необходимо выполнить.

функция LCS (X [1..m], Y [1..n]) start: = 1 m_end: = m n_end: = n обрезать совпадающие элементы в начале    пока начало ≤ m_end и начало ≤ n_end и X [начало] = Y [начало] начало: = начало + 1 обрезать совпадающие элементы в конце    пока начало ≤ m_end и начало ≤ n_end и X [m_end] = Y [n_end] m_end: = m_end - 1 n_end: = n_end - 1 C = массив (start-1..m_end, start-1..n_end) только перебирать элементы, которые изменились    за i: = start..m_end за j: = start..n_end алгоритм продолжается как прежде ...

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

Сократите время сравнения

Большая часть времени, затрачиваемого наивным алгоритмом, тратится на сравнение элементов в последовательностях. Для текстовых последовательностей, таких как исходный код, вы хотите видеть строки как элементы последовательности, а не отдельные символы. Это может означать сравнение относительно длинных строк для каждого шага алгоритма. Можно сделать две оптимизации, которые помогут сократить время, затрачиваемое на эти сравнения.

Преобразовать строки в хэши

А хэш-функция или же контрольная сумма может использоваться для уменьшения размера строк в последовательностях. То есть для исходного кода, в котором средняя строка составляет 60 или более символов, хэш или контрольная сумма для этой строки может быть длиной от 8 до 40 символов. Кроме того, случайный характер хэшей и контрольных сумм будет гарантировать, что сравнения будут сокращаться быстрее, поскольку строки исходного кода редко будут изменены в начале.

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

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

Уменьшите необходимое пространство

Если требуется только длина LCS, матрица может быть уменьшена до ${\displaystyle 2\times \min(n,m)}$ матрицу с легкостью, или ${\displaystyle \min(m,n)+1}$ vector (умнее), так как подход динамического программирования требует только текущего и предыдущего столбцов матрицы. Алгоритм Хиршберга позволяет построить саму оптимальную последовательность за то же квадратичное время и линейные пространственные ограничения.^[7]

Дальнейшие оптимизированные алгоритмы

Существует несколько алгоритмов, которые работают быстрее, чем представленный подход динамического программирования. Один из них является Алгоритм Ханта – Шимански, который обычно выполняется ${\displaystyle O((n+r)\log(n))}$ время ${\displaystyle n>m}$), куда ${\displaystyle r}$ - количество совпадений между двумя последовательностями.^[8] Для задач с ограниченным размером алфавита Метод четырех русских может использоваться для уменьшения времени работы алгоритма динамического программирования на логарифмический коэффициент.^[9]

Поведение на случайных строках

Основная статья: Константы Хватала – Санкова.

Начиная с Хваталь и Санкофф (1975) Ошибка harvtxt: цель отсутствует: CITEREFChvátalSankoff1975 (помощь),^[10] ряд исследователей исследовали поведение самой длинной общей длины подпоследовательности, когда две заданные строки выбираются случайным образом из одного и того же алфавита. Когда размер алфавита постоянен, ожидаемая длина LCS пропорциональна длине двух строк, а константы пропорциональности (в зависимости от размера алфавита) известны как Константы Хватала – Санкова.. Их точные значения неизвестны, но верхняя и нижняя границы их значений доказаны,^[11] и известно, что они растут обратно пропорционально квадратному корню из размера алфавита.^[12] Было показано, что упрощенные математические модели самой длинной общей проблемы подпоследовательности контролируются Распределение Трейси – Уидома.^[13]

Смотрите также

• Самая длинная возрастающая подпоследовательность
• Самая длинная чередующаяся подпоследовательность
• Расстояние Левенштейна

Рекомендации

1. Дэвид Майер (1978). «Сложность некоторых задач о подпоследовательностях и суперпоследовательностях». J. ACM. ACM Press. 25 (2): 322–336. Дои:10.1145/322063.322075. S2CID  16120634.
2. Вагнер, Роберт; Фишер, Майкл (январь 1974). «Проблема исправления строки в строку». Журнал ACM. 21 (1): 168–173. CiteSeerX  10.1.1.367.5281. Дои:10.1145/321796.321811. S2CID  13381535. Получено 2018-05-03.
3. Л. Бергрот, Х. Хаконен и Т. Райта (2000). «Обзор самых длинных общих алгоритмов подпоследовательности». ШПИЛЬ. Компьютерное общество IEEE. 00: 39–48. Дои:10.1109 / SPIRE.2000.878178. ISBN  0-7695-0746-8. S2CID  10375334.
4. Рональд И. Гринберг (2003-08-06). «Границы числа наиболее длинных общих подпоследовательностей». arXiv:cs.DM/0301030.
5. Ся, Сюйхуа (2007). Биоинформатика и клетка: современные вычислительные подходы в геномике, протеомике и транскриптомике. Нью-Йорк: Спрингер. п.24. ISBN  978-0-387-71336-6.
6. Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест и Клиффорд Штайн (2001). "15.4". Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 350–355. ISBN  0-262-53196-8.
7. Хиршберг, Д.С. (1975). «Алгоритм линейного пространства для вычисления максимальных общих подпоследовательностей». Коммуникации ACM. 18 (6): 341–343. Дои:10.1145/360825.360861. S2CID  207694727.
8. Апостолико, Альберто; Галил, Цви (1997-05-29). Алгоритмы сопоставления с образцом. ISBN  9780195354348.
9. Масек, Уильям Дж .; Патерсон, Майкл С. (1980), «Более быстрый алгоритм вычисления расстояний редактирования строк», Журнал компьютерных и системных наук, 20 (1): 18–31, Дои:10.1016/0022-0000(80)90002-1, МИСТЕР  0566639.
10. Чватал, Вацлав; Санкофф, Дэвид (1975), «Самые длинные общие подпоследовательности двух случайных последовательностей», Журнал прикладной теории вероятностей, 12 (2): 306–315, Дои:10.2307/3212444, JSTOR  3212444, МИСТЕР  0405531.
11. Люкер, Джордж С. (2009), "Улучшенные оценки средней длины самых длинных общих подпоследовательностей", Журнал ACM, 56 (3), A17, Дои:10.1145/1516512.1516519, МИСТЕР  2536132, S2CID  7232681.
12. Киви, Маркос; Лёбль, Мартин; Матушек, Иржи (2005), «Ожидаемая длина самой длинной общей подпоследовательности для больших алфавитов», Успехи в математике, 197 (2): 480–498, arXiv:математика / 0308234, Дои:10.1016 / j.aim.2004.10.012, МИСТЕР  2173842.
13. Majumdar, Satya N .; Нечаев, Сергей (2005), "Точные асимптотические результаты для модели соответствия Бернулли выравнивания последовательностей", Физический обзор E, 72 (2): 020901, 4, arXiv:q-bio / 0410012, Bibcode:2005PhRvE..72b0901M, Дои:10.1103 / PhysRevE.72.020901, МИСТЕР  2177365, PMID  16196539, S2CID  11390762.

внешняя ссылка

• Словарь алгоритмов и структур данных: самая длинная общая подпоследовательность
• Коллекция реализаций самой длинной общей подпоследовательности во многих языках программирования.
• Найдите самую длинную общую подпоследовательность в Python