추가 설명 — 되짚기는 길 하나가 아니라 영역을 준다

편집 거리의 표는 마지막 칸에 수 하나를 남긴다. 두 번 고치면 된다는 사실은 알려 주지만 무엇을 어떻게 고치는지는 말하지 않는다. 되짚어 보면 답이 하나가 아닐 수도 있다는 사실까지 드러난다.

이 글에서 다루는 내용

표가 담는 것은 값이고, 어떤 연산을 썼는지는 별개다
칸마다 어느 이웃에서 왔는지 되묻는 되짚기 규칙
abcab 와 abcba 의 최적 정렬이 셋이라는 것을 직접 세기
최적 경로 전체가 표 위에 만드는 영역의 정확한 뜻
경로 개수를 세는 표, 그리고 그 수가 지수로 커지는 예

값과 연산은 다르다

본편의 표는 칸마다 최솟값 하나를 적었다. 그 최솟값이 어떤 정렬에서 나왔는지는 적지 않았다. 값을 구하는 데 필요하지 않았기 때문이다. 본편이 두 행만 남겨 공간을 줄인 판을 보였는데, 되짚기는 그 판으로 할 수 없다. 지나온 칸을 하나씩 되물어야 하므로 표가 통째로 남아 있어야 한다.

되짚기(traceback)는 채운 표를 거꾸로 읽어 그 정렬을 복원한다. 채울 때는 세 이웃 중 최솟값을 골랐으니, 되짚을 때는 그 최솟값을 이룬 이웃이 누구였는지 되묻는다.

거꾸로 읽는 규칙

칸 $(i, j)$ 에서 다음 세 등식을 검사한다.

$D(i, j) = D(i-1, j-1) + t(i, j)$ 이면 대각선에서 왔다. $t(i, j)$ 는 $S_1[i]$ 와 $S_2[j]$ 가 같으면 0, 다르면 1이므로, 0이면 맞추기고 1이면 바꾸기다
$D(i, j) = D(i-1, j) + 1$ 이면 위에서 왔다. $S_1[i]$ 를 지우는 연산이다
$D(i, j) = D(i, j-1) + 1$ 이면 왼쪽에서 왔다. $S_2[j]$ 를 넣는 연산이다

$i = 0$ 이면 왼쪽으로만, $j = 0$ 이면 위로만 갈 수 있다. $(0, 0)$ 에 닿으면 끝이고, 거꾸로 모은 연산을 뒤집으면 정렬이 된다.

예시를 바꾸자. $S_1 =$ abcab, $S_2 =$ abcba 이고 편집 거리는 2다.

abcab와 abcba의 표에서 (5,5)부터 대각선을 따라 (0,0)까지 되짚어 올라가는 경로

$(5, 5)$ 에서 시작한다. 값은 2다. 대각선 이웃 $(4, 4)$ 는 1이고 b 와 a 가 다르므로 $1 + 1 = 2$ 로 등식이 성립한다. 대각선을 따라 $(4, 4)$ 로 간다. 여기서도 a 와 b 가 달라 바꾸기 한 번이다. $(3, 3)$ 부터는 abc 가 그대로 맞으므로 대각선을 세 번 더 타고 $(0, 0)$ 에 닿는다. 복원한 정렬은 바꾸기 두 번이다.

동점이면 갈래가 갈린다

$(5, 5)$ 에서 성립한 등식은 대각선 하나가 아니었다. 위 이웃 $(4, 5)$ 도 1이라 $1 + 1 = 2$ 이고, 왼쪽 이웃 $(5, 4)$ 도 1이라 $1 + 1 = 2$ 다. 세 등식이 모두 성립한다. 되짚기는 어느 쪽으로도 갈 수 있고, 어느 쪽을 골라도 비용 2인 정렬이 나온다.

세 갈래를 끝까지 따라가면 정렬이 셋이다.

abcab와 abcba의 최적 정렬 세 개. 첫째는 바꾸기 두 번, 둘째는 넣기와 지우기, 셋째는 지우기와 넣기로 이루어진다.

정렬 1: abc 를 맞추고 a 를 b 로, b 를 a 로 두 번 바꾼다
정렬 2: abc 를 맞추고 b 를 넣은 뒤 a 를 맞추고 마지막 b 를 지운다
정렬 3: abc 를 맞추고 a 를 지운 뒤 b 를 맞추고 a 를 넣는다

셋 다 비용 2다. 편집 거리는 이 셋을 구별하지 않는다.

그래서 영역이다

최적 정렬이 여럿이면 되짚기의 결과를 길 하나로 적을 수 없다. 최적 경로 전체를 겹쳐 놓으면 남는 것은 칸의 집합이다.

영역의 정의

최적 경로 하나 이상이 지나는 칸을 모두 모은 것

abcab 와 abcba 의 영역은 공통 접두사 abc 를 따라가는 대각선과, $(3, 3)$ 에서 벌어져 $(5, 5)$ 에서 다시 모이는 마름모다.

세 최적 경로를 색으로 구분해 겹쳐 그리고, 그 경로들이 지나는 칸을 파선으로 표시한 그림

영역의 모양이 정보를 준다. 대각선 한 줄로 좁으면 최적 정렬이 사실상 하나이고 어느 글자를 어디에 맞출지 여지가 없다. 넓게 벌어지면 같은 비용의 정렬이 여럿이며, 그중 무엇을 고를지는 편집 거리가 정해 주지 않는다.

한 가지는 조심해야 한다. 영역은 최적 경로들의 합집합일 뿐, 영역 안을 아무렇게나 걸어도 최적이라는 뜻이 아니다. 위 그림에서 $(3, 4)$ 와 $(4, 3)$ 은 둘 다 영역 안이지만 두 칸을 함께 지나는 경로는 없다. 경로의 걸음은 오른쪽·아래·대각선 셋뿐이라 행 번호와 열 번호가 모두 줄어들지 않는다. $(3, 4)$ 를 먼저 지나면 뒤에 오는 칸의 열 번호가 4 아래로 내려갈 수 없어 $(4, 3)$ 에 닿지 못하고, $(4, 3)$ 을 먼저 지나면 행 번호가 4 아래로 내려갈 수 없어 $(3, 4)$ 에 닿지 못한다.

영역을 구하는 값싼 방법

칸 하나가 영역에 드는지 판정하려면 그 칸을 지나는 최적 경로가 있는지 물으면 된다. 채워 둔 표 $D$ 는 $(0, 0)$ 에서 $(i, j)$ 까지의 최소 비용이다. 두 문자열을 각각 뒤집어 같은 표를 한 번 더 채우면 접미사끼리의 편집 거리가 나온다. 뒤집은 표의 칸 $(n-i, m-j)$ 가 원래 표에서 $(i, j)$ 에서 $(n, m)$ 까지 가는 최소 비용이고, 이 값을 $D'(i, j)$ 라 하자. $(i, j)$ 를 지나는 경로의 최소 비용이 $D(i, j) + D'(i, j)$ 이므로, 칸이 영역에 드는 조건은 $D(i, j) + D'(i, j) = D(n, m)$ 이다. 표 두 개를 채우는 비용이라 여전히 $O(NM)$ 이다.

경로가 몇 개인지 세기

경로를 일일이 따라가지 않고도 개수를 셀 수 있다. 표를 한 번 더 채우면 된다.

$C(i, j)$ 를 $(0, 0)$ 에서 $(i, j)$ 까지 가는 최적 경로의 개수라 하자. $C(0, 0) = 1$ 이고, 나머지 칸에서는 되짚기 등식이 성립하는 이웃의 $C$ 를 더한다. 본편처럼 본문의 인덱스는 1부터 세고 배열은 0부터 세므로, 코드에서 글자를 꺼낼 때 하나를 뺀다.

// D는 본편의 방식으로 이미 채워져 있다고 가정한다
long long countOptimalPaths(const string& s1, const string& s2,
                            const vector<vector<int>>& D) {
    int n = s1.size(), m = s2.size();
    vector<vector<long long>> C(n + 1, vector<long long>(m + 1, 0));
    C[0][0] = 1;

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++) {
            if (i == 0 && j == 0) continue;
            long long c = 0;
            if (i && j) {
                int t = (s1[i-1] == s2[j-1]) ? 0 : 1;
                if (D[i][j] == D[i-1][j-1] + t) c += C[i-1][j-1];
            }
            if (i && D[i][j] == D[i-1][j] + 1) c += C[i-1][j];
            if (j && D[i][j] == D[i][j-1] + 1) c += C[i][j-1];
            C[i][j] = c;
        }
    return C[n][m];
}

abcab 와 abcba 에 돌리면 3이 나온다. 본편의 예시 abcabcd 와 abcdabc 에 돌리면 1이다. 편집 거리는 양쪽 모두 2인데 한쪽은 정렬이 셋이고 다른 쪽은 하나다.

개수는 아주 빨리 커진다. aaaa 와 aa 를 보자. 편집 거리는 2이고, 네 개의 a 중 어느 둘을 지워도 비용이 2다. 경로는 $\binom{4}{2} = 6$ 개다. 일반적으로 a 를 $2k$ 개 늘어놓은 문자열과 $k$ 개 늘어놓은 문자열 사이의 최적 경로는 $\binom{2k}{k}$ 개이고, 이 값은 $k$ 에 대해 지수로 늘어난다.

이 사실이 결과를 영역으로 적는 이유를 설명한다. 최적 정렬을 전부 나열하려면 출력 자체가 지수 크기일 수 있다. 영역은 표의 칸을 넘지 않으므로 언제나 $(n+1)(m+1)$ 안에 담긴다.

어느 정렬을 고를 것인가

되짚기 코드에서 세 등식을 검사하는 순서가 그대로 정책이 된다. 되짚기는 정렬을 뒤에서부터 복원하므로, 대각선을 먼저 보면 뒤쪽에서 최대한 글자를 짝지어 나가고 빈 칸은 정렬의 앞쪽으로 밀린다. 위쪽을 먼저 보면 지우기가 뒤쪽에 먼저 놓인다. 비용은 어느 쪽이든 같으므로 알고리즘은 아무 말도 해 주지 않는다.

선택은 응용이 한다. 유전자 서열 정렬에서는 빈 칸이 흩어지기보다 한군데 뭉치는 편이 그럴듯하므로, 빈 칸을 여는 비용과 늘리는 비용을 따로 두는 모델을 쓴다. 이 모델은 세 항의 상수만 바꿔서는 담기지 않고, 지금 열이 빈 칸의 연속인지를 함께 들고 가야 한다. 오타 교정에서는 본편의 가중 편집 거리처럼 자판 거리를 비용에 반영한다. 두 경우의 공통점은 정렬을 고르는 기준을 비용 함수 안으로 들여온다는 것이다.

핵심 정리

표는 값을 담고, 되짚기는 그 값을 낸 연산을 복원한다. 동점이 있으면 최적 정렬이 여럿이므로 결과는 길 하나가 아니라 최적 경로가 지나는 칸의 집합, 곧 영역이다. 경로의 개수는 지수로 커질 수 있지만 영역은 표 크기 안에 담긴다.

돌아가는 글

편집 거리의 정의와 점화식, 표를 채우는 방법과 $O(NM)$ 의 정확한 의미는 편집 거리 — 비슷하다는 말을 수로 바꾸기에 있다.

마치며

표를 채우는 일과 되짚는 일은 방향만 다르다. 채울 때는 세 이웃에서 최선을 골랐고, 되짚을 때는 그 최선이 누구였는지 물었다. 물음의 답이 하나가 아닐 수 있다는 것, 그래서 결과가 길 하나가 아니라 영역이 된다는 것이 되짚기가 값 계산과 갈리는 지점이다.