최장 공통 부분 수열

최장 공통 부분수열 문제는 LCS라고도 불린다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다.(종종 단 두 개중 하나가 되기도 한다.) 컴퓨터 과학에서 고전으로 통하는 문제이며, diff 유틸리티의 근간이 되며, 생물정보학에서도 많이 응용되고 있다.

이 문제는 연속되어 있는 공통 문자열을 찾는 최장 공통 부분문자열(longest common substring) 문제와 혼동해서는 안 된다.

복잡도

이 문제는 임의의 수의 수열의 경우 NP-난해의 복잡도를 갖는다^[1]. 그러나 주어진 수열의 개수가 일정할 때 이 문제는 동적 계획법에 의해 다항 시간 안에 풀린다. 각각의 길이가 $n_{1},\dots ,n_{N}$ 인 $N$ 개의 수열이 주어졌다고 하자. 무식하게 해를 찾는 방법은, 모든 각 수열의 모든 가능한 부분수열을 전부 하나씩 구해 비교해 보는 것이며, 이때 각각의 부분수열은 남은 수열의 길이에 선형적으로 비례하는 시간동안 연산된다. 이 때의 시간 복잡도는 다음과 같다.

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

두 수열의 n 과 m원소에서, 동적 계획법에 의한 실행 시간은 O(n × m)이다. 임의의 입력 수열에 대해 동적 계획법에 의한 실행 시간은 다음과 같다.

\Theta \left(N\prod _{k=1}^{N}n_{k}\right)

복잡도를 더 낮출 수 있는 방법도 있으며^[2], 이 방법의 복잡도는 최장 공통 수열의 길이, 수열을 이루는 알파벳의 크기 등에 좌우된다.

LCS는 항상 유일해야 하는 것은 아님에 유의해야 한다. 예를 들어, "ABC"와 "ACB"의 LCS는 "AB"와 "AC" 둘 다이다. 즉 LCS 문제는 종종 최대의 길이를 갖는 모든 공통의 부분수열을 찾아내는 것으로 정의된다. 이런 문제는 더 높은 복잡도를 갖는데, 이런 부분수열의 가짓수는 최악의 경우 단 두개의 입력 문자열에서도 지수적이기 때문이다.

두 개의 수열에 대한 해

LCS 문제는 최적의 부분구조를 가진다. 이 문제는 더 작은, "부분문제"로 쪼개질 수 있고, 이것은 반복해서 자명한 부분문제가 될 때까지 더 간단한 부분문제로 쪼개질 수 있다. LCS는 또한 겹치는 부분문제를 가진다. 더 높은 부분문제에 대한 풀이는 몇몇의 하위 부분문제의 풀이에 의존한다. "최적의 부분구조"와 "겹치는 부분문제"는 동적 프로그래밍이라는 가장 간단한 부분문제에서 출발하는 문제 풀이 기법으로 접근될 수 있다. 이 과정은 부분문제의 해답을 표에 저장하는 방식인 메모이제이션을 통하여 상위 단계의 부분문제에서 해답을 접근할 수 있도록 하는 과정을 필요로 한다. 이 방법은 다음과 같이 묘사된다. 두 수열 $X_{1\dots m}$ and $Y_{1\dots n}$ 이 주어졌을 때, 주어진 두 수열의 최장 공통 부분수열(longest common subsequence)은 다음과 같이 표현된다.

접두사

부분문제는 수열이 짧아질 수록 간단해진다. 짧은 수열은 접두사라는 용어로 간단히 묘사된다. 어떤 수열의 접두사는 말단이 잘려나간 수열이다. S를 수열 (AGCA)라 둔다. 그러면 S의 접두사는 수열 (AG)이다. 접두사는 그 수열의 이름과 그 접두사가 포함하는 문자의 수로 정의된다.^[3] 따라서 접두사 (AG)는 S₂로 명명된다. S의 가능한 접두사들은

S₁ = (A)

S₂ = (AG)

S₃ = (AGC)

S₄ = (AGCA)

이다.

임의의 두 수열 X와 Y에서, LCS문제의 해법, 즉 최장 공통 부분 수열, LCS(X, Y)는 다음의 두 속성에 의존한다

첫 속성

두 수열이 같은 원소로 끝난다고 가정해보자. 그들의 LCS를 찾기 위해 마지막 원소를 지움으로써 수열의 길이를 줄이고, 짧아진 수열에 대한 LCS를 찾은 후 삭제한 원소를 붙여준다.

예를 들어, 같은 마지막 원소를 가진 두 수열 (BANANA)와 (ATANA)가 존재한다.

마지막 원소를 삭제한다. 이 과정을 공통된 마지막 원소가 존재하지 않을때까지 반복한다. 삭제된 수열은 ANA이다.

이제 연산해야 하는 수열은 다음과 같다. (BAN)와 (AT)

이 두 수열의 LCS는 (A)가 된다.

삭제했던 부분수열 (ANA)를 다시 결합시키면 (AANA)가 되고, 이것이 원 수열의 LCS가 된다.

접두사에서,

LCS(X_n, Y_m) = (LCS( X_n-1, Y_m-1), x_n)

반점은 원소 x_n가 이 수열에 붙게되는 부분을 말한다.

X_n 과 Y_m의 LCS를 계산하려면 더 짧은 수열 X_n-1 와 Y_m-1의 LCS를 계산해야 하는 점에 유의한다.

두 번째 속성

두 수열 X, Y가 같은 기호로 끝나지 않는다고 가정한다. 그러면 X와 Y의 LCS는 LCS(Xn,Ym-1)와 LCS(Xn-1,Ym)중 더 긴 수열이다. 이 특징을 이해하기 위해 다음 두 수열을 보도록 한다. 수열 X: ABCDEFG (n개의 원소) 수열 Y: BCDGK (m개의 원소) 이 두 수열의 LCS의 마지막 문자는 수열 X의 마지막 원소인 G로 끝나거나, 그렇지 않을것이다.

첫 번째 경우: LCS가 G로 끝나는 경우

이 경우 LCS는 K로 끝날 수 없다. 따라서 수열 Y에서 K를 제거하여도 손실이 일어나지 않는다. 만약 K가 LCS에 있었다면 마지막 문자였을것이기 때문이다. 따라서 이렇게 표기할 수 있다. LCS(X_n,Y_m) = LCS(X_n, Y_m-1).

두 번째 경우: LCS가 G로 끝나지 않는 경우
이 경우 위와 같은 이유로 수열 X에서 G를 제거하여도 손실이 일어나지 않는다. 즉 이렇게 쓸 수 있다. LCS(X_n,Y_m) = LCS(X_n-1, Y_m).

어떤 경우에서든지 우리가 찾는 LCS는 LCS(X_n, Y_m-1)이거나 LCS(X_n-1, Y_m)이다. 이 두 LCS는 둘다 X와 Y의 공통 부분수열이다. LCS(X,Y)는 최장이다. 따라서 그 값은 LCS(X_n, Y_m-1)와 LCS(X_n-1, Y_m)중의 최장 수열이다.

LCS 함수의 정의

두 수열을 다음과 같이 정의한다. X = (x₁, x₂...x_m), Y = (y₁, y₂...y_n). X의 접두사는 X_{1, 2,...m}이고, Y의 접두사는 Y_{1, 2,...n}이다. LCS(X_i, Y_j)를 접두사 X_i와 Y_j의 최장 공통 부분수열을 대표한다고 둔다. 이 수열의 집합은 다음과 같이 주어진다.

LCS\left(X_{i},Y_{j}\right)={\begin{cases}\emptyset &{\mbox{ if }}\ i=0{\mbox{ or }}j=0\\{\textrm {}}LCS\left(X_{i-1},Y_{j-1}\right)+1&{\mbox{ if }}x_{i}=y_{j}\\{\mbox{longest}}\left(LCS\left(X_{i},Y_{j-1}\right),LCS\left(X_{i-1},Y_{j}\right)\right)&{\mbox{ if }}x_{i}\neq y_{j}\\\end{cases}}

X_i 와 Y_j의 최장 공통 부분 수열을 찾기 위해서, 두 원소 x_i와 y_j를 비교한다. 만약 그들이 같다면 수열 LCS(X_i-1, Y_j-1)는 x_i원소로 확장된다. 만약 그들이 같지 않다면 두 수열 LCS(X_i, Y_j-1), 와 LCS(X_i-1, Y_j)중 더 긴 것이 얻어진다. (만약 그 둘이 길이가 같지만 동일하지 않다면 둘다 얻어진다.) 이 공식들에서 첨자가 1씩 감소했음을 주목하라. 이것은 첨자가 0이 되는 상황을 만들 수 있다. 수열의 원소들은 1부터 시작하는 것으로 정의되어 있으므로, 첨자가 0일 때 LCS는 비어있다는 필요조건을 추가할 필요가 있다.

예시

C = (AGCAT)와 R = (GAC)의 최장 공통 부분순열을 찾을것이다. LCS 함수는 "0번째"원소를 이용하기 때문에, 이 수열에서 비어있는 0번째 접두사를 정의하는 것이 편리하다. C₀ = Ø, 그리고 R₀ = Ø이다. 모든 접두사들은 C를 첫 번째 행에 위치하고, R을 첫 열에 위치시킨 표에 자리잡는다.

LCS Strings
	0	A	G	C	A	T
0	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø
A	Ø
C	Ø

이 표는 연산의 각 단계에서 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를 비교함으로써 결정된다. 그들은 동일하므로, 왼쪽 위의 (Ø)의 수열LCS(R₀, C₁)뒤에 붙어서 (ØG)가 되므로 결과적으로 (G)가 된다.

LCS(R₁, C₃)에서, G와 C는 일치하지 않는다. 그 위의 수열은 비어있고, 그 왼쪽의 것은 G라는 하나의 원소를 포함한다. 이들중 가장 긴 것을 선택하면 LCS(R₁, C₃)는 (G)가 된다. 화살표는 왼쪽을 가리키는데, 그것이 둘중 가장 긴 것이기 때문이다.

LCS(R₁, C₄)는 같은 방법으로 (G)이다.

LCS(R₁, C₅)또한 같은 방법으로 (G)이다.

"G" Row Completed
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\overset {\ \ \uparrow }{\leftarrow }}$ Ø	${\overset {\nwarrow }{\ }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)
A	Ø
C	Ø

LCS(R₂, C₁)에서, A는 A와 비교된다. 두 원소가 동일하므로, A는 Ø에 첨가되어 (A)가 된다.

LCS(R₂, C₂)에서, A와 G는 같지 않다. 따라서 두 수열LCS(R₁, C₂)와 LCS(R₂, C₁)중 가장 긴 것, 즉 (G)와 (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" Rows Completed
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\overset {\ \ \uparrow }{\leftarrow }}$ Ø	${\overset {\nwarrow }{\ }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)
A	Ø	${\overset {\nwarrow }{\ }}$ (A)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\overset {\nwarrow }{\ }}$ (GA)	${\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는 두 부분수열 (A)와 (C)를 포함하는 LCS(R₂, C₂)에 붙어 (AC) 와 (GC)가 된다.

LCS(R₃, C₄)에서, C와 A는 같지 않다. (AC)와 (GC)를 포함하는 LCS(R₃, C₃)와 (GA)를 포함하는 LCS(R₂, C₄)를 조합하면 총 세 개의 수열 (AC), (GC), 그리고 (GA)를 준다.

마지막으로, LCS(R₃, C₅)에 대해서, C와 T는 일치하지 않는다. 결과적으로 LCS(R₃, C₅) 또한 세 수열 (AC), (GC), 그리고 (GA)를 갖는다.

Completed LCS Table
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\overset {\ \ \uparrow }{\leftarrow }}$ Ø	${\overset {\nwarrow }{\ }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)
A	Ø	${\overset {\nwarrow }{\ }}$ (A)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\overset {\nwarrow }{\ }}$ (GA)	${\overset {\ }{\leftarrow }}$ (GA)
C	Ø	${\overset {\ \uparrow }{\ }}$ (A)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\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를 계산하는 데에는 현재 행의

Storing length, rather than sequences
	A	G	C	A	T
Ø	0	0	0	0	0
G	${\overset {\ \ \uparrow }{\leftarrow }}$ 0	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1
A	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ }{\leftarrow }}$ 2
C	${\overset {\ \uparrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2

실제 부분수열들은 표의 마지막 셀로부터 시작하여 화살표들을 거슬러 "역추적"함으로써 추론할 수 있다. 길이가 줄어들 때, 각 수열들은 반드시 공통 원소를 가진다. 두 화살표가 한 셀 안에서 있으면 여러 경로가 가능하다. 아래는 길이가 감소하는 셀에 대해 색이 칠해진 수들이 나타난 분석 과정을 나타낸 표이다. 굵은 숫자는 (GA) 수열을 찾아내는 경로이다.^[4]

Traceback example
	A	G	C	A	T
Ø	0	0	0	0	0
G	${\overset {\ \ \uparrow }{\leftarrow }}$ 0	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1
A	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ }{\leftarrow }}$ 2
C	${\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}$ 에서, shortest common supersequence의 길이는 다음의 식으로 LCS의 길이와 관련되어 있다.^[2]

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

삽입과 삭제만 가능하고, 치환이 불가능한, 또는 치환에 대한 비용이 삽입이나 삭제에 대한 값의 2배인 경우의 edit distance는

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

이다.

동적 계획법을 위한 풀이의 코드

LCS의 길이 연산

아래의 함수는 수열 X[1..m] 와 Y[1..n]를 입력받아 모든 1 ≤ i ≤ m 와 1 ≤ j ≤ n에 대해 X[1..i] 와 Y[1..j] 사이의 값에 대해 LCS를 연산하고, C[i,j]에 저장한다. C[m,n]는 X and Y에 대한 LCS 값을 가지게 된다.

function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

대체적으로, 메모이제이션 또한 사용될 수 있다.

하나의 LCS 읽어들이기

다음의 함수는 C의 표를 연산할 때 백트래킹을 이용한다. 만약 접두사의 마지막 문자들이 같다면, 그들은 반드시 한 LCS에 존재해야 한다. 만약 그렇지 않다면 $x_{i}$ 와 $y_{j}$ 쌍에서 무엇이 가장 큰 LCS를 갖는지를 판단하고 같은 선택을 다시 한다. 만약 그들이 같은 길이를 갖는다면 하나를 선택하면 된다. 함수를 i=m와 j=n이라 호출한다.

function backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i = 0 or j = 0
        return ""
    if  X[i] = Y[j]
        return backtrack(C, X, Y, i-1, j-1) + X[i]
    if C[i,j-1] > C[i-1,j]
        return backtrack(C, X, Y, i, j-1)
    return backtrack(C, X, Y, i-1, j)

모든 LCS 읽어들이기

$x_{i}$ 와 $y_{j}$ 가 같은 길이의 결과를 반환한다면, 결과적으로 나오는 부분수열을 둘 다에서 읽어들인다. 이것은 이 함수에 의해 하나의 집합으로서 반환된다. 두 문자열이 비슷하면 거의 모든 단계에서 가지를 뻗어 갈 수 있게 되므로 이 함수는 다항함수가 아님에 유의하라.

function backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i = 0 or j = 0
        return {""}
    if X[i] = Y[j]
        return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)}
    R := {}
    if C[i,j-1] ≥ C[i-1,j]
        R := R ∪ backtrackAll(C, X, Y, i, j-1)
    if C[i-1,j] ≥ C[i,j-1]
        R := R ∪ backtrackAll(C, X, Y, i-1, j)
    return R

diff 출력하기

이 함수는 C 행렬을 백트래킹하여 두 수열간의 diff를 출력한다. 아래의 코드에서, 당신이 ≥와 <를 >와 ≤로 바꾸면 다른 결과를 얻게 됨에 주목하여야 한다.

function printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i >= 0 and j >= 0 and X[i] = Y[j]
        printDiff(C, X, Y, i-1, j-1)
        print "  " + X[i]
    else if j > 0 and(i = 0 or C[i,j-1] ≥ C[i-1,j])
        printDiff(C, X, Y, i, j-1)
        print "+ " + Y[j]
    else if i > 0 and(j = 0 or C[i,j-1] < C[i-1,j])
        printDiff(C, X, Y, i-1, j)
        print "- " + X[i]
    else
        print ""

예시

$X$ 를 “XMJYAUZ”라 두고, $Y$ 를 “MZJAWXU”라고 둔다. $X$ 와 $Y$ 간의 LCS는 “MJAU”이다. 아래의 표 C는 함수LCSLength에 의해 생성되는데, 이것은 $X$ 와 $Y$ 각각의 접두사 사이의 LCS의 길이를 나타내고 있다. $i$ 번째 행과 $j$ 번째 열은 $X_{1..i}$ 와 $Y_{1..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

밑줄 쳐진 숫자들은 LCS를 읽어 나갈때 오른쪽 아래에서 왼쪽 위로 백트래킹 함수가 연산하는 경로를 나타낸다. $X$ 와 $Y$ 의 현재 기호가 같다면그들은 LCS의 일부로, 왼쪽 위로 이동하면 된다. 그렇지 않은 경우 우리는 위와 왼쪽 중 더 큰 수를 포함한 셀로 이동한다. 이것은 $X_{1..i-1}$ 와 $Y_{1..j}$ 사이, 또는 $X_{1..i}$ 와 $Y_{1..j-1}$ 사이의 LCS를 구하는 것과 대응된다.

코드 최적화

실생활에서 적용할 수 있게 하기 위해서 알고리즘을 최적화 시키는 방법이 여러 가지 있다.

문제의 집합을 축소하기

원래의 알고리즘의 C 행렬은 수열의 길이에 대해 제곱으로 증가한다. 두 100-길이의 수열에서 10,000-길이의 행렬이 필요하고, 10,000개의 비교가 이루어져야 한다. 대부분의 실제 세계의 사례에서, 특히 소스 코드의 diff와 패치들에서, 파일의 시작과 끝은 거의 바뀌지 않고, 그리고 그 둘이 동시에 변하는 것은 거의 전혀 일어나지 않는다. 만약 단 몇개의 항목만이 수열의 중간에서 변했다면 시작과 끝은 제거되어도 된다. 이것은 행렬의 메모리 필요량을 줄여줄 뿐 아니라, 비교되어야 할 개수도 줄여준다.

function LCS(X[1..m], Y[1..n])
    start := 1
    m_end := m
    n_end := n
    trim off the matching items at the beginning
    while start ≤ m_end and start ≤ n_end and X[start] = Y[start]
        start := start + 1
    trim off the matching items at the end
    while start ≤ m_end and start ≤ n_end and X[m_end] = Y[n_end]
        m_end := m_end - 1
        n_end := n_end - 1
    C = array(start-1..m_end, start-1..n_end)
    only loop over the items that have changed
    for i := start..m_end
        for j := start..n_end
            the algorithm continues as before ...

최적의 경우, 아무것도 바뀌지 않은 수열에서, 이 최적화는 C 행렬의 필요성 또한 완전히 없애준다. 최악의 경우, 맨 앞과 맨 뒤 항목이 바뀐 경우, 비교 항목이 2개 추가되게 된다.

비교 시간을 줄이기

원 알고리즘에서의 시간 소요는 수열의 항목을 비교할 때 소모된다. 소스 코드와 같은 문자열에서, 당신은 각각의 문자 대신 수열 원소를 라인으로 보고 싶다. 이것은 또한 알고리즘의 각 단계에서 상대적으로 긴 문자열간의 비교를 의미할 수 있다. 이 비교 시간 소모를 줄이기 위해 두 가지 최적화가 가능하다.

문자열을 해쉬로 줄이기

해쉬함수 또는 체크섬은 수열의 문자열의 크기를 줄이기 위해 사용될 수 있다. 즉, 평균 라인 수가 60 또는 그 이상의 길이의 소스 코드에서, 해쉬나 체크섬은 단 8에서 40 문자 정도의 길이이다. 추가적으로, 해쉬와 체크섬의 랜덤화된 특성은 비교가 회로를 더 빠르게 돌 것을 보장해 주는데, 이는 소스 코드의 라인들은 시작 부분에서 거의 변하지 않을 것이기 때문이다.

이 최적화에는 세 가지 문제점이 존재한다. 첫째, 두 수열의 연산 전, 해쉬를 연산하기 위한 시간이 소모된다. 둘째, 새로운 해쉬화된 수열을 위해 추가적인 메모리가 필요하다. 그러나 원 알고리즘에 비하면 두 단점은 비교적 작은 편이다.

세 번째 단점은 해쉬 충돌이다. 체크섬과 해쉬는 유일함이 보장되지 않았으므로, 다른 두개의 항목이 같은 해쉬로 축약될 아주 작은 가능성이 존재한다. 이것은 소스 코드에서 일어나기 쉽지 않지만, 가능하기는 하다. 암호학적인 해쉬는 이런 최적화를 위해 매우 적합할 것이다. 왜냐하면 그것의 엔트로피는 단순 체크섬에 비해 매우 클 것이기 때문이다. 그러나 암호학적인 해쉬의 세팅과 연산적 요구사항은 작은 수열을 위해서는 적당하지 않을 것이다.

요구 공간을 줄이기

만약 LCS의 길이만을 필요로 한다면, 행렬은 $2\times \min(n,m)$ 로 쉽게 줄여지거나, 더 똑똑한 방법으로는 $\min(m,n)+1$ 로 줄여질 수 있다. 왜냐하면 동적 계획법은 해열의 현재와 이전 열만을 필요로 하기 때문이다. Hirschberg의 알고리즘은 동일한 이차함수적인 시간과 선형 공간 제한 안에서 최적의 수열을 만들어 내도록 해준다.^[5]

같이 보기

최장 증가 부분 수열

참조

↑ David Maier (1978). “The Complexity of Some Problems on Subsequences and Supersequences”. 《J. ACM》 (New York, NY, USA: ACM 프레스) 25 (2): 322–336. doi:10.1145/322063.322075.
↑ ^가 ^나 L. Bergroth and H. Hakonen and T. Raita (2000). “A Survey of Longest Common Subsequence Algorithms”. 《SPIRE》 (로스 알라미토스, CA, USA: IEEE Computer Society) 00: 39–48. doi:10.1109/SPIRE.2000.878178. ISBN 0-7695-0746-8.
↑ Xia, Xuhua (2007). 《Bioinformatics and the Cell: Modern Computational Approaches in Genomics, Proteomics and Transcriptomics》. New York: Springer. 24쪽. ISBN 0-387-71336-0.
↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001). 〈15.4〉. 《Introduction to Algorithms》 2판. MIT Press and McGraw-Hill. 350–355쪽. ISBN 0-262-53196-8. CS1 관리 - 여러 이름 (링크)
↑ 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.

[1] David Maier (1978). “The Complexity of Some Problems on Subsequences and Supersequences”. 《J. ACM》 (New York, NY, USA: ACM 프레스) 25 (2): 322–336. doi:10.1145/322063.322075.

[BHR00-2] 가 ^나 L. Bergroth and H. Hakonen and T. Raita (2000). “A Survey of Longest Common Subsequence Algorithms”. 《SPIRE》 (로스 알라미토스, CA, USA: IEEE Computer Society) 00: 39–48. doi:10.1109/SPIRE.2000.878178. ISBN 0-7695-0746-8.

[3] Xia, Xuhua (2007). 《Bioinformatics and the Cell: Modern Computational Approaches in Genomics, Proteomics and Transcriptomics》. New York: Springer. 24쪽. ISBN 0-387-71336-0.

[4] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001). 〈15.4〉. 《Introduction to Algorithms》 2판. MIT Press and McGraw-Hill. 350–355쪽. ISBN 0-262-53196-8. CS1 관리 - 여러 이름 (링크)

[5] 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.

[1]

[2]

[3]

[4]

[5]

		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

		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

		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