편집 거리 — 비슷하다는 말을 수로 바꾸기

검색창에 recieve 를 치면 receive 를 권한다. 기계가 두 낱말이 비슷하다고 판단하려면 ‘비슷함’이 먼저 수여야 한다. 이 글은 그 수를 정의하고, 정의가 계산 방법까지 정해 주는 과정을 따라간다.

이 포스트에서 다루는 내용

거리 함수: 자리끼리만 맞추는 Hamming 거리가 어디서 무너지는가
편집 거리: 넣기·지우기·바꾸기의 최소 횟수
점화식: 최적 정렬의 마지막 열이 세 모양뿐이라는 논증
표 채우기: 기저 두 줄에서 시작해 세 이웃만 보고 채운다
비용: $O(NM)$ 과 “이보다 빠를 수 없다”는 말의 정확한 뜻

비슷함을 재는 자

세 장면을 놓고 보자. 검색창의 오타를 고쳐 주는 일, 두 유전자 서열이 얼마나 닮았는지 판정하는 일, 제출된 두 과제가 서로 베낀 것인지 가늠하는 일이다. 하는 일은 다르지만 필요한 재료는 같다. 문자열 두 개를 받아 수 하나를 내놓는 함수, 곧 거리 함수다. 그 수가 작으면 비슷하고 크면 다르다.

거리 함수를 어떻게 정하느냐가 무엇을 ‘비슷하다’고 볼지 정한다. 정의가 알고리즘보다 먼저다.

자리끼리 맞추기

가장 단순한 정의는 같은 자리를 견주는 것이다. 길이가 같은 두 문자열에서 글자가 다른 자리의 개수를 세면 Hamming 거리가 된다. sunny 와 funny 는 첫 자리만 다르므로 1이고, 01101 과 00111 은 두 자리가 다르므로 2다.

이 정의가 제자리를 찾는 곳이 있다. 고정 길이 블록을 네트워크로 주고받는 상황을 보자. 전송 중에 어떤 비트가 뒤집혀도 자리는 밀리지 않는다. 받은 블록과 보낸 블록의 Hamming 거리가 곧 오염된 비트 수다.

문제는 길이가 다를 때다. Hamming 거리는 길이가 같은 두 문자열에만 정의된다. 억지로 앞에서부터 자리를 맞춰 보자. $S_1 =$ ababc 와 $S_2 =$ abbc 는 앞의 두 자리가 같고, 셋째 자리에서 a 와 b 가 어긋나고, 넷째 자리에서 b 와 c 가 어긋나고, 다섯째 자리는 상대가 없다. 어긋남이 세 곳이다.

위쪽은 ababc와 abbc를 자리끼리 맞춘 비교로 세 자리가 어긋난다. 아래쪽은 셋째 자리에 빈 칸을 허용한 비교로 어긋남이 한 곳이다.

실제로 두 문자열의 차이는 글자 하나다. ababc 에서 셋째 글자 a 를 지우면 abbc 다. 어긋남이 셋으로 부푼 이유는 지운 자리 뒤의 글자가 모두 한 칸씩 밀렸기 때문이다. 자리를 고정한 비교에는 이 밀림을 적을 방법이 없다.

밀림을 허용하기

밀림을 적으려면 비교하는 쪽에 빈 칸을 놓을 수 있어야 한다. 허용하는 연산을 셋으로 정하자.

넣기(insert): 글자 하나를 새로 끼워 넣는다
지우기(delete): 글자 하나를 없앤다
바꾸기(change): 글자 하나를 다른 글자로 고친다

편집 거리(edit distance)는 한 문자열을 다른 문자열로 만드는 데 필요한 이 연산의 최소 횟수다. ababc 와 abbc 의 편집 거리는 1이다. 지우기 한 번으로 끝난다. 위 그림의 아래쪽이 그 연산을 빈 칸으로 그린 것이다.

연산마다, 그리고 바꾸기라면 글자 쌍마다 비용을 다르게 두면 가중 편집 거리(weighted edit distance)가 된다. 자판을 떠올리면 자연스럽다. a 와 s 는 한 칸 옆이라 잘못 누르기 쉽고, a 와 p 는 손이 반대편이라 그럴 일이 드물다. 오타 교정이라면 a → s 의 비용을 작게, a → p 의 비용을 크게 두는 편이 실제 오타 분포에 가깝다.

셋 다 잡지 못하는 것

abcdef 와 defabc 는 앞의 세 글자와 뒤의 세 글자를 통째로 맞바꾼 관계다. 사람 눈에는 조각을 옮긴 것 하나지만 편집 거리는 6이고, 이는 여섯 글자를 전부 새로 쓰는 값과 같다. 옮기기(move)나 베끼기(copy)를 연산 목록에 넣지 않았으므로 이런 관계는 ‘완전히 다름’으로 판정된다. 가중치를 얹어도 달라지지 않는다.

부분 문제

이제 편집 거리를 계산해야 한다. $S_1$ 과 $S_2$ 의 길이를 각각 $n$ , $m$ 이라 하자.

부분 문제의 정의

$D(i, j)$ = $S_1$ 의 앞 $i$ 글자와 $S_2$ 의 앞 $j$ 글자, 곧 두 접두사 사이의 편집 거리

찾는 답은 $D(n, m)$ 이다. $i$ 나 $j$ 가 0이면 빈 문자열과의 거리를 뜻한다.

$S_1 =$ abcabcd, $S_2 =$ abcdabc 로 보자. $D(2, 4)$ 는 ab 와 abcd 의 거리이고 값은 2다. ab 뒤에 c 와 d 를 넣으면 되므로 넣기 두 번이다. $D(5, 1)$ 은 abcab 와 a 의 거리이고 값은 4다. 앞의 a 를 짝지어 두고 남은 네 글자를 지우면 된다.

abcabcd를 행, abcdabc를 열로 둔 격자에서 D(2,4), D(5,1), D(7,7) 세 칸이 각각 어느 접두사 쌍을 가리키는지와 그 값이 각각 2, 4, 2임을 표시한 그림

$i$ 는 0부터 $n$ , $j$ 는 0부터 $m$ 까지 움직이므로 칸은 $(n+1)(m+1)$ 개다.

마지막 열에서 무슨 일이 있었나

점화식을 세우기 전에 말을 하나 만들어 두자. 두 문자열의 글자를 위아래로 짝지어 늘어놓은 것을 정렬(alignment)이라 부른다. 각 문자열의 글자를 순서대로 하나씩 모두 쓰고, 위아래가 함께 비는 열은 두지 않는다. 열은 세 모양뿐이다.

위아래에 글자가 하나씩 있는 열. 두 글자가 같으면 비용 0, 다르면 바꾸기 한 번이므로 비용 1
위에만 글자가 있는 열. $S_1$ 의 글자를 지우므로 비용 1
아래에만 글자가 있는 열. $S_2$ 의 글자를 넣으므로 비용 1

정렬의 비용은 열 비용의 합이다. 연산의 열과 정렬은 서로 옮겨 적을 수 있고, 그래서 두 최솟값이 같다. 정렬에서 연산의 열로 가는 길은 이렇다. 비용이 붙은 열마다 그 열이 말하는 연산을 왼쪽에서 오른쪽으로 적용하면 $S_1$ 이 $S_2$ 가 되고, 쓴 연산의 수는 정렬의 비용과 같다. 반대 방향은 이렇다. 연산을 차례로 적용하는 동안 어느 글자가 어느 글자와 짝지어졌는지만 남기면 정렬이 하나 나오고, 그 비용은 쓴 연산의 수를 넘지 않는다. 한 글자를 두 번 고친 경우처럼 낭비가 있으면 오히려 줄어든다. 두 방향을 합치면 최소 연산 수와 최소 정렬 비용이 같다. 앞 그림 아래쪽의 빈 칸 표기가 바로 정렬이다.

이제 $D(i, j)$ 를 내는 최적 정렬의 마지막 열만 본다.

정리 1마지막 열의 세 모양

$t(i, j)$ 를 $S_1[i] = S_2[j]$ 이면 0, 아니면 1이라 하자. $i \ge 1$ , $j \ge 1$ 이면 다음이 성립한다.

D(i, j) \;=\; \min\bigl\{\, D(i-1, j-1) + t(i, j),\;\; D(i-1, j) + 1,\;\; D(i, j-1) + 1 \,\bigr\}

기저는 $D(i, 0) = i$ , $D(0, j) = j$ 다.

증명. 기저부터 보자. 한쪽이 빈 문자열이면 짝지을 글자가 없다. $S_1$ 의 앞 $i$ 글자를 모두 지우는 정렬만 가능하고 그 비용은 $i$ 다. 반대쪽도 같은 이유로 $j$ 다.

좌변은 우변 이하다. 우변의 세 값 각각에 대해 그 비용을 내는 정렬을 실제로 만들 수 있다. $D(i-1, j-1)$ 을 내는 정렬 뒤에 $S_1[i]$ 와 $S_2[j]$ 가 마주 보는 열을 붙이면 두 접두사 전체를 덮는 정렬이고 비용은 $D(i-1, j-1) + t(i, j)$ 다. $D(i-1, j)$ 를 내는 정렬 뒤에 $S_1[i]$ 만 있는 열을 붙이면 비용은 $D(i-1, j) + 1$ 이고, $D(i, j-1)$ 을 내는 정렬 뒤에 $S_2[j]$ 만 있는 열을 붙이면 비용은 $D(i, j-1) + 1$ 이다. 편집 거리는 가능한 정렬 중 최소 비용이므로 $D(i, j)$ 는 세 값 모두 이하이고, 따라서 최솟값 이하다.

좌변은 우변 이상이다. $D(i, j)$ 를 내는 최적 정렬 $A$ 를 하나 잡는다. $i \ge 1$ 이고 $j \ge 1$ 이므로 $A$ 에는 열이 하나 이상 있고, 마지막 열은 위에서 나눈 세 모양 중 하나다.

위아래에 글자가 있는 열이라면 그 두 글자는 각 접두사의 마지막 글자, 곧 $S_1[i]$ 와 $S_2[j]$ 다. 이 열을 떼면 남는 것은 $S_1$ 의 앞 $i-1$ 글자와 $S_2$ 의 앞 $j-1$ 글자를 덮는 정렬이고, 그 비용은 최소 비용인 $D(i-1, j-1)$ 이상이다. 뗀 열의 비용이 $t(i, j)$ 이므로 $A$ 의 비용은 $D(i-1, j-1) + t(i, j)$ 이상이다.
위에만 글자가 있는 열이라면 그 글자는 $S_1[i]$ 다. 같은 논리로 $A$ 의 비용은 $D(i-1, j) + 1$ 이상이다.
아래에만 글자가 있는 열이라면 그 글자는 $S_2[j]$ 다. $A$ 의 비용은 $D(i, j-1) + 1$ 이상이다.

세 모양이 경우 전체를 덮으므로 $A$ 의 비용은 우변의 세 값 중 적어도 하나 이상이고, 그 값은 최솟값 이상이다. $A$ 의 비용이 $D(i, j)$ 이므로 좌변은 우변 이상이다. 두 방향을 합치면 등호다. ∎

이 정리가 답하는 물음이 하나 있다. 계산을 시작할 때 우리는 $S_1[i]$ 와 $S_2[j]$ 가 같은지 다른지 알아야 하는 것처럼 보이지만, 두 글자의 일치 여부는 $t(i, j)$ 한 항이 전부 흡수하고 나머지 구조는 그대로다. 맞추기(match)와 바꾸기를 따로 세면 갈래가 넷이고 열의 모양으로 세면 셋인 이유도 같다. 두 연산은 같은 모양의 열에서 비용만 갈린다.

D(i,j) 칸으로 들어오는 세 화살표와, 표 안쪽의 칸이 다시 쓰이는 세 칸을 점선으로 표시한 그림

답이 연산의 열이라는 관점

같은 이야기를 다른 각도에서 적을 수도 있다. 답은 넣기·지우기·맞추기·바꾸기 네 기호를 늘어놓은 열이고, 편집 거리는 그중 비용이 가장 작은 열의 비용이다.

이렇게 적으면 순환처럼 들린다. 최선의 열을 정의하는 자리에 최선의 열이 다시 나온다. 순환이 아닌 이유는 참조의 방향이다. $(i, j)$ 의 답은 $(i-1, j-1)$ , $(i-1, j)$ , $(i, j-1)$ 세 곳만 본다. 어느 쪽으로 가든 $i + j$ 가 적어도 1 줄어든다. 줄어들기만 하는 참조는 유한 번에 $(0, 0)$ 에 닿고, 그 자리의 답은 빈 열이다. 순환 참조는 같은 크기의 문제를 다시 참조할 때 생기며, 여기에는 그런 참조가 없다.

표를 격자로 보면 대응이 더 분명해진다. 칸 $(i, j)$ 를 격자점으로 두면 연산의 열은 $(0, 0)$ 에서 $(n, m)$ 까지 가는 걸음의 열이다.

대각선으로 한 칸 = 맞추기 또는 바꾸기
아래로 한 칸 = $S_1$ 의 글자 지우기
오른쪽으로 한 칸 = $S_2$ 의 글자 넣기

걸음마다 비용이 붙고 편집 거리는 가장 싼 경로의 비용이다. 편집 거리를 구하는 일은 격자에서 최단 경로를 찾는 일과 같다. 이 대응은 추가 설명에서 다시 쓴다.

표 채우기

기저 두 줄부터 채운다. $D(i, 0) = i$ , $D(0, j) = j$ 이므로 첫 열과 첫 행은 0, 1, 2, … 로 늘어난다.

내부 칸은 위·왼쪽·왼쪽 위 대각선을 본다. 세 이웃이 먼저 채워져 있어야 하므로 위에서 아래로, 각 행에서는 왼쪽에서 오른쪽으로 훑으면 된다.

작은 예를 손으로 채워 보자. $S_1 =$ v, $S_2 =$ wr 다. 기저는 $D(0, 0) = 0$ , $D(0, 1) = 1$ , $D(0, 2) = 2$ , $D(1, 0) = 1$ 이다.

$D(1, 1)$ : v 와 w 가 다르므로 $t = 1$ 이다. 대각선 $0 + 1 = 1$ , 위 $1 + 1 = 2$ , 왼쪽 $1 + 1 = 2$ 중 최솟값은 1
$D(1, 2)$ : v 와 r 가 다르므로 $t = 1$ 이다. 대각선 $1 + 1 = 2$ , 위 $2 + 1 = 3$ , 왼쪽 $1 + 1 = 2$ 중 최솟값은 2

$D(1, 2) = 2$ 인데 최솟값을 이룬 이웃이 둘이다. 대각선에서 왔다면 w 를 넣고 v 를 r 로 바꾼 것이고, 왼쪽에서 왔다면 v 를 w 로 바꾸고 r 를 넣은 것이다. 두 정렬의 비용이 같다. 값은 하나지만 그 값을 내는 방법은 여럿일 수 있다.

앞의 예시로 돌아가 $S_1 =$ abcabcd, $S_2 =$ abcdabc 의 표를 끝까지 채우면 이렇다.

abcabcd와 abcdabc의 완성된 편집 거리 표. 기저인 첫 행과 첫 열은 0부터 7까지 늘어나고 마지막 칸의 값은 2다.

답은 2다. abc 뒤에 d 를 넣고 맨 끝의 d 를 지우면 abcdabc 가 된다.

비용

칸이 $(n+1)(m+1)$ 개이고, 칸마다 하는 일은 이웃 세 값을 견주고 $t$ 를 한 번 구하는 것이라 상수 시간이다. 전체는 $O(NM)$ 이다. 여기서 $N$ , $M$ 은 두 문자열의 길이 $n$ , $m$ 을 가리킨다.

표를 통째로 들고 있으면 공간도 $O(NM)$ 이다. 값만 필요하다면 훨씬 적게 쓸 수 있다. 한 행을 채우는 동안 참조하는 것은 바로 위 행과 지금 행뿐이므로 두 행만 남기면 되고, 짧은 쪽을 열로 두면 공간은 $O(\min(N, M))$ 이다.

재귀로 곧장 옮기면 사정이 다르다. 호출 하나가 갈래 셋으로 벌어지고 깊이는 최대 $n + m$ 이므로 호출 수가 $3^{n+m}$ 규모로 커진다. 같은 칸을 몇 번씩 다시 계산하기 때문이다. 표 내부의 칸 $D(i, j)$ 는 $D(i+1, j)$ , $D(i, j+1)$ , $D(i+1, j+1)$ 세 곳에서 쓰인다. 마지막 행과 열의 칸은 이보다 적게 쓰이고 $D(n, m)$ 은 쓰이지 않는다. 표는 그 칸을 한 번만 계산해 세 번 나눠 쓴다. 겹치는 부분 문제를 한 번만 풀고 재사용하는 이 방식이 동적 계획법이고, 동적 계획법 ②가 같은 방식으로 다른 문제를 푼다.

이보다 빠를 수 없다는 말

$O(NM)$ 을 두고 “이보다 빠른 방법은 없다”고 말할 때가 있다. 정확히 옮기면 조건이 붙는다.

이차에 가까운 무조건적 하한은 알려져 있지 않다. 알려진 것은 다른 가설에 기댄 하한이다. Backurs와 Indyk는 길이가 모두 $n$ 인 두 문자열에 대해, SETH(강한 지수 시간 가설)가 참이라면 어떤 상수 $\varepsilon > 0$ 에 대해서도 $O(n^{2-\varepsilon})$ 시간 알고리즘이 존재하지 않음을 보였다. 근거가 SETH이므로 SETH가 거짓으로 밝혀지면 이 결론도 함께 무너진다.

조건을 좁히면 더 빠른 방법이 실제로 있다. 아래 둘은 위의 하한과 부딪히지 않는다. 로그 인자만큼 줄인 시간은 여전히 $O(n^{2-\varepsilon})$ 이 아니고, $O(nd)$ 는 거리가 작다는 가정을 새로 얹은 결과다.

알파벳이 유한하면 Masek과 Paterson의 방법이 로그 인자만큼 빠르다. 작은 조각의 계산 결과를 미리 표로 만들어 두고 한꺼번에 가져다 쓰는 방식이다.
편집 거리가 $d$ 이하라고 미리 알고 있으면 Ukkonen의 방법이 $O(nd)$ 다. 최적 경로는 주대각선에서 $d$ 칸보다 멀리 벗어날 수 없다. 벗어난 만큼 되돌아와야 하고 그 왕복만으로 이미 비용이 $d$ 를 넘기 때문이다. 대각선 주변의 띠만 채우면 된다.

참고 문헌

R. A. Wagner, M. J. Fischer, “The String-to-String Correction Problem”, JACM 21(1), 1974
W. J. Masek, M. S. Paterson, “A faster algorithm computing string edit distances”, JCSS 20(1), 1980
E. Ukkonen, “Algorithms for approximate string matching”, Information and Control 64, 1985
A. Backurs, P. Indyk, “Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)”, STOC 2015 (arXiv:1412.0348)

코드

표를 그대로 옮기면 이렇다. 본문의 인덱스는 1부터 셌고 배열은 0부터 세므로 글자를 꺼낼 때 하나를 뺀다.

// 단위 비용: 넣기·지우기·바꾸기가 모두 1
int editDistance(const string& s1, const string& s2) {
    int n = s1.size(), m = s2.size();
    vector<vector<int>> D(n + 1, vector<int>(m + 1));

    for (int i = 0; i <= n; i++) D[i][0] = i;   // 기저: 전부 지우기
    for (int j = 0; j <= m; j++) D[0][j] = j;   // 기저: 전부 넣기

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int t = (s1[i-1] == s2[j-1]) ? 0 : 1;
            D[i][j] = min({ D[i-1][j-1] + t,    // 맞추기 또는 바꾸기
                            D[i-1][j] + 1,      // s1[i] 지우기
                            D[i][j-1] + 1 });   // s2[j] 넣기
        }
    return D[n][m];
}

값만 필요하면 두 행으로 줄인다. 단위 비용에서는 넣기와 지우기의 값이 같아 편집 거리가 대칭이므로, 두 문자열의 역할을 바꿔 짧은 쪽을 열에 두어도 답은 같다.

int editDistanceTwoRows(const string& s1, const string& s2) {
    const string& a = s1.size() >= s2.size() ? s1 : s2;   // 긴 쪽을 행으로
    const string& b = s1.size() >= s2.size() ? s2 : s1;   // 짧은 쪽을 열로
    int n = a.size(), m = b.size();

    vector<int> prev(m + 1), cur(m + 1);
    for (int j = 0; j <= m; j++) prev[j] = j;

    for (int i = 1; i <= n; i++) {
        cur[0] = i;
        for (int j = 1; j <= m; j++) {
            int t = (a[i-1] == b[j-1]) ? 0 : 1;
            cur[j] = min({ prev[j-1] + t, prev[j] + 1, cur[j-1] + 1 });
        }
        swap(prev, cur);            // 방금 채운 행이 다음 반복의 '위 행'이 된다
    }
    return prev[m];
}

가중 편집 거리로 옮기려면 세 항의 1 과 t 를 비용 함수로 바꾸면 된다. 넣기와 지우기의 비용을 다르게 두는 순간 대칭이 깨지므로, 짧은 쪽을 열로 두는 위의 교체는 그때 쓸 수 없다.

핵심 정리

편집 거리는 최소 비용 정렬의 비용이다. 최적 정렬의 마지막 열이 세 모양 중 하나라는 사실에서 점화식이 곧바로 나온다. 표는 칸마다 세 이웃만 보고 한 번씩 채우므로 $O(NM)$ 이며, 강한 준이차 시간의 일반 알고리즘이 없다는 결론은 SETH 가정에 기대고 있다.

이어지는 글

표를 다 채웠지만 손에 남은 것은 수 하나다. 어떤 연산을 어디에 썼는지는 표에 적혀 있지 않고, v 와 wr 에서 봤듯 같은 값을 내는 정렬이 여럿일 수도 있다. 표를 거꾸로 읽어 연산을 복원하는 방법과, 최적 정렬이 여럿일 때 결과가 왜 길 하나가 아니라 표 위의 영역이 되는지는 추가 설명 — 되짚기는 길 하나가 아니라 영역을 준다에서 다룬다.

마치며

시작은 정의 문제였다. 자리를 고정한 비교는 밀림을 적지 못했고, 빈 칸을 허용하자 편집 거리가 나왔다. 정의를 바꾸자 계산 방법도 따라 바뀌었다. 최적 정렬의 마지막 열이 무엇이었는지 되묻는 것만으로 점화식이 나왔고, 표 하나가 그 점화식을 그대로 담았다.

무엇을 연산 목록에 넣느냐가 무엇을 ‘비슷하다’고 볼지 정한다. 옮기기를 넣지 않았기 때문에 abcdef 와 defabc 는 완전히 다른 문자열이다. 목록을 늘리면 잡아내는 관계도 늘지만 계산은 그만큼 어려워진다. 최대 부분배열에서도 부분 문제를 어떻게 잡느냐가 알고리즘을 갈랐다. 여기서는 부분 문제를 접두사 쌍으로 잡은 한 줄이 표 하나를 만들었다.