최장 공통 서브시퀀스 문제
Longest common subsequence problemLongest Common Succession(LCS; 최장 공통 서브시퀀스) 문제는 시퀀스 세트 내의 모든 시퀀스에 공통되는 최장 서브시퀀스를 찾는 문제입니다(대개 2개의 시퀀스만).이것은 가장 긴 일반적인 서브스트링 문제와 다릅니다.기판과는 달리 원래 시퀀스 내에서 연속적인 위치를 차지하기 위해 후속 작업이 필요하지 않습니다.가장 긴 공통적인 후속 문제는 유틸리티와 같은 데이터 비교 프로그램의 기반인 고전적인 컴퓨터 과학 문제이며 컴퓨터 언어학 및 생물 정보학에서 응용되고 있습니다.또한 Git과 같은 리비전 제어 시스템에서 리비전 제어된 파일 집합의 여러 변경 사항을 조정하기 위해 널리 사용됩니다.
예를 들어 시퀀스(ABCD)와 (ACBAD)에 대해 생각해 보겠습니다.(AB), (AC), (AD), (BD) 및 (CD)의 5가지 공통 서브시퀀스, (ABD) 및 (ACD)의 2가지 공통 서브시퀀스, 더 이상 공통 서브시퀀스가 없습니다.따라서 (ABD)와 (ACD)는 가장 긴 공통 서브시퀀스입니다.
복잡성
임의의 수의 입력 시퀀스의 일반적인 경우 문제는 [1]NP-hard입니다.시퀀스 수가 일정하면 동적 프로그래밍을 통해 다항 시간 내에 문제를 해결할 수 있습니다.
가 .. , ..., 인N(\ N 시퀀스를 하면 첫 번째 시퀀스의 2 를 각각 테스트하여 나머지 시퀀스의 후속인지 여부를 판별할 수 있습니다.나머지 시퀀스의 길이에서 시간 선형으로, 따라서 이 알고리즘의 시간은
n과 m 요소의 두 시퀀스의 경우 동적 프로그래밍 접근법의 실행 시간은 O(n × m)[2]이다.임의의 수의 입력 시퀀스에 대해 동적 프로그래밍 접근은 다음과 같은 해결책을 제공합니다.
LCS [3]길이, 알파벳 크기 또는 둘 다에 따라 복잡도가 낮은 방법이 있습니다.
LCS가 반드시 고유하다고는 할 수 없습니다.최악의 경우 공통 서브시퀀스의 수는 입력 길이로 기하급수적이므로 알고리즘의 [4]복잡도는 적어도 기하급수적이어야 합니다.
2개의 시퀀스에 대한 솔루션
LCS 문제에는 최적의 서브구조가 있습니다.이 문제는 보다 작고 단순한 서브문제로 분할할 수 있습니다.이러한 서브문제는, 보다 단순한 서브문제로 분할할 수 있습니다.이러한 서브문제는, 최종적으로 솔루션이 사소한 것이 될 때까지 계속됩니다.특히 LCS에는 중복되는 서브 문제가 있습니다.즉, 상위 레벨의 서브 문제에 대한 솔루션은 하위 레벨의 서브 문제에 대한 솔루션을 재사용하는 경우가 많습니다.이 두 가지 속성의 문제는 서브 문제 해결 방법을 메모하는 동적 프로그래밍 접근법에 따라 처리됩니다. 즉, 서브 문제 해결 방법은 재사용할 수 있도록 저장됩니다.
프리픽스
S의 프리픽스S는n [5]S의 첫 번째 n자로 정의됩니다.예를 들어 S =(AGCA)의 프레픽스는 다음과 같습니다.
- S0 = ()
- S1 = (A)
- S2 = (AG)
- S3 = (AGC)
- S4 = (AGCA).
LCS(X, Y)를 X 및 Y에 공통되는 최장 수열을 계산하는 함수라고 합니다.이러한 함수에는 두 가지 흥미로운 특성이 있습니다.
첫 번째 속성
모든 문자열 X, Y 및 모든 기호 A에 대해 LCS(X^A, Y^A) = LCS(X, Y)^A. 여기서 ^는 문자열 연결을 나타냅니다.이를 통해 동일한 기호로 끝나는 두 시퀀스에 대한 LCS 계산을 단순화할 수 있습니다.예를 들어 LCS('BANANA'),ATANA") = LCS("BANAN", "ATAN")^"A", 나머지 공통 기호인 LCS("BANANANA")에 대해 계속 진행합니다.ATANA") = LCS("BAN", AT")^"ANA"
세컨드 프로퍼티
A와 B가 별개의 기호(AaB)인 경우, LCS(X^A, Y^B)는 모든 문자열 X, Y에 대해 집합 {LCS(X^A, Y), LCS(X, Y^B)}의 최대 길이 문자열 중 하나입니다.
예를 들어 LCS("ABCDEFG", BCDGK")는 LCS("ABCDEFG", BCDG")와 LCS("ABCDEF", BCDGK") 중 가장 긴 문자열입니다.두 문자열의 길이가 같으면 임의로 선택할 수 있습니다.
속성을 실현하려면 다음 두 가지 경우를 구분합니다.
- LCS("ABCDEFG", BCDGK")가 "G"로 끝나는 경우 최종 "K"는 LCS에 있을 수 없으므로 LCS("ABCDEFG", BCDGK") = LCS(ABC(ABCDEFG),
- LCS("ABCDEFG", BCDGK")가 "G"로 끝나지 않으면 최종 "G"는 LCS에 있을 수 없으므로 LCS("ABCDEFG", BCDGK") = LCS(ABC(ABCDEFG") DEFG",
LCS 함수의 정의
X ( 2 x) { X = (} 및 ( 2 y) { Y =(2}\ y_의 2개의 시퀀스를 정의합니다.X X의 프리픽스는 1,2 1 \ Y(\ Y의 프리픽스는 (\Y입니다는 i})와 Yj의 가장 긴 공통 서브시퀀스 세트를 나타냅니다.이 시퀀스의 세트는 다음과 같습니다.
와 의 를 찾으려면 와 를 합니다.같은 경우 -,Y - 1를t, 같지 않은 L S j -i}) 중 가장 깁니다. 및 S ( i - , j) { { { } ( _ { i - ) 이 유지됩니다.(같은 길이이지만 동일하지 않으면 둘 다 유지됩니다).
작업 예
R = (GAC) 및 C = (AGCAT)에 공통되는 가장 긴 수열은 발견됩니다.LCS 함수는 "zeroth" 요소를 사용하기 때문에 R = ; 및 C0 = ø의0 시퀀스에 대해 비어 있는 프리픽스를 0으로 정의하는 것이 편리합니다.모든 프리픽스는 첫 번째 행에 C가 있고 첫 번째 행에 R이 있는 테이블에 배치되어 있습니다(열 머리글이 됩니다).
ø | A | G | C | A | T | |
---|---|---|---|---|---|---|
ø | ø | ø | ø | ø | ø | ø |
G | ø | |||||
A | ø | |||||
C | ø |
이 표는 계산의 각 단계에 대한 LCS 시퀀스를 저장하기 위해 사용됩니다.빈 시퀀스를 빈 시퀀스와 비교할 때 가장 긴 공통 시퀀스는 항상 빈 시퀀스가 되기 때문에 두 번째 열과 두 번째 행은 ø로 채워졌습니다.
LCS(R1, C1)는 각 시퀀스의 첫 번째 요소를 비교하여 결정된다.G와 A는 동일하지 않기 때문에 이 LCS는 LCS(R1, C0)와 LCS(R0, C1)의 2개의 시퀀스 중 가장 긴('두 번째 속성'을 사용합니다) 것을 취득합니다.표에 따르면 둘 다 비어 있기 때문에 아래 표와 같이 LCS1(R1, C)도 비어 있습니다.화살표는 위의 셀인 LCS(R0, C1)와 왼쪽 셀인 LCS(R1, C0) 양쪽에서 시퀀스가 온 것을 나타냅니다.
LCS(R1, C2)는 G와 G를 비교하여 결정한다.일치하므로 왼쪽 상단 시퀀스인 LCS(R1, C)에 G가 추가되며, LCS(R0, C), 즉 (G)가 부여된다.
LCS(R1, C3)의 경우 G와 C가 일치하지 않습니다.위의 시퀀스는 비어 있습니다.왼쪽의 시퀀스에는 G라는1개의 요소가 포함되어 있습니다.이들 중 가장 긴 것을 선택하면 LCS(R1, C3)가 (G)가 됩니다.화살표는 두 시퀀스 중 가장 길기 때문에 왼쪽을 가리킵니다.
LCS(R1, C4)도 마찬가지로 (G)입니다.
LCS(R1, C5)도 마찬가지로 (G)입니다.
ø | A | G | C | A | T | |
---|---|---|---|---|---|---|
ø | ø | ø | ø | ø | ø | ø |
G | ø | 화살표 } | (G) | arrow (G) | arrow (G) | arrow (G) |
A | ø | |||||
C | ø |
LCS(R2, C1)의 경우 A와 A를 비교합니다.두 요소가 일치하므로 A가 (에 추가되어 (A)가 됩니다.
LCS(R2, C2)에서는 A와 G가 일치하지 않기 때문에 (G) LCS12(R, C)와 (A1) LCS(R2, C) 중 가장 긴 것이 사용됩니다.이 경우, 각 요소에는 1개의 요소가 포함되어 있기 때문에, 이 LCS에는 (A)와 (G)의 2개의 서브시퀀스가 주어집니다.
LCS(R2, C3)에서는 A가 C와 일치하지 않습니다.LCS(R2, C2)에는 시퀀스(A)와 (G)가 포함되어 있습니다.LCS(R1, C3)는 (G)이며, LCS(R2, C)는 이미 LCS(R, C2)에 포함되어 있습니다.그 결과, LCS(R2, C3)에는 (A)와 (G)의 2개의 서브시퀀스도 포함됩니다.
LCS(R2, C4)의 경우 A는 A와 일치합니다.A는 왼쪽 상단 셀에 부가되어 Giving(GA)이 됩니다.
LCS(R2, C5)의 경우 A는 T와 일치하지 않습니다.(GA)와 (G)의 두 시퀀스를 비교하면 가장 긴 것은 (GA)이므로 LCS(R2, C5)는 (GA)이다.
ø | A | G | C | A | T | |
---|---|---|---|---|---|---|
ø | ø | ø | ø | ø | ø | ø |
G | ø | 화살표 } | (G) | arrow (G) | arrow (G) | arrow (G) |
A | ø | (A) | {\ 화살표A) & (G) | {\ 화살표A) & (G) | ( | arrow ( |
C | ø |
LCS(R3, C1)에서는 C와 A가 일치하지 않기 때문에 LCS(R3, C1)는 2개의 시퀀스 중 가장 긴 시퀀스(A)를 취득합니다.
LCS(R3, C2), C와 G가 일치하지 않습니다.LCS(R3, C1)와 LCS(R2, C2)는 모두 1개의 요소를 가지고 있습니다.그 결과, LCS(R3, C2)에는 (A)와 (G)의 2개의 서브시퀀스가 포함됩니다.
LCS(R3, C3), C 및 C가 일치하는 경우, C는 LCS(R2, C)에 부가됩니다.LCS(R2, C)에는 (A)와 (G)의 2개의 서브시퀀스가 포함되어 (AC)와 (GC)가 부여됩니다.
LCS(R3, C4), C와 A가 일치하지 않습니다.(AC)와 (GC)를 포함한 LCS(R3, C3)와 (GA)를 포함한 LCS(R2, C4)를 조합하면 (AC), (GC), (GA)의 총 3개의 시퀀스를 얻을 수 있다.
마지막으로 LCS(R3, C5)의 경우 C와 T가 일치하지 않습니다.그 결과 LCS(R3, C5)에는 (AC), (GC) 및 (GA)의 3개의 시퀀스도 포함됩니다.
ø | A | G | C | A | T | |
---|---|---|---|---|---|---|
ø | ø | ø | ø | ø | ø | ø |
G | ø | 화살표 } | (G) | arrow (G) | arrow (G) | arrow (G) |
A | ø | (A) | {\ 화살표A) & (G) | {\ 화살표A) & (G) | ( | arrow ( |
C | ø | (A) | {\ 화살표A) & (G) | () & (GC | 화살표 (AC) & (GC) & ( | 화살표 (AC) & (GC) & ( |
최종 결과는 마지막 셀에 (AGCAT)와 (GAC)에 공통되는 모든 최장 서브시퀀스가 포함됩니다.이것들은 (AC), (GC) 및 (GA)입니다.또한 이 표는 가능한 모든 프레픽스쌍에 대해 가장 긴 공통 서브시퀀스를 나타내고 있습니다.예를 들어 (AGC) 및 (GA)의 경우 가장 긴 공통 서브시퀀스는 (A) 및 (G)입니다.
트레이스백 어프로치
LCS 테이블 행의 LCS를 계산하려면 현재 행과 이전 행에 대한 솔루션만 필요합니다.그러나 긴 시퀀스의 경우 이러한 시퀀스는 수가 많고 길어질 수 있으므로 많은 저장 공간이 필요합니다.스토리지 공간은 아래 표와 같이 실제 시퀀스가 아니라 시퀀스의 길이와 화살표 방향을 저장함으로써 절약할 수 있습니다.
ø | A | G | C | A | T | |
---|---|---|---|---|---|---|
ø | 0 | 0 | 0 | 0 | 0 | 0 |
G | 0 | } 화살표 | 1 | displaystyle | displaystyle | displaystyle |
A | 0 | 1 | } 화살표 | } 화살표 | {2 | |
C | 0 | 1 | } 화살표 | {2 | } 화살표 | } 화살표 |
실제 서브시퀀스는 표의 마지막 셀부터 시작하여 화살표를 거꾸로 따르는 "추적" 절차에서 추론됩니다.길이가 줄어들면 시퀀스에 공통 요소가 있어야 합니다.셀에 화살표가 2개 표시될 경우 여러 경로를 사용할 수 있습니다.아래 표는 이러한 분석을 위한 표로, 길이가 감소하려고 하는 셀에 수치를 채색한 것입니다.굵은 글씨 숫자는 시퀀스(GA)[6]를 추적합니다.
ø | A | G | C | A | T | |
---|---|---|---|---|---|---|
ø | 0 | 0 | 0 | 0 | 0 | 0 |
G | 0 | } 화살표 | 1 | 1 | displaystyle | displaystyle |
A | 0 | 1 | } 화살표 | } 화살표 | 2 | 2 |
C | 0 | 1 | } 화살표 | {2 | } 화살표 | 2 |
기타 문제와의 관계
For two strings and , the length of the shortest common supersequence is related to the length of the LCS by[3]
삽입 및 삭제만 허용(대체 없음)되거나 대체 비용이 삽입 또는 삭제 비용의 2배인 경우 편집 거리는 다음과 같습니다.
동적 프로그래밍 솔루션 코드
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]) i : = 0 . m C [ i , 0 ] = j : = 0 . n C [ 0 , j ] = i : = 1 . m = [ X ]의 경우 0 의 경우, LCSLength (X [ 1 . m ], Y [ 1 . n ]) C [ 0 . n ]) C = 어레이 ( 0 ) = 0 )
또는 메모화를 사용할 수도 있습니다.
C#의 예
정적인 인트 LcsLength(스트링 a, 스트링 b) { 인트 m = a.길이; 인트 n = b.길이; 인트[,] C = 신규 인트[m + 1, n + 1]; 위해서 (인트 i = 0; i <=> m; i++) C[i, 0] = 0; 위해서 (인트 j = 0; j <=> n; j++) C[0, j] = 0; 위해서 (인트 i = 1; i <=> m; i++) 위해서 (인트 j = 1; j <=> n; j++) { 한다면 (a[i - 1] == b[j - 1]) C[i, j] = C[i - 1, j - 1] + 1; 또 다른 C[i, j] = 수학.맥스.(C[i, j - 1], C[i - 1, j]); } 돌아가다 C[m, n]; }
LCS 읽기
다음 함수는 다음을 계산할 때 선택한 항목을 역추적합니다.C
prefix의 마지막 문자가 같을 경우 LCS에 있어야 합니다.그렇지 않은 경우 스타일 }) 및 yj 스타일 를 유지하는 LCS 중 가장 큰 것을 확인하고 동일한 선택을 합니다.길이가 같으면 하나만 고르세요.함수를 호출하다i=m
그리고.j=n
.
함수 백트랙(C[0..m,0..n], X[1..m], Y[1..n], i, j) i = 0이면 X[i] = Y[j] 리턴 백트랙(C, X, Y, i-1, j-1) + X[i] if C-I,
C#의 예
스트링 백트랙(인트[,] C, 차[] aStr, 차[] 동작, 인트 x, 인트 y) { 한다면 (x == 0 y == 0) 돌아가다 ""; 한다면 (aStr[x - 1] == 동작[y - 1]) // x-1, y-1 돌아가다 되돌아가다(C, aStr, 동작, x - 1, y - 1) + aStr[x - 1]; // x-1 한다면 (C[x, y - 1] > C[x - 1, y]) 돌아가다 되돌아가다(C, aStr, 동작, x, y - 1); 돌아가다 되돌아가다(C, aStr, 동작, x - 1, y); }
모든 LCS 읽기
i })와 y j 스타일 를 하면 결과가 동일하게 길어지는 경우 두 개의 후속 결과를 모두 읽습니다.이것은 이 함수에 의해 세트로 반환됩니다.문자열이 비슷할 경우 거의 모든 단계에서 분기될 수 있으므로 이 함수는 다항식이 아닙니다.
function backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j) i = 0이면 X[i]가 {"}을(를) 반환합니다. BacktrackAll(C, X-i, J-1)의 모든 Z에 대해 {Z + X[i]를 반환합니다.R이 되다
diff 인쇄
이 함수는 C 매트릭스를 역추적하여 두 시퀀스 간의 차이를 인쇄합니다.교환하면 다른 답변을 얻을 수 있습니다.≥
그리고.<
,와 함께>
그리고.≤
아래.
기능 printDiff(C[0..m,0..n], X[1..m], Y[1..n], 나는, j)만약 내입니다.;=0과 j>=0과 X[나는])Y[j]printDiff(C, X, Y, i-1, j-1)인쇄""+X[나는] 다른 만약 j>0과(나는 정도 0또는 C[i,j-1]≥ C[i-1,j])printDiff(C, X, Y, 나는, 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 Y는 "MZJAWXU
". X디스플레이 X와 Y Y 의 가장 긴 공통 서브시퀀스는"MJAU
". 테이블C
함수에 의해 생성되는 아래 그림LCSLength
는 프리픽스(\ X와 Y Y 사이의 가장 긴 공통 서브시퀀스 길이를 나타냅니다. i 과j(\ j 행은 의 LCS 길이를 나타냅니다. 및 를 누릅니다.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
---|---|---|---|---|---|---|---|---|---|
ø | M | Z | J | A | W | X | U | ||
0 | ø | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | X | 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 | A | 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 |
강조 표시된 숫자는 함수의 경로를 나타냅니다.backtrack
LCS를 읽을 때 오른쪽 아래에서 왼쪽 상단 모서리로 이어집니다.X X와 Y Y의 현재 기호가 동일한 경우 이들은 LCS의 일부이며 위 및 왼쪽으로 이동합니다(굵은 글씨로 표시).그렇지 않은 경우, 어떤 셀이 더 큰지 여부에 따라 위 또는 왼쪽으로 이동합니다.은 X1 의 LCS를 취득하는 것에 대응합니다.- 및 ({
코드 최적화
상기의 알고리즘에 대해서, 몇개의 최적화를 실시해, 실제의 경우에 맞추어 고속화할 수 있습니다.
문제 세트를 줄입니다.
순진한 알고리즘의 C행렬은 시퀀스의 길이에 따라 2차적으로 커집니다.두 개의 100개 항목 시퀀스의 경우 10,000개 항목 매트릭스가 필요하며 10,000개 비교가 필요합니다.대부분의 실제 사례(특히 소스 코드 차이와 패치)에서 파일의 시작과 끝은 거의 변경되지 않으며 동시에 변경되지 않습니다.시퀀스 도중에 일부 항목만 변경된 경우 시작과 끝을 제거할 수 있습니다.따라서 매트릭스의 메모리 요건뿐만 아니라 비교해야 할 수도 줄어듭니다.
LCS(X[1..m], Y[1..n]) start : = 1 m_end : = m n_end : = n 시작 시 m_end 및 start ▲ n_end 및 X[start] = Y[start] start : = start + 1 triming off 시작 시 m_end n_end n_end = 시작 시 일치 항목을 잘라냅니다.n_end : =n_end - 1C = 어레이(start-1..)m_end, start-1..n_end)는 i := start..에 대해 변경된 항목만 루프합니다.j:= 시작의 m_end..n_end 알고리즘은 이전과 같이 계속됩니다.
최적의 시나리오에서는 변경이 없는 시퀀스에서 이 최적화를 통해 C 매트릭스가 필요하지 않습니다.최악의 경우 시퀀스의 첫 번째 항목과 마지막 항목을 변경하는 경우 두 가지 추가 비교만 수행됩니다.
비교 시간 단축
순진한 알고리즘에 걸리는 대부분의 시간은 시퀀스 내의 항목 간 비교에 소비됩니다.소스 코드와 같은 텍스트 시퀀스의 경우 행을 단일 문자가 아닌 시퀀스 요소로 볼 수 있습니다.이는 알고리즘의 각 단계에 대해 비교적 긴 문자열을 비교하는 것을 의미합니다.두 가지 최적화를 통해 이러한 비교에 소요되는 시간을 줄일 수 있습니다.
문자열을 해시로 축소
해시 함수 또는 체크섬을 사용하여 시퀀스 내의 문자열 크기를 줄일 수 있습니다.즉, 평균 행 길이가 60자 이상인 소스 코드의 경우 해당 행의 해시 또는 체크섬 길이는 8~40자밖에 되지 않을 수 있습니다.또한 해시 및 체크섬의 랜덤화된 특성은 소스 코드 행이 처음에 거의 변경되지 않기 때문에 비교가 더 빨리 단락됨을 보장할 수 있습니다.
이 최적화에는 3가지 주요 단점이 있습니다.먼저 두 시퀀스의 해시를 미리 계산하기 위해 시간이 필요합니다.둘째, 새로운 해시 시퀀스에 추가 메모리를 할당해야 합니다.다만, 여기서 사용되고 있는 순진한 알고리즘에 비해, 이러한 양쪽의 단점은 비교적 미미합니다.
세 번째 단점은 충돌이다.체크섬 또는 해시가 고유하다고 보장되지 않기 때문에 두 개의 다른 항목이 동일한 해시로 축소될 가능성은 거의 없습니다.이는 소스 코드에서는 거의 발생하지 않지만 가능합니다.따라서 암호화 해시는 단순한 체크섬보다 엔트로피가 훨씬 크기 때문에 이 최적화에 훨씬 적합합니다.단, 작은 시퀀스 길이에 대한 암호화 해시의 설정 및 계산 요건이 필요하지 않을 수 있습니다.
필요한 공간을 줄이다
LCS의 길이만 필요한 경우 매트릭스를 쉽게 (,m ) \ 2 times \ ,m ) 、 \ style \ , ) + \ style \min m , ) ( smarter )로 줄일 수 있습니다.[8]Hirschberg의 알고리즘은 동일한 2차 시간 및 선형 공간 [9]경계에서 최적의 시퀀스 자체를 구성할 수 있도록 합니다.
한층 더 최적화된 알고리즘
제시된 동적 프로그래밍 방식보다 더 빠르게 실행되는 여러 알고리즘이 있습니다.그 중 하나는 Hunt-Szymanski 알고리즘입니다.이 은 보통 O ( ( + ) log () \ O ( ( ( + r ) \( n ) ) ( time ( > \ n > m )。 r은 두 시퀀스 [10]간의 일치 횟수입니다.알파벳 크기가 제한된 문제의 경우, Method of Four Russian을 사용하여 동적 프로그래밍 알고리즘의 실행 시간을 로그 계수로 [11]줄일 수 있습니다.
랜덤 문자열에서의 동작
Chvátal & Sankoff(1975[12] 에서 시작하여, 연구자들은 두 개의 주어진 문자열을 동일한 알파벳에서 무작위로 추출할 때 가장 긴 공통 연속 길이의 동작을 조사했다.알파벳 크기가 일정할 경우 LCS의 예상 길이는 두 문자열의 길이에 비례하며 비례 상수는 (알파벳 크기에 따라) Chvatal-Sankoff 상수로 알려져 있습니다.정확한 값은 알 수 없지만 값의 상한과 하한이 [13]입증되었으며 알파벳 [14]크기의 제곱근에 반비례하여 자라는 것으로 알려져 있습니다.가장 긴 공통 수열 문제의 단순화된 수학적 모델은 트레이시-위돔 [15]분포에 의해 제어되는 것으로 나타났다.
「 」를 참조해 주세요.
레퍼런스
- ^ David Maier (1978). "The Complexity of Some Problems on Subsequences and Supersequences". J. ACM. ACM Press. 25 (2): 322–336. doi:10.1145/322063.322075. S2CID 16120634.
- ^ Wagner, Robert; Fischer, Michael (January 1974). "The string-to-string correction problem". Journal of the ACM. 21 (1): 168–173. CiteSeerX 10.1.1.367.5281. doi:10.1145/321796.321811. S2CID 13381535. Retrieved 2018-05-03.
- ^ a b L. Bergroth and H. Hakonen and T. Raita (2000). "A Survey of Longest Common Subsequence Algorithms". SPIRE. IEEE Computer Society: 39–48. doi:10.1109/SPIRE.2000.878178. ISBN 0-7695-0746-8. S2CID 10375334.
- ^ Ronald I. Greenberg (2003-08-06). "Bounds on the Number of Longest Common Subsequences". arXiv:cs.DM/0301030.
- ^ Xia, Xuhua (2007). Bioinformatics and the Cell: Modern Computational Approaches in Genomics, Proteomics and Transcriptomics. New York: Springer. p. 24. ISBN 978-0-387-71336-6.
- ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001). "15.4". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 350–355. ISBN 0-262-53196-8.
{{cite book}}
: CS1 maint: 여러 이름: 작성자 목록(링크) - ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. "Dynamic Programming". Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. p. 394. ISBN 0-262-03384-4.
- ^ Binette, Olivier (2022-01-23), ⚡ StringCompare: Efficient String Comparison Functions, retrieved 2022-01-24
- ^ Hirschberg, D. S. (1975). "A linear space algorithm for computing maximal common subsequences". Communications of the ACM. 18 (6): 341–343. doi:10.1145/360825.360861. S2CID 207694727.
- ^ Apostolico, Alberto; Galil, Zvi (1997-05-29). Pattern Matching Algorithms. ISBN 9780195354348.
- ^ 를 클릭합니다Masek, William J.; Paterson, Michael S. (1980), "A faster algorithm computing string edit distances", Journal of Computer and System Sciences, 20 (1): 18–31, doi:10.1016/0022-0000(80)90002-1, MR 0566639.
- ^ 를 클릭합니다Chvatal, Václáv; Sankoff, David (1975), "Longest common subsequences of two random sequences", Journal of Applied Probability, 12 (2): 306–315, doi:10.2307/3212444, JSTOR 3212444, MR 0405531.
- ^ 를 클릭합니다Lueker, George S. (2009), "Improved bounds on the average length of longest common subsequences", Journal of the ACM, 56 (3), A17, doi:10.1145/1516512.1516519, MR 2536132, S2CID 7232681.
- ^ 를 클릭합니다Kiwi, Marcos; Loebl, Martin; Matoušek, Jiří (2005), "Expected length of the longest common subsequence for large alphabets", Advances in Mathematics, 197 (2): 480–498, arXiv:math/0308234, doi:10.1016/j.aim.2004.10.012, MR 2173842.
- ^ 를 클릭합니다Majumdar, Satya N.; Nechaev, Sergei (2005), "Exact asymptotic results for the Bernoulli matching model of sequence alignment", 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.
외부 링크