Levenshtein Distance

Levenshtein Distance는 한 문자열을 다른 문자열로 바꿀 때 몇 번의 변경이 필요한지를 측정하는 방식이다. 예를 들어, 새끼 고양이를 뜻하는 kitten을 앉아있다는 sitting으로 변경하기 위해서는

kitten → sitten : 첫번째 문자 k를 s로 변경

sitten → sittin  : 끝에서 2번째 문자인 e를 i로 변경

sittin → sitting : 마지막으로 g를 문자열 마지막에 추가

과 같은 과정을 거치게됨으로 Levenshtein Distance는 3이 된다. 

Levenshtein Distance를 구하기 위해서는 2차원 배열를 이용하는데, 첫번째 Row에 문자열 하나를 (여기서는 kitten)을, 첫번째 Column에 다른 문자를 (여기서는 sitting)을 순차적인 숫자로 변환하여 입력한다.

다음 s와 kitten에 대한 거리를 계산한다.

먼저 (s,k)는 같은 문자가 아니므로 (s,k) 셀의 왼쪽, 위, 그리고 왼쪽/위 대각선의 값에 1을 더한 값 중에 최소 값을 입력한다. (s,k) cell의 왼쪽 cell과 위쪽 cell 값은 2, 왼쪽/위 대각선은 1이 됨으로 1을 입력한다.

  (s,i) cell 역시 두 문자가 같지 않으므로, (2,3,2) 중에 최소값인 2가 된다.  동일한 방법으로 나머지 cell의 값을 입력한다.

그런데, (i,i) cell의 경우, 두 문자가 동일하기에 왼쪽/위 대각선 값을 입력한다. 여기서는 1이 된다.

완성된 배열은 다음과 같다.

완성된 배열에서 Levenshtein Distance는 마지막 cell인 (g,n)의 값이 된다. 3....

다음은 Wikipedia에 있는 Levenshtein Distance (http://en.wikipedia.org/wiki/Levenshtein_distance)를 구하는 알고리즘이다.

int LevenshteinDistance(char s[1..m], char t[1..n])

{

    // for all i and j, d[i,j] will hold the Levenshtein distance between

    // the first i characters of s and the first j characters of t;

    // note that d has (m+1)x(n+1) values

    declare int d[0..m, 0..n]

    for i from 0 to m

        d[i, 0] := i // the distance of any first string to an empty second string

    for j from 0 to n

        d[0, j] := j // the distance of any second string to an empty first string

    for j from 1 to n {

        for i from 1 to m {

            if s[i] = t[j] then  

                d[i, j] := d[i-1, j-1]       // no operation required

            else

                d[i, j] := minimum (

                                d[i-1, j] + 1,  // a deletion

                                d[i, j-1] + 1,  // an insertion

                                d[i-1, j-1] + 1 // a substitution

                            )

        }

    }

    return d[m,n]

}

위의 알고리즘에서 보듯이 Levenshtein Distance를 구하기 위한 Time Complexity O(m*n)이 되겠다.