Edit Distance 문서 원본 보기

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]
상위 문서: [[Dynamic Programming]] 

==개요==
문자열을 비교할 때는 오탈자가 있는 문자열을 고려해야 하는 경우가 있으며, 이를 위해서 근사(approximate) 매칭이 필요하다. 이를 위해서 두 문자열이 얼마나 다른지를 측정하는 척도가 필요하며, 이를 Edit Distance라고 한다. 이는 문자열 A를 문자열 B로 바꾸기 위해 필요한 최소 변경 횟수에 해당한다. Edit Distance는 보통 세 가지 연산을 기반으로 한다: 
# Substitution (치환): 한 글자를 다른 글자로 바꾸기<ref>예를 들어, shot → spot의 경우는 ‘g’를 삽입하므로 Insertion 1회에 해당한다.</ref>
# Insertion (삽입): 문자 하나를 새로 삽입<ref>예를 들어, ago → agog의 경우는 ‘h’를 ‘p’로 바꾸므로 Substitution 1회에 해당한다.</ref>
# Deletion (삭제): 문자 하나 삭제<ref>예를 들어, hour → our의 경우는 ‘h’ 삭제 → Deletion 1회에 해당한다.</ref>

==Simple Recursive Algorithm==
Edit Distance 계산은 문자열 뒤에서부터 비교하면서 재귀적으로 해결할 수 있다. 이는 두 문자열 두 문자열 S[1..i], T[1..j]이 있을때 마지막 문자를 비교하여 해결할 수 있다. 만약 비교하는 두 문자가 같으면 비용 증가 없이 이전 문제로 이동한다.<ref>(s[1..i-1], t[1..j-1])에 해당한다.</ref> 반면 두 문자가 다른 경우에는 substitution을 통해 Edit Distance를 1 증가시킨다.<ref>혹은 S에 문자를 추가하거나 삭제하는 방식을 취할 수도 있다.</ref> 

===Recurrence Relation===
위에서 설명한 원리를 점화식으로 풀면 아래와 같다:
 <math>D[i, j]</math> is minimum of:
 • <math>D[i - 1, j - 1]</math> if <math>S[i] = T [j]</math>: 둘이 같으면 비용 추가 안 됨
 • <math>D[i - 1, j - 1] + 1</math> if <math>S[i] \ne T [j]</math>: 둘이 다르면 substitution 필요
 • <math>D[i, j - 1] + 1</math> for an insertion into <math>S</math>: T에서 문자를 하나 가져오는 경우(insertion)
 • <math>D[i - 1, j] + 1</math> for a deletion from <math>S</math>: S에서 문자를 하나 버리는 경우(deletion)

===Recursive Edit Distance Code===
아래는 단순 재귀 기반의 알고리즘을 C 코드로 옮긴 예시이다:
<syntaxhighlight lang="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);
}
</syntaxhighlight>

==Recursive Algorithm Using DP==
위에서 구현한 단순한 재귀 알고리즘은 
<syntaxhighlight lang="c">
</syntaxhighlight>
<syntaxhighlight lang="c">
</syntaxhighlight>
<syntaxhighlight lang="c">
</syntaxhighlight>
<syntaxhighlight lang="c">
</syntaxhighlight>
<syntaxhighlight lang="c">
</syntaxhighlight>

==각주==