15.4 Longest Common Subsequence (알고리즘 개론, Introduction to Algorithms)

15.4 Longest Common Subsequence
생물 프로그램은 종종 두 개 (또는 그 이상) 다른 유기체의 DNA를 비교할 필요가 있다. DNA 한 가닥은 bases라고 불려지는 분자의 한 string으로 구성되어 있다. 거기에서 가능한 bases들은 adenine, guanine, cytosine, and thymine. 이다. 이러한 bases들각각은 그것들의 초기 문자로 나타내는데, 우리는 DNA의 한 strand를 유한한 집합 {A,C,G,T}에 대한 한 string으로서 표현할수 있다 (string의 정의를 위해 Appendix C 참조.) 예를들어, 한 유기체의 DNA는 S1 = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA, 그리고 다른 유기체의 DNA는 아마도 S2 = GTCGTTCGGAATGCCGTTGCTCTGTAAA 일지도 모른다. DNA의 두 strands를 비교하는 이유는 그 두 개의 strands가 얼마나 유사한지를 결정하기 위해서이다, 왜냐하면 그 두 유기체가 얼마나 관련있는지에 대한 척도이기 때문이다. 우리는 많은 다른 방식으로 유사성을 정의할 수 있다. 예를들어, 만약 한 strand가 다른 것의 substring이라면 우리는 두 개의 DNA strands가 비슷하다고 말할 수 있다. (Chapter 32는 이 문제를 해결하는 알고리즘을 본다.) 우리의 예제에서, S1가 S2는 둘 다 다른 것의 substring은 아니다. 대안적으로, 우리는 만약 하나를 다른 것으로 바꾸는데 필요한 변화의 개수가 작다면 두 strands가 비슷하다고 말할 수 있다 (문제 15-5가 이 개념을 본다.) 그러나 strands S1과 S2의 유사성을 측정하는 또 다른 방법은 세 번째 strand S3를 찾아서 되는데, 거기에서 S3에 있는 bases는 S1과 S2의 각각에 나타난다; 이러한 bases는 같은 순서로 나타나야만 하지만, 필수적으로 연속적일 필요는 없다. strand S3가 더 길수록,우리는 S1과 S2가 더 유사하다고 발견할 수 있다. 우리의 예제에서, 가장 긴 strand S3는 GTCGTCGGAAGCCGGCCGAA 이다.

우리는 이 마지막 유사성의 개념을 Longest-Common-subsequence 문제로 공식화한다. 한 주어진 수열의 부분수열은 zero 또는 더 많은 elements들이 있는 주어진수열이다. 공식적으로, 한 수열 X = <x_1, x_2, ..., x_m>, 또 다른 수열 Z = <z_1, z_2, ...,z_k>는 X의 부분수열인데, 만약 엄격히X의 인덱스들의 증가하는 수열 <i_1, i_2, ... ,i_k>가 존재하면이다, 그리고 모든 j = 1, 2,...., k 이고, 우리는 x_i_j = z_j를 가진다. 예를들어, Z = <B, C, D, B>가 X = <A, B, C, B, D, A, B>의 부분 수열이다, 인덱스 수열 2,3,5,7에 대응되어.

두 개의 수열 X와 Y가 주어진다면, 우리는 수열 Z는 X와 Y의 공통 부분 수열이라고 말한다, 만약 Z가 X와 Y 둘 다의 부분 수열이라면. X = <A, B,C, B,D, A, B> Y = <B, D, C, A, B, A>라면, 수열 <B, C, A>는 X와 Y 둘 다의 공통 부분 수열이다. 그 수열 <B,C,A>는 X와 Y 둘 다의 가장 긴 공통 부분 수열은(LCS) 아니다. 그것이 길이가 3을 가졌기 때문에고, X와 Y 둘 다에 또한 공통된 수열 <B, C, B, A>가 길이 4를 가지기 때문이다. 그 수열 <B,C, B, A>는 X와 Y의 LCS이다, <B, D, A, B>가 수열이듯이, X와 Y가 길이가 5보다 더큰 공통 부분수열을 가지고 있지 않기 때문이다.

longest-common-subsequence problem에서, 우리는 두 개의 수열 X와 Y가 주어지고, X와 Y의 최대 길이의 공통 부분 수열을 찾길 원한다. 이 섹션은  DP를 사용하여 LCS 문제를 어떻게 효율적으로 푸는지를 보여준다.

Step1 : Chacracterizing a longest common subsequence
LCS문제를 해결하는 brute-force 접근법에서, 우리는 X의 모든 부분수열들을 열거하고 각 subsequences를 그것이 Y의 subsequence인지 보기위해 체크하고, 우리가 찾은 가장 긴 부분 수열을 추적한다. X의 각 부분 수열은 X의 인덱스 <1,2,...m>의 부분집합과 일치한다. X가 2^m 부분 수열을가지고 있기 때문에, 이 접근법은 exponentail time을 ㅇ구한다, 긴 수열에 대해서 비실용적으로 만들어서.

그러나, LCS 문제는 최적의 substructure 특징을 갖는다, 다음의 정리가 보여주듯이. 우리가 보게 되듯이, 부분 문제들의 자연적인 계층들은 두 개의 입력 수열의 "prefixes"의 쌍과 일치한다. 정확히 하기 위해, 수열 X = <x_1,...,, x_,>이 주어진다면, 우리는 i = 0,1,...,m에 대해 X의 i번째 prefix를 X_i <x1, x2, ..., xi> 라고 정의한다. 예를들어, 만약 X = <A, B, C, B, D, A, B>라면, 그러고나서 X4 = <A,B,C,B> 이고 X0는 빈 수열이다.

Theorem 15.1 (Optimal substructure of an LCS)
X = x1, ..., x_m이고, Y = y1,...,y_n인 수열이라고 하자, Z = z1, ..., z_k가 X와 Y의 LCS라고 하자.

1. x_m과 y_n이 같다면, 그러면 z_k = x_m = y_n이고 Z_k-1은 X_m-1 과 y_n-1의 LCS이다.
2. x_m != y_n 이라면, z_k != z_m은 Z가 X_m-1과 Y의 LCS라는 것을 암시한다.
3. x_m != y_n 이라면, 그러면 z_k != y_n은 Z는 X와 Y_n-1의 LCS라는 것을 암시한다.

Proof (1) 만약 z_k != x_m이라면, 그러면 우리는 x_m = y_n을 Z에 더할 수 있다, 길이가 k + 1인 X와 Y의 공통 부분수열을 얻기 위해서. 그리고 이것은 Z가 X와 Y의 가장 긴 공통 부분 수열이라는 가정과 모순된다. 따라서, 우리는 z_k = x_m = y_n을 가져야 한다. 이제 그 prefix Z_k-1은 X_m-1과 Y_n-1의 길이가 (k-1)인 공통 부분수열이다. 우리는 그것이 LCS라는 것을 보여주기를 원한다. 모순의 목적을 위해서 x_m-1과  y_n-1의 k - 1보다 더 큰 공통 부분 수열 W가 있다고 가정하자. 그러고나서 x_m = y_n을 W에 더하는 것은 길이가 k보다 더 큰 X와 Y의 공통 부분 수열을 만들어내고, 이것은 모순이다.

(2) z_k !=x_m이라면, 그러면 Z는 x_m-1과 Y의 공통 부분수열이다. 만약 X_m-1과 Y의 k보다 더 큰 공통 부분 수열이 있다고 한다면, 그러면 W는 x_m과 Y의 공통 부분수열일 것이고, 이것은 Z가 X와 Y의 LCS라는 가정과 모순된다.

(3) 이 증명은 (2)와 대칭이다.

정리 15.1이 LCS를 특징짓는 방식은 우리에게 두 수열의 한 LCS가 그것 내에서 두 개의 수열의 prefixes의 LCS를 포함한다는 것을말해준다. 따라서, LCS문제는optimal-substructure property를 가진다. 재귀 방법은 또한 overlapping-subproblems를 가진다, 잠시뒤에 우리가 보게 되듯이.

Step 2: A recursive solution

정리 15.1은 우리가 X와 Y의 LCS를 찾을 때 한 개 또는 두 개의 부분문제들 중 하나를 검사해야 한다는 것을 암시한다. 만약 x_m과 y_n이 같다면, 우리는 X_m-1과 Y_n-1의 LCS를 찾아야만 한다. x_m = y_n을 이 LCS에 더하는 것은 X와 Y의 LCS를 만들어낸다. 만약 x_m != y_n이라면, 그러면 우리는 두 개의 부분 문제들을 풀어야 한다: X_m-1과 Y의 LCS 찾기와 X와 Y_n-1의 LCS 찾기.이러한 두 개의 LCS들 중 더 긴 것이 X와 Y의 LCS이다. 이러한 경우들이 모든 가능성을 소진하기 때문에, 우리는 optimal subproblem solutions중의 하나는 X와 Y의 LCS내에서 나타나야만 하는 것을 안다.

우리는 쉽게 LCS 문제에서 overlapping-subproblems property를 볼 수 있다. X와 Y의 LCS를 찾기위해서, 우리는 X와 Y_n-1 그리고 X_m-1과 Y의 LCS들을 찾을 필요가 있을지도 모른다. 그러나, 이러한 subproblems들 각각은 X_m-1과 Y_n-1의 LCS를 찾는 부분 문제이다. 많은 다른 부분문제들은 subsubproblems를 나눈다.

matrix-chain multiplication problem에서 처럼, LCS문제에대한 우리의 재귀 솔루션은 optimal solution의 값에 대한 재귀를 만드는 것을 포함한다. 우리가 수열 X_i와 Y_j의 LCS의 길이가 c[i, j]라고 정의하자. 만약 i = 0 or j = 0 둘 중 하나라면, 그 수열들 중 하나는 길이가 0을 갖고, 그래서 그 LCS는 길이가 0이다. LCS 문제의 optimal substructue는 재귀 함수를 준다



이 재귀 공식에서 그 문제의 한 조건이 어떤 subproblems를 우리가 고려할지를 제한하는 것을 관찰해라. x_i = y_j일 때, 우리는 X_j-1, Y_j-1의 LCS를 찾는 subproblem을 고려할 수 있고 고려해야 한다. 만약 그렇지 않다면, 우리는 대신에 X_i와 Y_j-1 그리고 X_i-1 과 Y_j의 LCS를 찾는 두 개의 subproblems를 고려한다. 우리가 조사한 이전의 DP 알고리즘에서 - rod cutting and matrix-chain multiplication - 우리는 문제에서 조건에 의해 subproblems를 배제했었다. LCS를 찾는 것은 그 문제에서 조건들을 기반으로 한 subproblems를 배제하는 유일한 DP 알고리즘이 아니다. 예를들어, edit-distance problem (see Problem 15-5)는 이 특징을 갖는다.

Step 3 : Computing the length of an LCS
방정식(15.9)를 기반으로, 우리는 쉽게 exponential-time의 재귀 알고리즘을 작성할 수 있다,  두 수열의 LCS의 길이를 연산하는. 그 LCS 문제는 오직 O(mn)의 별개의 subproblems를 가질 수 있기 때문에, 그러나, 우리는 solutions을 bottom up으로 연산하기 위해 DP를 사용할 수 있다.

Procedure LCS-LENGTH는 두 개의 수열 X = <x1, ... ,x_m> 그리고 Y = <y1, ..., y_n>을 입력으로 받는다. 그것은 한 테이블 c[0...,m,0..n]에 c[i,j]의 값을 저장하고, 그것은 row-major order에서 그 성분들을 연산한다. (즉, 그 procedure는 c의 첫 번째 행을 왼쪽에서 오른쪽으로채우고, 그러고나서 두 번째로 가고, 등등). 그 절차는 또한 table b[1..m,1..n[을 유지하는데, 우리가 optimal solution을 구성하는 것을 돕기위해서 이다. 직관적으로, b[i,j]는 c[i,j]를 연산할 때, 선택되는 optimal subproblem solution과 일치하는 table entry를 가리킨다. 그 절차는 b와 c 테이블을 반환한다: c[m,n]은 X와 Y의 LCS의 길이를 포함한다. 

LCS-LENGTH(X,Y)
1  m = X.length
2  n = Y.length
3  let b[1..m,1..n] and c[0..m,0..n] be new tables
4  for i = 1 to m
5        c[i,0] = 0
6  for j = 0 to n
7        c[0, j] = 0
8  for i = 1 to m
9        for j = 1 to n
10            if x_i == y_j
11                 c[i,j] = c[i-1,j-1] + 1
12                 b[i,j] = "North-west"
13            else if c[i-1, j] >= c[i, j-1]
14                 c[i,j] = c[i-1,j]
15                 b[i,j] = "North"
16            else c[i,j] = c[i, j-1]
17                 b[i,j] = "West"
18 return c and b

그림 15.8은 수열 X = <A, B, C, B, D, A, B>와 Y = <B, D, C, A, B, A>에서의 LCS-LENGTH에 의해 만들어진 테이블을 보여준다. 그 절차의 작동 시간은 O(mn)이다, 왜냐하면 각 table entry는 연산하기에 O(1) 시간이 걸리기 때문이다.

Step 4: Constructing an LCS
LCS-LENGTH에 의해 반환된 그 b 테이블은 우리가 빠르게 X와 Y의 LCS를 구성할 수 있게 한다. 우리는 간단히 b[m,n]에서 시작하고, 화살표를 따라서 그 테이블을 따라간다. entry b[i,j]에서 "North-west"를 만날 때 마다, x_i = y_j는 LCS-LENGTH가 발견한 LCS의 한 원소인 것을 암시한다. 이 방식으로, 우리는 역순으로 이 LCS의 원소들을 만난다. 다음의 재귀 절차는 X와 Y의 LCS를 적절히, forward 순서로 출력한다. 초기 호출은 PRINT-LCS(b, X, X.length, Y.length) 이다.

PRINT-LCS(b, X, i , j)
1 if i == 0 or j == 0
2       return
3 if b[i,j] == "North-west"
4       PRINT-LCS(b, X, i - 1, j - 1)
5       print x_i
6 else if b[i,j] == "North"
7      PRINT-LCS(b, X, i - 1, j)
8 else PRINT_LCS(b, X, i, j - 1)

그림 15.8에 있는 b 테이블에 대해, 이 절차는 BCBA를 출력한다. 그 절차는 O(m + n)의 시간이 걸린다. 그것은 적어도 각 재귀 호출에서 i와 j중의 하나가 줄어들기 때문이다.

Improving the code
너가 일단 한 알고리즘을 개발했다면, 너는 종종 너가 그것을 사용하는 시간 또는 공간을 개선시킬 수 있다는 것을 발견할 것이다. 몇 가지 변화들은 그 코드를 간단하게 할 수 있고, 상수 요소를 개선할 수 있지만, 그렇지 않다면 성능에서 asymptotic improvement를 만들어내지 않을 것이다. 다른 것들은 시간과 공간에서 상당한 asymptotic savings를 만들어낼 수 있다.

예를들어, LCS 알고리즘에서, 우리는 b 테이블을 전적으로 제거할 수 있다. C[i,j] entry는 오직 세 개의 다른 c 테이블 entries에 의존한다 : c[i-1, j -1], c[i-1, j], and c[i,j-1]. c[i,j]의 값이 주어진다면, 우리는 O(1) 시간에 이러한 세 개의 값 중 어떤 것이 c[i,j]를 연산하기 위해 사용되었는지를 결정할 수 있다, 테이블 b를 검사하는 것 없이. 따라서, 우리는 LCS를 PRINT-LCS와 유사한 절차를 사용해서 O(m + n) 시간에 재구성할 수 있다. 예제 15.4-2는 너에게 이 슈도코드를 주라고 요청한다.) 비록 우리는 O(mn) 공간을 이 방식으로 절약하지만, LCS를 연산하기 위해 그 보조 공간 요구사항은 asymptotically하게 줄어들지 않는다, 왜냐하면 우리는 어쨋든 c 테이블을 위해 O(mn) 공간이 필요하기 때문이다.

그러나, 우리는 LCS-LENGTH에 대한 asymptotic space requirements를 줄일 수 있다. 왜냐하면 그것은 오직 한 번에 c의 두 개의 행을 필요하기 때문이다. 연산되고 있는 행과, 그 이전 행. (사실, 예제 15.4-4는 너에게 보여달라고 요쳥하기 때문에, 우리는 LCS의 길이를 연산하기 위해 C의 한 행에 대해 그 이상의 공간을 사용할 수 있다.) 이 개선은 효과가 있다, 만약 우리가 LCS의 길이만 필요하다면; 만약 우리가 LCS의 원소들을 재구성할 필요가 있다면, 더 작은 테이블은 우리의 steps들을 다시 쫓기에 충분한 정보를 유지하지 못한다, O(m+n)시간에.