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

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

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

Сложность [ править ]

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

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

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

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

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

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

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

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

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

Префиксы [ править ]

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

С ₀ = ()

С ₁ = (А)

S2 ₌ (AG)

S3 ₌ (АРУ)

S ₄ = (AGCA).

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

Первый объект [ править ]

LCS ( X ^ A , Y ^ A ) = LCS ( X , Y )^ A для всех строк X , Y и всех символов A , где ^ обозначает конкатенацию строк. Это позволяет упростить вычисление LCS для двух последовательностей, заканчивающихся одним и тем же символом. Например, LCS ("БАНАНА","АТАНА") = LCS ("БАНАН","АТАН")^"А", Продолжая для остальных общих символов, LCS ("БАНАНА","АТАНА") = LCS (" БАН","АТ")^"АНА".

Второе свойство [ править ]

Если 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», «БЦДГК»).

LCS Определена функция [ править ]

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

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

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

Рабочий пример [ править ]

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

LCS-строки
	е	А	г	С	А	Т
е	е	е	е	е	е	е
г	е
А	е
С	е

Эта таблица используется для хранения последовательности 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), что есть (Г).

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

LCS ( R ₁ , C ₄ ) также представляет собой (G).

LCS ( R ₁ , C ₅ ) также представляет собой (G).

Ряд «G» завершен.
	е	А	г	С	А	Т
е	е	е	е	е	е	е
г	е	${\overset {\ \ \uparrow }{\leftarrow }}$ е	${\overset {\nwarrow }{\ }}$ (Г)	${\overset {\ }{\leftarrow }}$ (Г)	${\overset {\ }{\leftarrow }}$ (Г)	${\overset {\ }{\leftarrow }}$ (Г)
А	е
С	е

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

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

Для LCS ( R2 _, C2 C3 _LCS ) A не соответствует C. ( R2 , _{(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» завершены.
	е	А	г	С	А	Т
е	е	е	е	е	е	е
г	е	${\overset {\ \ \uparrow }{\leftarrow }}$ е	${\overset {\nwarrow }{\ }}$ (Г)	${\overset {\ }{\leftarrow }}$ (Г)	${\overset {\ }{\leftarrow }}$ (Г)	${\overset {\ }{\leftarrow }}$ (Г)
А	е	${\overset {\nwarrow }{\ }}$ (А)	${\overset {\ \ \uparrow }{\leftarrow }}$ (БЫТЬ)	${\overset {\ \ \uparrow }{\leftarrow }}$ (БЫТЬ)	${\overset {\nwarrow }{\ }}$ (GA)	${\overset {\ }{\leftarrow }}$ (GA)
С	е

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

Для LCS ( R3 _, ) C2 _. C и G не совпадают И LCS ( R ₃ , C ₁ ), и LCS ( R ₂ , C ₂ ) имеют по одному элементу. В результате LCS ( R3 _, . C2 ₎ содержит две подпоследовательности: (A) и (G)

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

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

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

Заполненная таблица LCS
	е	А	г	С	А	Т
е	е	е	е	е	е	е
г	е	${\overset {\ \ \uparrow }{\leftarrow }}$ е	${\overset {\nwarrow }{\ }}$ (Г)	${\overset {\ }{\leftarrow }}$ (Г)	${\overset {\ }{\leftarrow }}$ (Г)	${\overset {\ }{\leftarrow }}$ (Г)
А	е	${\overset {\nwarrow }{\ }}$ (А)	${\overset {\ \ \uparrow }{\leftarrow }}$ (БЫТЬ)	${\overset {\ \ \uparrow }{\leftarrow }}$ (БЫТЬ)	${\overset {\nwarrow }{\ }}$ (GA)	${\overset {\ }{\leftarrow }}$ (GA)
С	е	${\overset {\ \uparrow }{\ }}$ (А)	${\overset {\ \ \uparrow }{\leftarrow }}$ (БЫТЬ)	${\overset {\nwarrow }{\ }}$ (AC) и (GC)	${\overset {\ \ \uparrow }{\leftarrow }}$ (AC) и (GC) и (GA)	${\overset {\ \ \uparrow }{\leftarrow }}$ (AC) и (GC) и (GA)

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

Подход с отслеживанием [ править ]

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

Хранение длины, а не последовательностей
	А	г	С	А	Т
е	0	0	0	0	0
г	${\overset {\ \ \uparrow }{\leftarrow }}$ 0	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1
А	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ }{\leftarrow }}$ 2
С	${\overset {\ \uparrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2

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

Пример обратной трассировки
	А	г	С	А	Т
е	0	0	0	0	0
г	${\overset {\ \ \uparrow }{\leftarrow }}$ 0	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1
А	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ }{\leftarrow }}$ 2
С	${\overset {\ \uparrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2

Связь с другими проблемами [ править ]

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

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

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

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

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

Вычисление длины LCS [ править ]

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

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

Альтернативно мемоизацию можно использовать .

Чтение LCS [ править ]

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

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

Чтение всех LCS [ править ]

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

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

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

Эта функция вернется через матрицу 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) 
          напечатать " " + X[i] 
      иначе, если  j > 0  и  (i = 0  или  C[i,j-1] ≥ C[i-1,j]) 
          printDiff(C, X, Y, i, j-1) 
          напечатайте "+ " + Y[j] 
      иначе, если  я > 0  и  (j = 0  или  C[i,j-1] < C[i-1,j]) 
          printDiff(C, X, Y, i-1, j) 
          напечатайте "-" + X[i] 
      еще 
          Распечатать ""

Пример [ править ]

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

		0	1	2	3	4	5	6	7
		е	М	С	Дж	А	В	Икс	В
0	е	0	0	0	0	0	0	0	0
1	Икс	0	0	0	0	0	0	1	1
2	М	0	1	1	1	1	1	1	1
3	Дж	0	1	1	2	2	2	2	2
4	И	0	1	1	2	2	2	2	2
5	А	0	1	1	2	3	3	3	3
6	В	0	1	1	2	3	3	3	4
7	С	0	1	2	2	3	3	3	4

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

Оптимизация кода [ править ]

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

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

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

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

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

Сократите время сравнения [ править ]

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

Превратить строки в хэши [ править ]

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

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

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

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

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

Уменьшить количество промахов в кэше [ править ]

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

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

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

Поведение со случайными строками [ править ]

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

См. также [ править ]

Ссылки [ править ]

^ Дэвид Майер (1978). «Сложность некоторых задач о подпоследовательностях и суперпоследовательностях» . Дж. АКМ . 25 (2). ACM Press: 322–336. дои : 10.1145/322063.322075 . S2CID 16120634 .
^ Вагнер, Роберт; Фишер, Майкл (январь 1974 г.). «Проблема построчной коррекции». Журнал АКМ . 21 (1): 168–173. CiteSeerX 10.1.1.367.5281 . дои : 10.1145/321796.321811 . S2CID 13381535 .
^ Перейти обратно: ^а ^б Л. Бергрот, Х. Хаконен и Т. Райта (7–29 сентября 2000 г.). Обзор алгоритмов самых длинных общих подпоследовательностей . Труды Седьмого международного симпозиума по обработке строк и поиску информации. SPIRE 2000. Куруна, Испания: Компьютерное общество IEEE. стр. 39–48. дои : 10.1109/SPIRE.2000.878178 . ISBN 0-7695-0746-8 . S2CID 10375334 .
^ Рональд И. Гринберг (6 августа 2003 г.). «Границы числа самых длинных общих подпоследовательностей». arXiv : cs.DM/0301030 .
^ Ся, Сюйхуа (2007). Биоинформатика и клетка: современные вычислительные подходы в геномике, протеомике и транскриптомике . Нью-Йорк: Спрингер. п. 24 . ISBN 978-0-387-71336-6 .
^ Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн (2001). «15,4». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 350–355. ISBN 0-262-53196-8 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009) [1990]. «Динамическое программирование». Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. п. 394. ИСБН 0-262-03384-4 .
^ Хиршберг, Д.С. (1975). «Алгоритм линейного пространства для вычисления максимальных общих подпоследовательностей» . Коммуникации АКМ . 18 (6): 341–343. дои : 10.1145/360825.360861 . S2CID 207694727 .
^ Перейти обратно: ^а ^б Чоудхури, Резаул; Рамачандран, Виджая (январь 2006 г.). «Динамическое программирование без учета кэша» . Материалы семнадцатого ежегодного симпозиума ACM-SIAM по дискретному алгоритму - SODA '06 . стр. 591–600. дои : 10.1145/1109557.1109622 . ISBN 0898716055 . S2CID 9650418 .
^ Чоудхури, Резаул; Ле, Хай-Сон; Рамачандран, Виджая (июль 2010 г.). «Динамическое программирование без учета кэша для биоинформатики» . Транзакции IEEE/ACM по вычислительной биологии и биоинформатике . 7 (3): 495–510. дои : 10.1109/TCBB.2008.94 . ПМИД 20671320 . S2CID 2532039 .
^ Перейти обратно: ^а ^б Фриго, Маттео; Лейзерсон, Чарльз Э.; Прокоп, Харальд; Рамачандран, Шридхар (январь 2012 г.). «Алгоритмы, не обращающие внимания на кэш» . Транзакции ACM на алгоритмах . 8 (1): 1–22. дои : 10.1145/2071379.2071383 .
^ Апостолико, Альберто; Галил, Цви (29 мая 1997 г.). Алгоритмы сопоставления с образцом . Издательство Оксфордского университета. ISBN 9780195354348 .
^ Масек, Уильям Дж.; Патерсон, Майкл С. (1980), «Более быстрый алгоритм вычисления расстояний редактирования строк», Journal of Computer and System Sciences , 20 (1): 18–31, doi : 10.1016/0022-0000(80)90002-1 , MR 0566639 .
^ Хватал, Вацлав ; Санкофф, Дэвид (1975), «Самые длинные общие подпоследовательности двух случайных последовательностей», Journal of Applied Probability , 12 (2): 306–315, doi : 10.2307/3212444 , JSTOR 3212444 , MR 0405531 , S2CID 250345191 .
^ Люкер, Джордж С. (2009), «Улучшенные границы средней длины самых длинных общих подпоследовательностей», Журнал ACM , 56 (3), A17, doi : 10.1145/1516512.1516519 , MR 2536132 , S2CID 7232681 .
^ Киви, Маркос; Лебл, Мартин; Матушек, Иржи (2005), «Ожидаемая длина самой длинной общей подпоследовательности для больших алфавитов», Advance in Mathematics , 197 (2): 480–498, arXiv : math/0308234 , doi : 10.1016/j.aim.2004.10.012 , МР 2173842 .
^ Маджумдар, Сатья Н.; Нечаев, Сергей (2005), «Точные асимптотические результаты для модели выравнивания последовательностей Бернулли», Physical Review E , 72 (2): 020901, 4, arXiv : q-bio/0410012 , Bibcode : 2005PhRvE..72b0901M , doi : 10.1103/PhysRevE.72.020901 , MR 2177365 , PMID 16196539 , S2CID 11390762 .

Внешние ссылки [ править ]

[1] Дэвид Майер (1978). «Сложность некоторых задач о подпоследовательностях и суперпоследовательностях» . Дж. АКМ . 25 (2). ACM Press: 322–336. дои : 10.1145/322063.322075 . S2CID 16120634 .

[2] Вагнер, Роберт; Фишер, Майкл (январь 1974 г.). «Проблема построчной коррекции». Журнал АКМ . 21 (1): 168–173. CiteSeerX 10.1.1.367.5281 . дои : 10.1145/321796.321811 . S2CID 13381535 .

[BHR00-3] Перейти обратно: ^а ^б Л. Бергрот, Х. Хаконен и Т. Райта (7–29 сентября 2000 г.). Обзор алгоритмов самых длинных общих подпоследовательностей . Труды Седьмого международного симпозиума по обработке строк и поиску информации. SPIRE 2000. Куруна, Испания: Компьютерное общество IEEE. стр. 39–48. дои : 10.1109/SPIRE.2000.878178 . ISBN 0-7695-0746-8 . S2CID 10375334 .

[4] Рональд И. Гринберг (6 августа 2003 г.). «Границы числа самых длинных общих подпоследовательностей». 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 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[:1-7] Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009) [1990]. «Динамическое программирование». Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. п. 394. ИСБН 0-262-03384-4 .

[8] Хиршберг, Д.С. (1975). «Алгоритм линейного пространства для вычисления максимальных общих подпоследовательностей» . Коммуникации АКМ . 18 (6): 341–343. дои : 10.1145/360825.360861 . S2CID 207694727 .

[CR-06-9] Перейти обратно: ^а ^б Чоудхури, Резаул; Рамачандран, Виджая (январь 2006 г.). «Динамическое программирование без учета кэша» . Материалы семнадцатого ежегодного симпозиума ACM-SIAM по дискретному алгоритму - SODA '06 . стр. 591–600. дои : 10.1145/1109557.1109622 . ISBN 0898716055 . S2CID 9650418 .

[CLR-08-10] Чоудхури, Резаул; Ле, Хай-Сон; Рамачандран, Виджая (июль 2010 г.). «Динамическое программирование без учета кэша для биоинформатики» . Транзакции IEEE/ACM по вычислительной биологии и биоинформатике . 7 (3): 495–510. дои : 10.1109/TCBB.2008.94 . ПМИД 20671320 . S2CID 2532039 .

[FLPR-12-11] Перейти обратно: ^а ^б Фриго, Маттео; Лейзерсон, Чарльз Э.; Прокоп, Харальд; Рамачандран, Шридхар (январь 2012 г.). «Алгоритмы, не обращающие внимания на кэш» . Транзакции ACM на алгоритмах . 8 (1): 1–22. дои : 10.1145/2071379.2071383 .

[12] Апостолико, Альберто; Галил, Цви (29 мая 1997 г.). Алгоритмы сопоставления с образцом . Издательство Оксфордского университета. ISBN 9780195354348 .

[13] Масек, Уильям Дж.; Патерсон, Майкл С. (1980), «Более быстрый алгоритм вычисления расстояний редактирования строк», Journal of Computer and System Sciences , 20 (1): 18–31, doi : 10.1016/0022-0000(80)90002-1 , MR 0566639 .

[14] Хватал, Вацлав ; Санкофф, Дэвид (1975), «Самые длинные общие подпоследовательности двух случайных последовательностей», Journal of Applied Probability , 12 (2): 306–315, doi : 10.2307/3212444 , JSTOR 3212444 , MR 0405531 , S2CID 250345191 .

[15] Люкер, Джордж С. (2009), «Улучшенные границы средней длины самых длинных общих подпоследовательностей», Журнал ACM , 56 (3), A17, doi : 10.1145/1516512.1516519 , MR 2536132 , S2CID 7232681 .

[16] Киви, Маркос; Лебл, Мартин; Матушек, Иржи (2005), «Ожидаемая длина самой длинной общей подпоследовательности для больших алфавитов», Advance in Mathematics , 197 (2): 480–498, arXiv : math/0308234 , doi : 10.1016/j.aim.2004.10.012 , МР 2173842 .

[17] Маджумдар, Сатья Н.; Нечаев, Сергей (2005), «Точные асимптотические результаты для модели выравнивания последовательностей Бернулли», Physical Review E , 72 (2): 020901, 4, arXiv : q-bio/0410012 , Bibcode : 2005PhRvE..72b0901M , doi : 10.1103/PhysRevE.72.020901 , MR 2177365 , PMID 16196539 , S2CID 11390762 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

v т Это Струны
String metric	Approximate string matching Bitap algorithm Damerau–Levenshtein distance Edit distance Gestalt pattern matching Hamming distance Jaro–Winkler distance Lee distance Levenshtein automaton Levenshtein distance Wagner–Fischer algorithm
String-searching algorithm	Apostolico–Giancarlo algorithm Boyer–Moore string-search algorithm Boyer–Moore–Horspool algorithm Knuth–Morris–Pratt algorithm Rabin–Karp algorithm Raita algorithm Trigram search Two-way string-matching algorithm Zhu–Takaoka string matching algorithm
Multiple string searching	Aho–Corasick Commentz-Walter algorithm
Regular expression	Comparison of regular-expression engines Regular grammar Thompson's construction Nondeterministic finite automaton
Sequence alignment	BLAST Hirschberg's algorithm Needleman–Wunsch algorithm Smith–Waterman algorithm
Data structure	DAFSA Suffix array Suffix automaton Suffix tree Generalized suffix tree Rope Ternary search tree Trie
Other	Parsing Pattern matching Compressed pattern matching Longest common subsequence Longest common substring Sequential pattern mining Sorting String rewriting systems String operations