Самая длинная общая подпоследовательность

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

Например, рассмотрим последовательности (ABCD) и (ACBAD). У них есть пять общих подпоследовательностей длины 2: (AB), (AC), (AD), (BD) и (CD); две общие подпоследовательности длины 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).}$

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

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

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

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

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

Префикс S _n слова S определяется как первые n символов слова S. [ ^5] Например, префиксы слова S = (AGCA) следующие:

С ₀ = ()

С ₁ = (А)

С ₂ = (АГ)

С ₃ = (АГС)

С ₄ = (АГКА).

Пусть LCS ( X , Y ) — функция, которая вычисляет самую длинную подпоследовательность, общую для X и Y. Такая функция обладает двумя интересными свойствами.

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

Если A и B — различные символы ( A ≠ B ), то LCS (X^A,Y^B) — одна из строк максимальной длины в наборе { LCS ( X ^ A , Y ), LCS ( X , Y ^ B ) } для всех строк X , Y .

Например, LCS ("ABCDEFG","BCDGK") является самой длинной строкой среди LCS ("ABCDEFG","BCDG") и LCS ("ABCDEF","BCDGK"); если бы обе имели одинаковую длину, одну из них можно было бы выбрать произвольно.

Для реализации имущества различают два случая:

• Если LCS ("ABCDEFG","BCDGK") заканчивается на "G", то конечная "K" не может быть в LCS, следовательно, LCS ("ABCDEFG","BCDGK") = LCS ("ABCDEFG","BCDG").
• Если LCS ("ABCDEFG","BCDGK") не заканчивается на "G", то конечная "G" не может быть в LCS, следовательно, LCS ("ABCDEFG","BCDGK") = LCS ("ABCDEF","BCDGK").

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

${\displaystyle {\mathit {LCS}}(X_{i},Y_{j})={\begin{cases}\epsilon &{\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}}}$

Чтобы найти НКП и , сравните и . Если они равны, то последовательность расширяется на этот элемент, . Если они не равны, то сохраняется самая длинная из двух последовательностей, , и . (Если они имеют одинаковую длину, но не идентичны, то сохраняются обе.) Базовым случаем, когда либо или пусто, является пустая строка , .${\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})}$${\displaystyle X_{i}}$${\displaystyle Y_{i}}$${\displaystyle \epsilon }$

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

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

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

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

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

LCS ( R ₁ , C ₄ ) также является (G).

LCS ( R ₁ , C ₅ ) также является (G).

Строка "G" завершена

	ε	А	Г	С	А	Т
ε	ε	ε	ε	ε	ε	ε
Г	ε	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$ε	${\displaystyle {\overset {\nwarrow }{\ }}}$(Г)	${\displaystyle {\overset {\ }{\leftarrow }}}$(Г)	${\displaystyle {\overset {\ }{\leftarrow }}}$(Г)	${\displaystyle {\overset {\ }{\leftarrow }}}$(Г)
А	ε
С	ε

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

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

Для LCS ( R ₂ , C ₃ ) A не соответствует C. LCS ( R ₂ , C ₂ ) содержит последовательности (A) и (G); LCS( R ₁ , C ₃ ) — это (G), которая уже содержится в LCS ( R ₂ , C ₂ ). Результатом является то, что LCS ( R ₂ , C ₃ ) также содержит две подпоследовательности, (A) и (G).

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

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

Ряды «G» и «A» завершены

	ε	А	Г	С	А	Т
ε	ε	ε	ε	ε	ε	ε
Г	ε	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$ε	${\displaystyle {\overset {\nwarrow }{\ }}}$(Г)	${\displaystyle {\overset {\ }{\leftarrow }}}$(Г)	${\displaystyle {\overset {\ }{\leftarrow }}}$(Г)	${\displaystyle {\overset {\ }{\leftarrow }}}$(Г)
А	ε	${\displaystyle {\overset {\nwarrow }{\ }}}$(А)	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$(А) и (Г)	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$(А) и (Г)	${\displaystyle {\overset {\nwarrow }{\ }}}$(ГА)	${\displaystyle {\overset {\ }{\leftarrow }}}$(ГА)
С	ε

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

Для LCS ( R ₃ , C ₂ ), C и G не совпадают. Как LCS ( R ₃ , C ₁ ), так и LCS ( R ₂ , C ₂ ) имеют по одному элементу. Результатом является то, что LCS ( R ₃ , C ₂ ) содержит две подпоследовательности, (A) и (G).

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

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

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

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

	ε	А	Г	С	А	Т
ε	ε	ε	ε	ε	ε	ε
Г	ε	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$ε	${\displaystyle {\overset {\nwarrow }{\ }}}$(Г)	${\displaystyle {\overset {\ }{\leftarrow }}}$(Г)	${\displaystyle {\overset {\ }{\leftarrow }}}$(Г)	${\displaystyle {\overset {\ }{\leftarrow }}}$(Г)
А	ε	${\displaystyle {\overset {\nwarrow }{\ }}}$(А)	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$(А) и (Г)	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$(А) и (Г)	${\displaystyle {\overset {\nwarrow }{\ }}}$(ГА)	${\displaystyle {\overset {\ }{\leftarrow }}}$(ГА)
С	ε	${\displaystyle {\overset {\ \uparrow }{\ }}}$(А)	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$(А) и (Г)	${\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 требует только решений для текущей строки и предыдущей строки. Тем не менее, для длинных последовательностей эти последовательности могут стать многочисленными и длинными, требуя много места для хранения. Место для хранения можно сэкономить, сохраняя не сами подпоследовательности, а длину подпоследовательности и направление стрелок, как в таблице ниже.

Хранение длины, а не последовательности

	ε	А	Г	С	А	Т
ε	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
С	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]

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

	ε	А	Г	С	А	Т
ε	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
С	0	${\displaystyle {\overset {\ \uparrow }{\ }}}$1	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$1	${\displaystyle {\overset {\nwarrow }{\ }}}$2	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$2	${\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}}$2

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

${\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|.}$

This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. (March 2013) (Learn how and when to remove this message)

Функция ниже принимает в качестве входных данных последовательности X[1..m]и Y[1..n], вычисляет НКП между X[1..i]и Y[1..j]для всех 1 ≤ i ≤ mи 1 ≤ j ≤ nи сохраняет их в C[i,j]. C[m,n]будет содержать длину НКП Xи Y. ^[7]

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

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

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

функция backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j) если i = 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] вернуть backtrack(C, X, Y, i, j-1) вернуть backtrack(C, X, Y, i-1, j)

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

функция backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j) если i = 0 или j = 0 вернуть {""} если X[i] = Y[j] вернуть {Z + X[i] для всех Z в backtrackAll(C, X, Y, i-1, j-1)} Р := {} если 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) возврат R

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

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

Пусть будет « » и будет « ». Самая длинная общая подпоследовательность между и — это « ». Таблица , показанная ниже, которая сгенерирована функцией , показывает длины самых длинных общих подпоследовательностей между префиксами и . Строка th и столбец th показывают длину LCS между и .${\displaystyle X}$XMJYAUZ${\displaystyle Y}$MZJAWXU${\displaystyle X}$${\displaystyle Y}$MJAUCLCSLength${\displaystyle X}$${\displaystyle Y}$${\displaystyle i}$${\displaystyle j}$${\displaystyle X_{1..i}}$${\displaystyle Y_{1..j}}$

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

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

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

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

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

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

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

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

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

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

Чоудхури и Рамачандран разработали квадратичный по времени линейно-пространственный алгоритм ^{[9] [10]} для нахождения длины LCS вместе с оптимальной последовательностью, который на практике работает быстрее, чем алгоритм Хиршберга, благодаря своей превосходной производительности кэша. ^[9] Алгоритм имеет асимптотически оптимальную сложность кэша в рамках идеальной модели кэша . ^[11] Интересно, что сам алгоритм не обращает внимания на кэш ^[11], что означает, что он не делает никаких выборов на основе параметров кэша (например, размера кэша и размера строки кэша) машины.

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

Начиная с Chvátal & Sankoff (1975), ^[14] ряд исследователей изучали поведение длины самой длинной общей подпоследовательности, когда две заданные строки выбираются случайным образом из одного и того же алфавита. Когда размер алфавита постоянен, ожидаемая длина LCS пропорциональна длине двух строк, а константы пропорциональности (зависящие от размера алфавита) известны как константы Chvátal–Sankoff . Их точные значения неизвестны, но были доказаны верхние и нижние границы их значений, ^[15] и известно, что они растут обратно пропорционально квадратному корню из размера алфавита. ^[16] Было показано, что упрощенные математические модели задачи о самой длинной общей подпоследовательности контролируются распределением Трейси–Уидома . ^[17]

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

Реализация алгоритма Wikibook имеет страницу на тему: Самая длинная общая подпоследовательность

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