Levenshtein distance

Levenshtein Distance란?

wikipedia에서는 아래와 같이 정의하고 있다.

Ininformation theoryandcomputer science, theLevenshtein distanceis astring metricfor measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (i.e. insertions, deletions or substitutions) required to change one word into the other. It is named afterVladimir Levenshtein, who considered this distance in 1965.[1] Levenshtein distance may also be referred to asedit distance, although that may also denote a largerfamily of distance metrics.[2]:32It is closely related topairwise string alignments.

요약 해 보면 두 문자열의 차이를 측정하는 방법이라고 소개하고 있다.

거리를 구하는 방법은 간단하다. 

하나의 문자열에서 한 글자씩 문자를 추가, 삭제, 변경을 하면서 다른 문자열로 변환해 가며 몇 단계가 걸리는 지를 구하는 것이다.

예를 들어보자.

kitten과 sitting의 편집 거리를 구한다면…

1. kitten —> sitten : k를 s로 변환
2. sitten —> sittin : e를 i로 변환
3. sittin —> sitting : g를 추가

위 단계를 거쳐 편집 거리는 3이 된다.(이 외에도 여러 가지 경우가 있으나 최소값은 3이다.)

정의는 아래와 같다.(wikipedia 참고)

뭔가 수식이 어려워 보이지만 사실은 간단하다. 아래 표를 확인해 보자.

min 항목에 아래와 같이 3가지 의미는 다음과 같다(i가 세로, j가 가로인 경우)

• lev(i-1, j) + 1: 삭제
• lev(i, j-1) + 1: 추가
• lev(i-1, j-1) + 1: 수정

min(i, j)가 0인 경우는 max(i, j)이다. 이 의미는 무엇일까? i 또는 j 중 0이라면 이는 i 또는 j 중 큰 값이 편집 거리가 된다는 의미이다.

즉, “”(빈 문자열)과 “abcd”라는 문자의 편집 거리는 4로 “abcd” 문자열의 길이가 되는 것이다.

구현

편집 거리를 계산하는 방법을 구현해보자.

wikipedia에서 재귀호출(Recursive)을 이용하는 방법과 full matrix를 이용하는 방법을 제시하고 있다.

재귀호출(Recursive)

public int getDistance(String first, int i, String second, int j) {     if (i == 0) {         return j;     } else if (j == 0) {         return i;     }     int cost = 0;     if (first.charAt(i - 1) != second.charAt(j - 1)) {         cost = 1;     }     return minimum(             getDistance(first, i-1, second, j) + 1,             getDistance(first, i, second, j-1) + 1,             getDistance(first, i-1, second, j-1) + cost     ); }

Full Matrix

2차원 배열을 활용하였다. 1차원 배열을 사용해서도 사용이 가능하다. 한 줄 중에 min 값만 유지하면 되기 때문이다.

public int getDistance(String first, String second) {     if (StringUtils.equals(first, second)) {         return 0;     } else if (StringUtils.isEmpty(first)) {         return second.length();     } else if (StringUtils.isEmpty(second)) {         return first.length();     }     int[][] dist = new int[first.length() + 1][second.length() + 1];     for (int i = 0; i < first.length() + 1; i++) {  //좌측변 초기화         dist[i][0] = i;     }     for (int j = 0; j < second.length() + 1; j++) { //상단 초기화         dist[0][j] = j;     }     for (int i = 1; i < first.length() + 1; i++) {         for (int j = 1; j < second.length() + 1; j++) {             if (first.charAt(i - 1) == second.charAt(j - 1)) {                 dist[i][j] = dist[i - 1][j - 1];             } else {                 dist[i][j] = minimum(                         dist[i - 1][j] + 1,                         dist[i][j - 1] + 1,                         dist[i -1][j - 1] + 1                         );             }         }     }     return dist[first.length()][second.length()]; }

결론

Recursive와 Full Matrix 사이에 성능 처이가 있을지는 확인하진 않았으나 구글링을 해보면 Full Matrix가 빠르다고 한다. 두 방법 모두 입력된 문자열 모두를 읽어야 하기 때문에 복잡도 상으로는 차이가 없을 것이다. 아마도 그 차이는 재귀호출에 따른 overhead 때문이 아닐까 생각해 본다.

참고로 commons-lang3을 사용한다면, StringUtils.getLevenshteinDistance()로 구현되어 있다.

내부 로직은 1차원 배열을 사용하여 구현하고 있다.(아마도 메모리 공간을 좀 더 적게 사용하기 위함이라고 생각된다.)

알고리즘도 중요하지만 Levenshtein Distance를 어디에 활용할 수 있을까?

잘은 모르겠지만 검색 키워드 보정에도 쉽게 사용해 볼 수 있지 않을까? 오타 같은 것을 표준 단어로 변경해 준다거나 하는 식으로 말이다.

어떤 곳은 짧은 댓글을 달 수 있는 게시판에서 도배 댓글을 구분할 때 사용하기도 한다는 말을 들었다.

정확히 어느 곳에 활용하면 좋을지는 잘 모르겠다.

github: https://github.com/tomining/AlgorithmStudy/blob/master/src/main/java/com/algorithm/distance/LevenshteinDistance.java

TC: https://github.com/tomining/AlgorithmStudy/blob/master/src/test/java/com/algorithm/distance/LevenshteinDistanceTest.java

---

참고

• https://en.wikipedia.org/wiki/Levenshtein_distance
  
• http://hsp1116.tistory.com/41
  
• http://yceffort.com/archives/360