Levenshtein Distance

Levenshtein Distance이란 무엇인가?

Levenshtein Distance(이하 LD)는 두 문자열의 비슷한 정도를 측정하기위해 고안되었습니다.
여기서 원문자열을 (s)로, 대상문자열을 (t) 라고 나타낸다고 하겠습니다. distance란 s를
t로 변형시키기 위해 삭제, 추가, 또는 수정이 필요한 횟수를 뜻합니다. 예를든다면,

* s가 "test"이고 t도 "test"라면, LD(s,t) = 0 이 됩니다. 왜냐하면 문자열들이 이미 동일하여 변환이 필요하지 않기 때문입니다.

* s가 "test"이고 t가 "tent"라면, LD(s,t) = 1 이 됩니다. 왜냐하면 s를 t로 만들기 위해서는 "s"를 "n"으로 한번 수정이 필요하기 때문입니다.

Levenshtein distance는 string 간의 차이가 클수록 위대함을 느낄 수 있습니다.

Levenshtein distance는 러시아 과학자인 Vladimir Levenshtein가 1965년에 고안하여 그렇게 이름지어졌습니다.
Levenshtein 이란 단어가 쓰거나 읽기 힘들기 때문에 종종 edit distance라고도 불립니다.

Levenshtein distance 알고리즘은 다음과 같은 분야에 쓰여집니다:

* 철자 검사
* 음성 인식
* DNA 분석
* 표절여부 검사

알고리즘 설명

1
s의 문자열 길이를 n에 넣는다.
t의 문자열의 길이를 m에 넣는다.
만약 n = 0 이라면, m 을 리턴하고 종료한다.
만약 m = 0 이라면, n 을 리턴하고 종료한다.
0..m 행과, 0..n 열로 이루어진 행열을 만든다.
2
첫번째 행인 0..n을 초기화 한다.
첫번째 열인 0..m을 초기화 한다.
3
s의 각 문자(i는 1부터 n까지)를 검사한다.
4
t의 각 문자(j는 1부터 m까지)를 검사한다.
5
s[i]와 t[j]가 같다면, 변경하기 위한 비용은 0이 된다.
s[i]와 t[j]가 같지 않다면, 비용은 1이 된다.
6
행열의 셀 d[i,j]에 다음의 것들 중 가장 작은 값을 넣는다.
a. 바로 위의 셀이 더하기 1이 되는 경우: d[i-1, j] + 1
b. 바로 왼쪽 셀이 더하기 일이 되는 경우: d[i,j-1] + 1
c. 대각선으로 연속적인, 바로 왼,위쪽 셀의 비용: d[i-1,j-1] + cost
7
(3, 4, 5, 6) 단계를 반복하여 완료되면, d[n, m]셀에 있는 것이 distance가 된다.

참고문헌(?)

* http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit.html (Lloyd Allison)
* http://www.cut-the-knot.com/do_you_know/Strings.html (Alex Bogomolny)
* http://www-igm.univ-mlv.fr/~lecroq/seqcomp/node2.html (Thierry Lecroq)

실제 소스

 public static int getLevenshteinDistance (String s, String t) {
    if (s == null || t == null) {
      throw new IllegalArgumentException("Strings must not be null");
    }
   
    /*
      The difference between this impl. and the previous is that, rather
       than creating and retaining a matrix of size s.length()+1 by t.length()+1,
       we maintain two single-dimensional arrays of length s.length()+1.  The first, d,
       is the 'current working' distance array that maintains the newest distance cost
       counts as we iterate through the characters of String s.  Each time we increment
       the index of String t we are comparing, d is copied to p, the second int[].  Doing so
       allows us to retain the previous cost counts as required by the algorithm (taking
       the minimum of the cost count to the left, up one, and diagonally up and to the left
       of the current cost count being calculated).  (Note that the arrays aren't really
       copied anymore, just switched...this is clearly much better than cloning an array
       or doing a System.arraycopy() each time  through the outer loop.)
       Effectively, the difference between the two implementations is this one does not
       cause an out of memory condition when calculating the LD over two very large strings.   
    */ 
   
    int n = s.length(); // length of s
    int m = t.length(); // length of t
   
    if (n == 0) {
      return m;
    } else if (m == 0) {
      return n;
    }
    int p[] = new int[n+1]; //'previous' cost array, horizontally
    int d[] = new int[n+1]; // cost array, horizontally
    int _d[]; //placeholder to assist in swapping p and d
    // indexes into strings s and t
    int i; // iterates through s
    int j; // iterates through t
    char t_j; // jth character of t
    int cost; // cost
    for (i = 0; i<=n; i++) {
       p[i] = i;
    }
   
    for (j = 1; j<=m; j++) {
       t_j = t.charAt(j-1);
       d[0] = j;
   
       for (i=1; i<=n; i++) {
          cost = s.charAt(i-1)==t_j ? 0 : 1;
          // minimum of cell to the left+1, to the top+1, diagonally left and up +cost   
          d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1),  p[i-1]+cost);
       }
       // copy current distance counts to 'previous row' distance counts
       _d = p;
       p = d;
       d = _d;
    }
   
    // our last action in the above loop was to switch d and p, so p now
    // actually has the most recent cost counts
    return p[n];
  }

 public static int getDifference(String a, String b)
 {
     // Minimize the amount of storage needed:
     if (a.length() > b.length())
     {
         // Swap:
         String x = a;
         a = b;
         b = x;
     }
 
     // Store only two rows of the matrix, instead of a big one
     int[] mat1 = new int[a.length() + 1];
     int[] mat2 = new int[a.length() + 1];
 
     int i;
     int j;
 
     for (i = 1; i <= a.length(); i++)
         mat1[i] = i;
 
     mat2[0] = 1;
 
     for (j = 1; j <= b.length(); j++)
     {
         for (i = 1; i <= a.length(); i++)
         {
                 int c = (a.charAt(i - 1) == b.charAt(j - 1) ? 0 : 1);
 
                 mat2[i] =
                         Math.min(mat1[i - 1] + c,
                         Math.min(mat1[i] + 1, mat2[i - 1] + 1));
         }
 
         // Swap:
         int[] x = mat1;
         mat1 = mat2;
         mat2 = x;
 
         mat2[0] = mat1[0] + 1;
     }
 
     // It's row #1 because we swap rows at the end of each outer loop,
     // as we are to return the last number on the lowest row
     return mat1[a.length()];
 }

public class Distance {
    //****************************
    // Get minimum of three values
    //****************************
    private int Minimum (int a, int b, int c) {
    int mi;
      mi = a;
      if (b < mi) {
        mi = b;
      }
      if (c < mi) {
        mi = c;
      }
      return mi;
    }
    //*****************************
    // Compute Levenshtein distance
    //*****************************
    public int LD (String s, String t) {
    int d[][]; // matrix
    int n; // length of s
    int m; // length of t
    int i; // iterates through s
    int j; // iterates through t
    char s_i; // ith character of s
    char t_j; // jth character of t
    int cost; // cost
      // Step 1
      n = s.length ();
      m = t.length ();
      if (n == 0) {
        return m;
      }
      if (m == 0) {
        return n;
      }
      d = new int[n+1][m+1];
      // Step 2
      for (i = 0; i <= n; i++) {
        d[i][0] = i;
      }
      for (j = 0; j <= m; j++) {
        d[0][j] = j;
      }
      // Step 3
      for (i = 1; i <= n; i++) {
        s_i = s.charAt (i - 1);
        // Step 4
        for (j = 1; j <= m; j++) {
          t_j = t.charAt (j - 1);
          // Step 5
          if (s_i == t_j) {
            cost = 0;
          }
          else {
            cost = 1;
          }
          // Step 6
          d[i][j] = Minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);
        }
      }
      // Step 7
      return d[n][m];
    }
  }

Levenshtein Distance 알고리즘의 정의와 설명과 참고문헌은 Progh2's 블로그에서 옮겨왔고
실제소스는 Daniel님의 노트에서 옮겨왔습니다. ^^;