최장 공통 부분 수열

3. 두 개의 수열에 대한 해

LCS 문제는 최적 부분 구조를 갖는다. 즉, 문제를 더 작고 간단한 하위 문제로 분해할 수 있으며, 이는 다시 더 간단한 하위 문제로 분해될 수 있고, 결국 해답이 자명해진다. 특히 LCS는 중복되는 하위 문제를 가지는데, 상위 수준의 하위 문제에 대한 해답은 종종 하위 수준의 하위 문제에 대한 해답을 재사용한다. 이러한 두 가지 속성을 가진 문제는 동적 계획법 접근 방식에 적합하며, 여기서 하위 문제의 해답은 메모이제이션된다. 즉, 하위 문제의 해답이 재사용을 위해 저장된다.^[23]

두 수열 $X\_\{1\; \backslash dots\; m\}$과 $Y\_\{1\; \backslash dots\; n\}$이 주어졌을 때, LCS는 이 문제를 더 작은 부분 문제로 나누어 해결하고, 부분 문제의 해답을 표(메모이제이션)에 저장하여 상위 단계의 부분 문제에서 재사용하는 방식으로 구한다.

3. 1. 접두사

3. 2. LCS 함수의 정의

• 수열 X: ABCDEFG (n개의 원소)
• 수열 Y: BCDGK (m개의 원소)

3. 3. 예시

• 초기 설정:
• 빈 수열(Ø)은 비교 대상이 없으므로, 첫 번째 행과 열은 모두 Ø로 채워진다.
• G 비교:
• G는 A와 다르므로, (G, A)의 LCS는 Ø이다.
• G는 G와 같으므로, (G, AG)의 LCS는 (G)가 된다.
• G는 C, A, T와 다르므로, (G, AGC), (G, AGCA), (G, AGCAT)의 LCS는 모두 (G)이다.
• A 비교:
• A는 A와 같으므로, (GA, A)의 LCS는 (A)가 된다.
• A는 G와 다르므로, (GA, AG)의 LCS는 (A) 또는 (G)이다.
• A는 C와 다르므로, (GA, AGC)의 LCS는 (A) 또는 (G)이다.
• A는 A와 같으므로, (GA, AGCA)의 LCS는 (GA)가 된다.
• A는 T와 다르므로, (GA, AGCAT)의 LCS는 (GA)이다.
• C 비교:
• C는 A와 다르므로, (GAC, A)의 LCS는 (A)이다.
• C는 G와 다르므로, (GAC, AG)의 LCS는 (A) 또는 (G)이다.
• C는 C와 같으므로, (GAC, AGC)의 LCS는 (AC) 또는 (GC)이다.
• C는 A와 다르므로, (GAC, AGCA)의 LCS는 (AC), (GC), (GA)이다.
• C는 T와 다르므로, (GAC, AGCAT)의 LCS는 (AC), (GC), (GA)이다.

3. 4. 역추적 접근

4. 다른 문제들과의 연관성

두 문자열 \(X_{1 \dots m}\)과 \(Y_{1 \dots n}\)에서, 최단 공통 상위 수열의 길이는 다음 식으로 LCS의 길이와 관련되어 있다.^[22]

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

삽입과 삭제만 가능하고, 치환이 불가능하거나 치환 비용이 삽입이나 삭제 비용의 2배인 경우 편집 거리는 다음과 같다.

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

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

LCS의 길이를 계산하는 함수는 다음과 같다.^[7]

'''함수''' 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]

'''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)

'''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 := 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

'''함수''' 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)

        print "  " + X[i]

    '''그렇지 않고 만약''' j > 0 '''그리고''' (i = 0 '''또는''' C[i,j-1] ≥ C[i-1,j])

        printDiff(C, X, Y, i, j-1)

        print "+ " + Y[j]

    '''그렇지 않고 만약''' i > 0 '''그리고''' (j = 0 '''또는''' C[i,j-1] < C[i-1,j])

        printDiff(C, X, Y, i-1, j)

        print "- " + X[i]

    '''그렇지 않으면'''

        print ""

강조 표시된 숫자는 LCS를 읽어낼 때 함수 `backtrack`이 오른쪽 아래에서 왼쪽 위 구석으로 따라갈 경로를 보여준다. $X$와 $Y$의 현재 기호가 같으면 LCS의 일부이며 위와 왼쪽으로 이동한다 ('''굵게''' 표시됨). 그렇지 않으면 숫자가 더 높은 셀에 따라 위 또는 왼쪽으로 이동한다. 이는 $X\_\{1..i-1\}$와 $Y\_\{1..j\}$ 사이 또는 $X\_\{1..i\}$와 $Y\_\{1..j-1\}$ 사이의 LCS를 구하는 것에 해당한다.

6. 코드 최적화

실제 상황에 적용하기 위해 알고리즘을 최적화하는 방법은 여러 가지가 있다.

• 원래 알고리즘의 C 행렬 최적화:

• 비교 시간 소모 감소를 위한 최적화:

• 메모리 사용량 최적화:

• 기타 알고리즘
• Chowdhury와 Ramachandran은 최장 공통 부분 수열 길이를 찾기 위한 2차 시간, 선형 공간 알고리즘을 개발했으며^[10][9], 실제 실행 시 히르쉬버그 알고리즘보다 캐시 성능이 뛰어나 더 빠르게 실행된다.^[10]
• 헌트-시만스키 알고리즘(Hunt–Szymanski algorithm)은 일반적으로 $O((n\; +\; r)\backslash log(n))$ 시간 내에 실행된다($n\; >\; m$일 때). 여기서 $r$은 두 시퀀스 간의 일치하는 횟수이다.^[12]
• 제한된 알파벳 크기의 문제의 경우, 네 러시아인 방법(Method of Four Russians)을 사용하여 동적 프로그래밍 알고리즘의 실행 시간을 로그 팩터만큼 줄일 수 있다.^[13]

7. 무작위 문자열에서의 동작

Chvátal|츠바탈^영어과 Sankoff|산코프^영어 (1975)의 연구^[14]를 시작으로, 여러 연구자들이 동일한 알파벳에서 무작위로 추출된 두 문자열에서 최장 공통 부분 수열 길이의 동작을 조사했다. 알파벳 크기가 일정할 때 LCS의 예상 길이는 두 문자열 길이에 비례하며, 이 비례 상수(알파벳 크기에 따라 다름)는 Chvátal–Sankoff 상수로 알려져 있다. 정확한 값은 알려져 있지 않지만, 값에 대한 상한과 하한이 증명되었으며,^[15] 알파벳 크기의 제곱근에 반비례하여 증가한다는 것이 알려져 있다.^[16] 최장 공통 부분 수열 문제의 단순화된 수학적 모델은 Tracy–Widom 분포에 의해 제어되는 것으로 나타났다.^[17]

참조

_[1] 논문 The Complexity of Some Problems on Subsequences and Supersequences ACM Press
_[2] 논문 The string-to-string correction problem 1974-01
_[3] 간행물 A survey of longest common subsequence algorithms IEEE Computer Society 2000-09-07
_[4] arXiv Bounds on the Number of Longest Common Subsequences 2003-08-06
_[5] 서적 Bioinformatics and the Cell: Modern Computational Approaches in Genomics, Proteomics and Transcriptomics https://archive.org/[...] Springer
_[6] 서적 Introduction to Algorithms MIT Press and McGraw-Hill
_[7] 문서 Introduction to Algorithms
_[8] 논문 A linear space algorithm for computing maximal common subsequences
_[9] 논문 Cache-oblivious dynamic programming for bioinformatics https://ieeexplore.i[...] 2010-07
_[10] 서적 Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 2006-01
_[11] 논문 Cache-oblivious algorithms https://dl.acm.org/d[...] 2012-01
_[12] 웹사이트 Pattern Matching Algorithms https://books.google[...] Oxford University Press 1997-05-29
_[13] citation A faster algorithm computing string edit distances
_[14] citation Longest common subsequences of two random sequences
_[15] citation Improved bounds on the average length of longest common subsequences
_[16] citation Expected length of the longest common subsequence for large alphabets
_[17] citation Exact asymptotic results for the Bernoulli matching model of sequence alignment
_[18] 논문 A Survey of Longest Common Subsequence Algorithms IEEE Computer Society
_[19] arXiv Bounds on the Number of Longest Common Subsequences 2003-08-06
_[20] 서적 Bioinformatics and the Cell: Modern Computational Approaches in Genomics, Proteomics and Transcriptomics Springer
_[21] 저널
_[22] 저널
_[23] 서적 인용 Bioinformatics and the Cell: Modern Computational Approaches in Genomics, Proteomics and Transcriptomics https://archive.org/[...] Springer
_[24] 서적 인용 Introduction to Algorithms MIT Press and McGraw-Hill
_[25] 저널 인용 A linear space algorithm for computing maximal common subsequences