[Algorithm] 문장의 유사도 분석 - 편집 거리 알고리즘 (Levenshtein Distance)

1. 문장의 유사도

세 문자열을 보자

직관적으로 봐도 "나는 너를 좋아해" 와 "너는 나 좋아하니?"와 유사하고 "오늘 집에 갈거야" 와는 유사하지 않다는 걸 알 수 있다.

우리는 인간이니까 직관적으로 두 문자열이 비슷한지 전혀 다른지 판단할 수 있지만 기계는 직관적으로 판단 할 수 없다. 

두 문자열의 유사도를 어떻게 판단할 수 있을까? Hamming Distance, Smith-Waterman, Sørensen–Dice coefficient 등 있지만 지금은 가장 간단한 Levenshtein Distance을 알아볼 것이다.(사실 문제 풀다가 나와서 정리하는 것)

2. 레벤슈타인 거리(Levenshtein Distance)

레벤슈타인 거리 알고리즘은 두 문자열이 같아지려면 몇번의 문자 조작(삽입, 삭제, 변경)이 필요한지 구하는 것이다.

레벤슈타인 거리 점화식

점화식만 보면 어려우니까 예시로 표현해보자.

두 문자열을 비교하면 문자 조작 비용은 총 6이다.

 

3. 알고리즘

위에서 말한 것 처럼 직관적으로 비용이 6인것을 알 수 있는데, 이를 알고리즘으로 어떻게 구현하는지 알아보자. LCS와 매우 유사하다.

처음 비교 대상은 공집합과 공집합이다. 둘 다 같은 문자열이기 때문에 비용은 0이다. 그 다음은 공집합과 "나" 이다. 공집합이 "나"가 되려면 비용이 1이다. 그 다음은 공집합과 "나는"이다. 마찬가지로 비용이 2가든다. 계속 진행하면 위와 같이 표가 완성된다.

 

이제 "너" 와 공집합 - "나" - "나는" - "나는 "... - "나는 너를 좋아해!"를 비교해보자.

"너"와 공집합을 보자.  '너'가 {}이 되려면 문자를 삭제해야 한다. 그러므로 비용 1

"너"와 "나"를 보자. '너'와 '나'는 서로 다르기 때문에 교체해야 한다. 그러므로 비용 1

"너"와 "나는"을 보자. 길이가 다르기 때문에 추가해야 하고, 교체해야 한다. 그러므로 비용 2

"너"와 "나는 "을 보자. 역시 길이가 다르기 때문에 2개 추가해야 하고, 교체해야 한다. 그러므로 비용 3

"너"와 "나는 너"를 보자. 길이가 다르기 때문에 문자 3개를 추가해야 하지만, '너'는 서로 같기 때문에 그대로 둔다. 그러므로 비용 3

이런식으로 "나는 너를 좋아해!"까지 표를 완성하면 위와 같이 된다.

 

한번만 더 해보자. "너는"과 공집합 - "나" - "나는" - "나는 " - ... - "나는 너를 좋아해!"를 비교해보자

"너는"과 공집합을 비교해보자. "너는"이 {}이 되려면 문자 두개를 삭제해야 한다. 그러므로 비용 2

"너는"과 "나"를 비교해보자. 문자 한개 삭제와 교체가 필요하다. 그러므로 비용 2

"너는"과 "나는"을 비교해보자. '는'은 서로 같고, '너'와 '나'는 다르기 때문에 교체가 필요하다. 그러므로 비용 1

"너는"과 "나는 "을 비교해보자. 추가, 교체가 필요하다. 그러므로 비용 2

 

이런식으로 표를 완성하면 다음과 같이 된다.

쉽게 정리하면

1. 글자가 서로 동일하면 대각선 값을 가져온다
2. 변경이 필요하면 대각선 값에서 + 1을 한다.
3. 삽입이 필요하면 위의 값에서 +1을 한다.
4. 삭제가 필요하면 왼쪽 값에서 +1을 한다.
5. 1~4의 경우에서 최소값을 가져온다.

4. 코드

public class Levenshtein {

  public static int getDistance(String a, String b) {
    int[][] table = new int[a.length() + 1][b.length() + 1];

    for (int i = 1; i <= a.length(); i++) {
      table[i][0] = i;
    }
    for (int j = 1; j <= b.length(); j++) {
      table[0][j] = j;
    }

    for (int i = 1; i <= a.length(); i++) {
      for (int j = 1; j <= b.length(); j++) {
        int insert = table[i - 1][j] + 1;
        int delete = table[i][j - 1] + 1;
        int replace = (a.charAt(i - 1) == b.charAt(j - 1) ? 0 : 1) + table[i - 1][j - 1];
      }
    }

    return table[a.length()][b.length()];
  }
}

5. 예제

www.codewars.com/kata/5259510fc76e59579e0009d4/train/java