최장 공통 부분 수열

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

두 개의 수열에 대한 해

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

두 번째 속성

두 수열 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ₙ,Yₘ) = LCS(Xₙ, Yₘ₋₁).
두 번째 경우: LCS가 G로 끝나지 않는 경우

이 경우 위와 같은 이유로 수열 X에서 G를 제거하여도 손실이 일어나지 않는다. 즉 이렇게 쓸 수 있다.
LCS(Xₙ,Yₘ) = LCS(Xₙ₋₁, Yₘ).
어떤 경우에서든지 우리가 찾는 LCS는 LCS(Xₙ, Yₘ₋₁)이거나 LCS(Xₙ₋₁, Yₘ)이다. 이 두 LCS는 둘다 X와 Y의 공통 부분수열이다. LCS(X,Y)는 최장이다. 따라서 그 값은 LCS(Xₙ, Yₘ₋₁)와 LCS(Xₙ₋₁, Yₘ)중의 최장 수열이다.

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에 존재해야 한다. 만약 그렇지 않다면 와  쌍에서 무엇이 가장 큰 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 ""
    else if  X[i] = Y[j]
        return backtrack(C, X, Y, i-1, j-1) + X[i]
    else
        if C[i,j-1] > C[i-1,j]
            return backtrack(C, X, Y, i, j-1)
        else
            return backtrack(C, X, Y, i-1, j)

모든 LCS 읽어들이기

와 가 같은 길이의 결과를 반환한다면, 결과적으로 나오는 부분수열을 둘 다에서 읽어들인다. 이것은 이 함수에 의해 하나의 집합으로서 반환된다. 두 문자열이 비슷하면 거의 모든 단계에서 가지를 뻗어 갈 수 있게 되므로 이 함수는 다항함수가 아님에 유의하라.
function backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i = 0 or j = 0
        return {""}
    else if X[i] = Y[j]
        return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)}
    else
        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

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 ""

코드 최적화

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

문제의 집합을 축소하기

원래의 알고리즘의 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의 길이만을 필요로 한다면, 행렬은 로 쉽게 줄여지거나, 더 똑똑한 방법으로는 로 줄여질 수 있다. 왜냐하면 동적 계획법은 해열의 현재와 이전 열만을 필요로 하기 때문이다. Hirschberg의 알고리즘은 동일한 이차함수적인 시간과 선형 공간 제한 안에서 최적의 수열을 만들어 내도록 해준다.