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

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

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

Для случая двух последовательностей из n и m элементов время работы подхода динамического программирования составляет O ( n × m ). ^[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 ( 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 (« БАН »,« АТ ») ^« АНА ».

Вторая собственность [ править ]

Если 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 [ править ]

Пусть две последовательности определены следующим образом: и . В префиксы являются ; префиксы есть . Позвольте представить набор самой длинной общей подпоследовательности префиксов и . Этот набор последовательностей дается следующим.${\ Displaystyle X = (x_ {1} x_ {2} \ cdots x_ {m})}$${\ Displaystyle Y = (y_ {1} y_ {2} \ cdots y_ {n})}$${\ displaystyle X}$${\ Displaystyle X_ {1,2, \ точки, м}}$${\ displaystyle Y}$${\ Displaystyle Y_ {1,2, \ точки, 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})}$

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

Будет найдена самая длинная подпоследовательность, общая для R = (GAC) и C = (AGCAT). Поскольку функция LCS использует «нулевой» элемент, удобно определять нулевые префиксы, которые пусты для этих последовательностей: R ₀ = Ø; и C ₀ = Ø. Все префиксы помещаются в таблице с C в первой строке ( что делает его с olumn заголовка) и 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" завершена

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

Для 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"

	Ø	А	грамм	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 ( 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

	Ø	А	грамм	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

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

Для двух строк и длина кратчайшей общей суперпоследовательности связана с длиной 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|.}$

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

Вычисление длины 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.

функция 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 for i: = 1..m for j: = 1..n if 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 # [ править ]

static  int [,]  LcsLength ( строка  a ,  строка  b ) {  int [,]  C  =  new  int [ a . Длина  +  1 ,  б . Длина  +  1 ];  // (a, b) .Length + 1  for  ( int  i  =  0 ;  i  <  a . Length ;  i ++)  C [ i ,  0 ]  =  0 ; для  ( int  j  =  0 ;  j  <  b . Length ;  j ++)  C [ 0 ,  j ]  =  0 ;  for  ( int  i  =  1 ;  i  <=  a . Length ;  i ++)  for  ( int  j  =  1 ;  j  <=  b . Length ;  j ++)  {  if  ( a[ i  -  1 ]  ==  b [ j  -  1 ]) // i-1, j-1  C [ i ,  j ]  =  C [ i  -  1 ,  j  -  1 ]  +  1 ;  иначе  C [ i ,  j ]  =  Math . Макс ( C [ i ,  j  -  1 ],  C [ i  -  1 ,  j]);  }  return  C ; }

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

Следующая функция отслеживает выбор, сделанный при вычислении Cтаблицы. Если последние символы в префиксах равны, они должны быть в 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] возврат с возвратом (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 # [ править ]

строка  Backtrack ( int [,]  C ,  char []  aStr ,  char []  bStr ,  int  x ,  int  y ) {  if  ( x  ==  0  |  y  ==  0 )  return  "" ;  if  ( aStr [ x  -  1 ]  ==  bStr [ y  -  1 ])  // x-1, y-1  возвращаем  backtrack ( C , aStr ,  bStr ,  x  -  1 ,  y  -  1 )  +  aStr [ x  -  1 ];  // x-1  if  ( C [ x ,  y  -  1 ]  >  C [ x  -  1 ,  y ])  return  backtrack ( C ,  aStr ,  bStr ,  x ,  y  -  1 );  возврат  назад (C ,  aStr ,  bStr ,  x  -  1 ,  y ); }

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

Если выбор и даст одинаково длинный результат, зачитайте обе полученные подпоследовательности. Это возвращается как набор этой функцией. Обратите внимание, что эта функция не является полиномиальной, так как она может ветвиться почти на каждом шаге, если строки похожи.${\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)} 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) вернуть R

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

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

function 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, я, 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] еще Распечатать ""

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

Пусть будет « » и будет « ». Самая длинная общая подпоследовательность между и - « ». Приведенная ниже таблица , созданная функцией , показывает длины самых длинных общих подпоследовательностей между префиксами и . В строке и столбце показана длина 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 между и , либо и .${\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 сравнений. В большинстве реальных случаев, особенно при обнаружении различий и исправлений исходного кода, начало и конец файлов редко меняются, и почти наверняка не оба одновременно. Если в середине последовательности изменились только несколько элементов, можно удалить начало и конец. Это снижает не только требования к памяти для матрицы, но и количество необходимых сравнений.

функция LCS (X [1..m], Y [1..n]) начало: = 1 m_end: = m 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] 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, матрицу можно с легкостью уменьшить до матрицы или до вектора (более разумно), поскольку для подхода динамического программирования требуются только текущий и предыдущий столбцы матрицы. Алгоритм Хиршберга позволяет построить саму оптимальную последовательность за то же квадратичное время и линейные пространственные ограничения. ^[7]${\displaystyle 2\times \min(n,m)}$${\displaystyle \min(m,n)+1}$

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

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

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

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

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

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

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

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

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

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