Edit Distance

상위 문서: Dynamic Programming

개요

문자열을 비교할 때는 오탈자가 있는 문자열을 고려해야 하는 경우가 있으며, 이를 위해서 근사(approximate) 매칭이 필요하다. 이를 위해서 두 문자열이 얼마나 다른지를 측정하는 척도가 필요하며, 이를 Edit Distance라고 한다. 이는 문자열 A를 문자열 B로 바꾸기 위해 필요한 최소 변경 횟수에 해당한다. Edit Distance는 보통 세 가지 연산을 기반으로 한다:

1. Substitution (치환): 한 글자를 다른 글자로 바꾸기
2. Insertion (삽입): 문자 하나를 새로 삽입
3. Deletion (삭제): 문자 하나 삭제

Simple Recursive Algorithm

Edit Distance 계산은 문자열 뒤에서부터 비교하면서 재귀적으로 해결할 수 있다. 이는 두 문자열 두 문자열 S[1..i], T[1..j]이 있을때 마지막 문자를 비교하여 해결할 수 있다. 만약 비교하는 두 문자가 같으면 비용 증가 없이 이전 문제로 이동한다. 반면 두 문자가 다른 경우에는 substitution을 통해 Edit Distance를 1 증가시킨다.

Recurrence Relation

위에서 설명한 원리를 점화식으로 풀면 아래와 같다:

$D[i,j]$ is minimum of:
• $D[i-1,j-1]$ if $S[i]=T[j]$: 둘이 같으면 비용 추가 안 됨
• $D[i-1,j-1]+1$ if $S[i]\ne T[j]$: 둘이 다르면 substitution 필요
• $D[i,j-1]+1$ for an insertion into $S$: T에서 문자를 하나 가져오는 경우(insertion)
• $D[i-1,j]+1$ for a deletion from $S$: S에서 문자를 하나 버리는 경우(deletion)

Recursive Edit Distance Code

아래는 단순 재귀 기반의 알고리즘을 C 코드로 옮긴 예시이다:

#define MATCH   0      /* enumerated type symbol for match */
#define INSERT  1      /* enumerated type symbol for insert */
#define DELETE  2      /* enumerated type symbol for delete */

int string_compare_r(char *s, char *t, int i, int j) {
    int k;             /* counter */
    int opt[3];        /* cost of the three options */
    int lowest_cost;   /* lowest cost */

    if (i == 0) {      /* indel is the cost of an insertion or deletion */
        return (j * indel(' '));
    }

    if (j == 0) {
        return (i * indel(' '));
    }

    /* match is the cost of a match/substitution */

    opt[MATCH]  = string_compare_r(s, t, i-1, j-1) + match(s[i], t[j]);
    opt[INSERT] = string_compare_r(s, t, i,   j-1) + indel(t[j]);
    opt[DELETE] = string_compare_r(s, t, i-1, j  ) + indel(s[i]);

    lowest_cost = opt[MATCH];

    for (k = INSERT; k <= DELETE; k++) {
        if (opt[k] < lowest_cost) {
            lowest_cost = opt[k];
        }
    }

    return (lowest_cost);
}

Recursive Algorithm Using DP

위에서 구현한 단순한 재귀 알고리즘은 같은 (i, j) 상태를 수백 번, 수천 번 다시 계산한다. 이때 전체 가능한 상태의 수는 $|S|\times |T|$ 뿐인데, 이를 매번 재계산하기 때문에 비효율적이다. 실제로, 단순 재귀 알고리즘을 실제로 구현할 경우 시간 복잡도는 무려 $O(3^{m+n})$이다.

이를 단축시키기 위해 (i, j)를 계산한 값을 테이블에 저장하고, 이를 다시 사용하여 시간을 단축시킬 수 있다. 이는 동적 프로그래밍(DP)을 활용하여 구현될 수 있다. 이를 구현하기 위한 DP 테이블은 2D 배열 m[i][j]으로 구성된다. 테이블의 각 칸에는 그 위치까지 컴퓨팅한 최소 비용(cost)과, 어떤 연산(MATCH/INSERT/DELETE)으로 이 칸에 왔는지 추적하기 위한 포인터(parent)가 저장된다. 이때 parent는 실제 편집 경로(edit sequence)를 복원하는 데에 사용된다. 아래는 해당 자료구조를 C언어 코드로 구현한 예시이다:

typedef struct { 
    int cost;               /* cost of reaching this cell */
    int parent;             /* parent cell */
} cell;

cell m[MAXLEN+1][MAXLEN+1]; /* dynamic programming table */

이때 DP 테이블의 각 칸은 vertex처럼 간주할 수 있으며, (i, j) → (i+1, j), (i, j+1), (i+1, j+1) 방향으로 edge가 존재한다고 할 수 있다. 즉, 이렇게 간주하면 DAG(Directed Acyclic Graph)이므로 topological order(위상 정렬)로 평가할 수 있다. 이는 DP 테이블에 “다음 칸을 계산하려면 이전 칸들이 먼저 계산되어야 한다”는 방향성이 있기 때문에 성립한다.

이때 위의 DP 테이블 인덱스(i, j)를 문자열 인덱스와 동일하게 사용하기 위해서는 문자열의 첫 인덱스에는 아무것도 저장하지 않아야 한다. 예를 들어 문자열 배열 s에 "An"을 저장하고자 한다면 s[0]=, s[1]='A', s[2]='n'과 같이 저장된다.

이 알고리즘이 단순 재귀적인 알고리즘과 구분되는 점은 재귀 알고리즘과 같이 D[i][j]를 계산하기 위해서 D[i−1][j], D[i][j−1], D[i−1][j−1]를 또 재귀 호출하는 대신 배열 lookup을 사용하여 단순히 테이블에 저장된 값을 읽기만 하여 훨씬 빠른 속도를 보장하고, parent 포인터를 저장하여 편집 경로를 복원할 수 있다는 것이다. 또한 goal_cell() 같은 일반화된 함수 사용하여 여러 문제로 이를 확장할 수 있다는 장점이 있다.

Dynamic Programming Edit Distance Code

아래는 동적 프로그래밍을 사용한 알고리즘을 C언어로 구현한 것이다:

int string_compare(char *s, char *t, cell m[MAXLEN+1][MAXLEN+1]) {
    int i, j, k;      /* counters */
    int opt[3];       /* cost of the three options */

    for (i = 0; i <= MAXLEN; i++) {
        row_init(i, m);
        column_init(i, m);
    }

    for (i = 1; i < strlen(s); i++) {
        for (j = 1; j < strlen(t); j++) {

            opt[MATCH]  = m[i-1][j-1].cost + match(s[i], t[j]);
            opt[INSERT] = m[i][j-1].cost   + indel(t[j]);
            opt[DELETE] = m[i-1][j].cost   + indel(s[i]);

            m[i][j].cost   = opt[MATCH];
            m[i][j].parent = MATCH;

            for (k = INSERT; k <= DELETE; k++) {
                if (opt[k] < m[i][j].cost) {
                    m[i][j].cost   = opt[k];
                    m[i][j].parent = k;
                }
            }
        }
    }

    goal_cell(s, t, &i, &j);
    return (m[i][j].cost);
}

Example of Implementation

Figure 는 "thou shalt"를 "you should"로 편집하기 위한 Edit Distance를 구한 결과 DP 테이블이다. 해당 DP 테이블의 값들은 해당 인덱스가 가리키는 부분문자열을 일치시키기 위해서 요구되는 Edit Distance(편집 횟수)를 의미한다. 예를 들어 m[3][2]는 "tho"를 "so"로 편집하기 위해서 요구되는 편집 횟수를 의미한다. 이때 각각의 값들은 두 문자열의 마지막 문자를 서로 비교하며 결정되며 사용되는 식은 아래와 같다: