LCS·부분 수열·표와 복원

문서를 고친 뒤 이전 판과 무엇이 달라졌는지 보여 주는 비교 도구는, 두 판에서 바뀌지 않은 부분을 먼저 찾고 나머지를 지워진 곳과 추가된 곳으로 표시합니다. 바뀌지 않은 부분은 두 판에서 같은 순서로 나타나지만, 사이사이에 다른 내용이 끼어 있어 붙어 있지는 않습니다. 이렇게 두 순서열에서 순서를 지키며 공통으로 나타나는 가장 긴 부분을 찾는 문제를 최장 공통 부분 수열(longest common subsequence, LCS) 문제라고 합니다. 이 글에서는 동전 문제에서 익힌 동적 계획법을 두 입력에 적용해, 상태가 두 개의 수로 정해지는 2차원 표를 채우고 그 표에서 실제 답을 복원합니다.

부분 수열과 부분 문자열

문자열에서 몇 글자를 지우고 남은 글자들을 원래 순서대로 이은 것을 부분 수열(subsequence)이라고 합니다. ABC에서 B를 지운 AC는 ABC의 부분 수열입니다. 지운 글자 없이 연속으로 붙어 있는 구간은 부분 문자열(substring)이라고 하며, AC는 ABC의 부분 문자열이 아닙니다. 부분 수열에서 중요한 것은 순서입니다. 글자를 건너뛸 수는 있지만 순서를 바꿀 수는 없으므로 CA는 ABC의 부분 수열이 아닙니다.

두 문자열에 모두 부분 수열로 나타나는 문자열을 공통 부분 수열이라 하고, 그중 가장 긴 것이 LCS입니다. ABCBDAB와 BDCABA의 LCS는 길이 4이며 BCBA가 그 하나입니다. 길이가 같은 LCS가 여러 개일 수 있으므로, 보통 LCS의 길이는 하나로 정해지지만 LCS 자체는 그중 하나를 구합니다.

모든 경우를 따지는 방법은 쓸 수 없습니다. 길이 m인 문자열의 각 글자는 부분 수열에 들어가거나 안 들어가므로 부분 수열이 2ᵐ개이고, 길이 50인 문자열만 되어도 1000조 개가 넘습니다. 하나하나 다른 문자열의 부분 수열인지 확인하는 것은 불가능합니다.

상태: 두 문자열의 앞부분

동적 계획법의 첫 단계는 상태를 정하는 것입니다. 두 문자열 first와 second가 있을 때, table[i][j]를 "first의 앞 i글자와 second의 앞 j글자의 LCS 길이"로 정합니다. 앞 0글자는 빈 문자열이므로 table[0][j]와 table[i][0]은 모두 0입니다. 우리가 원하는 답은 두 문자열 전체에 해당하는 table[m][n]입니다.

점화식은 두 앞부분의 마지막 글자를 기준으로 경우를 나누어 세웁니다. 두 마지막 글자 first[i - 1]과 second[j - 1]이 같다면, 그 글자를 공통 부분 수열의 마지막 글자로 쓰고 두 문자열에서 모두 한 글자씩 뺀 나머지의 LCS에 붙이면 됩니다. 그래서 table[i][j] = table[i - 1][j - 1] + 1입니다. 두 마지막 글자가 다르다면, 두 글자를 모두 공통 부분 수열의 마지막 글자로 쓸 수는 없습니다. 그러면 공통 부분 수열은 first의 마지막 글자를 쓰지 않거나 second의 마지막 글자를 쓰지 않으므로, 한쪽 마지막 글자를 뺀 두 경우 가운데 큰 쪽을 고릅니다.

table[i][j] = table[i - 1][j - 1] + 1                  (두 마지막 글자가 같을 때)
table[i][j] = max(table[i - 1][j], table[i][j - 1])    (다를 때)

표로 보면 같을 때는 왼쪽 위 대각선 칸을, 다를 때는 위 칸과 왼쪽 칸을 읽습니다. 아래 그림은 AB와 AC의 칸을 계산하는 모습입니다. 마지막 글자 B와 C가 다르므로 위 칸의 1과 왼쪽 칸의 1 가운데 큰 값 1을 적습니다.

표 채우기

각 칸은 위, 왼쪽, 왼쪽 위의 칸만 읽으므로 위의 행부터, 각 행에서는 왼쪽 칸부터 채우면 필요한 칸이 늘 먼저 채워집니다. ABC와 AC의 표는 다음과 같습니다. 행은 ABC의 앞부분, 열은 AC의 앞부분입니다.

A행 A열은 두 마지막 글자 A가 같아 왼쪽 위의 0에 1을 더한 1입니다. AB행 AC열은 마지막 글자 B와 C가 달라 위의 1과 왼쪽의 1 가운데 큰 1이고, ABC행 AC열은 C와 C가 같아 왼쪽 위의 1에 1을 더한 2입니다. 마지막 칸의 2가 LCS의 길이입니다.

표를 거꾸로 따라가 답을 복원한다

표에는 길이만 있지만, 각 칸이 어느 칸에서 왔는지를 거꾸로 따라가면 LCS 자체를 얻을 수 있습니다. 마지막 칸에서 시작해, 두 마지막 글자가 같으면 그 글자를 답에 넣고 왼쪽 위로 갑니다. 다르면 위 칸과 왼쪽 칸 가운데 값이 큰 쪽으로 갑니다. 그 칸이 지금 칸의 값을 만든 쪽이기 때문입니다. 두 값이 같으면 어느 쪽으로 가도 같은 길이의 LCS가 나오며, 아래 코드는 위쪽을 택합니다. 이렇게 모은 글자는 뒤에서부터 모였으므로 마지막에 뒤집습니다.

def lcs(first, second):
    rows, columns = len(first), len(second)
    table = [[0] * (columns + 1) for _ in range(rows + 1)]
    for i in range(1, rows + 1):
        for j in range(1, columns + 1):
            if first[i - 1] == second[j - 1]:
                table[i][j] = table[i - 1][j - 1] + 1
            else:
                table[i][j] = max(table[i - 1][j], table[i][j - 1])
    answer = []
    i, j = rows, columns
    while i > 0 and j > 0:
        if first[i - 1] == second[j - 1]:
            answer.append(first[i - 1])
            i, j = i - 1, j - 1
        elif table[i - 1][j] >= table[i][j - 1]:
            i -= 1
        else:
            j -= 1
    answer.reverse()
    return answer, table


answer, table = lcs("ABC", "AC")
print("".join(answer))
for row in table:
    print(row)
answer, table = lcs("ABCBDAB", "BDCABA")
print("".join(answer), table[-1][-1])
print(lcs("", "ABC")[0])

AC
[0, 0, 0]
[0, 1, 1]
[0, 1, 1]
[0, 1, 2]
BCBA 4
[]

ABC와 AC에서는 마지막 칸에서 C가 같아 C를 넣고 왼쪽 위로 가고, B와 A가 달라 위로 간 뒤, A가 같아 A를 넣습니다. 모은 C, A를 뒤집으면 AC입니다. 함수는 글자들의 리스트를 돌려주므로, 문자열이 필요하면 "".join으로 잇습니다. 리스트를 돌려주게 만든 덕분에 이 함수는 문자열뿐 아니라 리스트끼리도 비교할 수 있는데, 이것을 더 깊이에서 씁니다.

왜 맞는가

점화식의 두 경우가 모두 맞는다는 것을 보이면, 작은 앞부분부터 채우는 순서에 따라 귀납법으로 모든 칸이 맞습니다. 먼저 두 마지막 글자가 같은 경우입니다. 이 글자를 쓰지 않는 공통 부분 수열이 있다면, 그 끝에 이 글자를 붙여도 여전히 공통 부분 수열이므로 하나 더 길어집니다. 그래서 가장 긴 공통 부분 수열은 이 글자로 끝나는 것으로 골라도 되고, 그 앞부분은 두 문자열에서 한 글자씩 뺀 나머지의 LCS여야 합니다. 앞부분이 더 길어질 수 있다면 전체도 더 길어지기 때문입니다.

두 마지막 글자가 다른 경우에는, 어떤 공통 부분 수열도 두 글자를 모두 마지막 글자로 쓸 수 없습니다. 공통 부분 수열의 마지막 글자는 두 문자열에서 같은 글자여야 하는데 두 마지막 글자가 서로 다르기 때문입니다. 따라서 모든 공통 부분 수열은 first의 마지막 글자를 뺀 쪽이나 second의 마지막 글자를 뺀 쪽의 공통 부분 수열이고, 두 경우의 최댓값을 고르면 놓치는 것이 없습니다. 복원은 i나 j가 반복마다 줄어들어 한쪽이 0이 되면 끝납니다.

비용

두 문자열의 길이가 m과 n이면 표에 칸이 (m + 1) × (n + 1)개 있고 칸마다 상수 시간이 들므로, 시간과 공간이 모두 O(mn)입니다. 복원은 i와 j 가운데 하나가 반복마다 1씩 줄어 O(m + n)입니다. 길이만 필요하다면 각 행이 바로 위 행만 읽으므로 두 행만 남겨 공간을 O(n)으로 줄일 수 있습니다. 답의 복원까지 적은 공간으로 하는 방법도 있지만, 이 글에서는 복원을 위해 표 전체를 남겼습니다.

더 깊이: 비교 도구는 LCS로 바뀐 곳을 찾는다

처음에 든 문서 비교 도구는 문서를 줄 단위로 나누고, 두 판의 줄 목록에서 LCS를 구해 그 줄들을 바뀌지 않은 줄로 봅니다. LCS에 들지 않은 줄은 이전 판에만 있으면 지워진 줄, 새 판에만 있으면 추가된 줄입니다. 바뀌지 않은 줄을 가장 많이 남기는 것이 곧 지우고 추가하는 줄을 가장 적게 만드는 것이기 때문입니다.

def lcs(first, second):
    rows, columns = len(first), len(second)
    table = [[0] * (columns + 1) for _ in range(rows + 1)]
    for i in range(1, rows + 1):
        for j in range(1, columns + 1):
            if first[i - 1] == second[j - 1]:
                table[i][j] = table[i - 1][j - 1] + 1
            else:
                table[i][j] = max(table[i - 1][j], table[i][j - 1])
    answer = []
    i, j = rows, columns
    while i > 0 and j > 0:
        if first[i - 1] == second[j - 1]:
            answer.append(first[i - 1])
            i, j = i - 1, j - 1
        elif table[i - 1][j] >= table[i][j - 1]:
            i -= 1
        else:
            j -= 1
    answer.reverse()
    return answer


def diff(old, new):
    i = j = 0
    for line in lcs(old, new):
        while old[i] != line:
            print("-", old[i])
            i += 1
        while new[j] != line:
            print("+", new[j])
            j += 1
        print(" ", line)
        i += 1
        j += 1
    for line in old[i:]:
        print("-", line)
    for line in new[j:]:
        print("+", line)


diff(["장보기", "빨래", "청소", "독서"], ["장보기", "청소", "독서", "운동"])

  장보기
- 빨래
  청소
  독서
+ 운동

diff는 LCS의 줄을 하나씩 보면서, 두 목록에서 그 줄이 나올 때까지 지나친 줄을 각각 -와 +로 출력합니다. 실제 버전 관리 도구인 Git은 기본 설정에서 Myers 알고리즘이라는 더 빠른 방법을 씁니다. Myers 알고리즘은 가장 짧은 편집 과정을 찾는 방법이고, 이것은 LCS를 구하는 것과 같은 문제입니다. 다만 Git은 편집 비용이 커지면 탐색을 일찍 끊는 장치를 함께 쓰므로 결과가 늘 가장 짧지는 않고, 가장 짧은 결과가 꼭 필요하면 git diff --minimal을 씁니다. Python 표준 라이브러리의 difflib은 사람이 읽기 좋은 결과를 내도록 조금 다른 방법을 쓰지만, 바뀌지 않은 부분을 먼저 찾는다는 생각은 같습니다.

정리

• 부분 수열은 글자를 건너뛸 수 있지만 순서는 지키는 것이고, 부분 문자열은 연속된 구간입니다. LCS는 두 문자열의 공통 부분 수열 가운데 가장 긴 것입니다.
• 상태 table[i][j]를 두 문자열의 앞 i글자와 앞 j글자의 LCS 길이로 정하고, 두 마지막 글자가 같으면 대각선 칸에 1을 더하고, 다르면 위 칸과 왼쪽 칸 가운데 큰 값을 씁니다.
• 마지막 칸에서 시작해 값을 만든 칸을 거꾸로 따라가면 LCS 하나를 복원할 수 있습니다. 길이가 같은 LCS는 여러 개일 수 있습니다.
• 시간과 공간은 O(mn)이고, 길이만 필요하면 두 행으로 공간을 O(n)까지 줄일 수 있습니다.
• 문서 비교 도구는 줄 목록의 LCS를 바뀌지 않은 줄로 보고, 나머지를 지워진 줄과 추가된 줄로 표시합니다.

연습 문제

1. 순서가 엇갈린 두 문자열

AB와 BA의 LCS 길이는 얼마이고, 가능한 LCS는 무엇인가요? 본문의 lcs는 어느 쪽을 돌려줄까요?

2. 미리 정렬하면 안 되는 이유

CAB와 CBA의 LCS 길이를 구하세요. 두 문자열을 모두 정렬해 ABC로 만든 뒤 LCS를 구하면 어떻게 될까요?

3. 부분 수열과 부분 문자열의 차이

ABXCD와 ABYCD의 LCS와, 두 문자열에 공통으로 들어 있는 가장 긴 부분 문자열을 각각 구하세요.

다음 장의 단순 문자열 탐색·롤링 해시·충돌에서는 짧은 문자열이 긴 문자열 안에 연속된 구간으로 나타나는 위치를 모두 찾습니다.