Levenshtein Distance(Edit Distance, 편집 거리 알고리즘)

Levenshtein Distance 는 두 문자열간의 형태적 유사도를 계산하는 알고리즘이예요.

 

별명은 Edit Distance 로 편집 거리 알고리즘이라고도 불려요.

 

소련의 수학자인 Vladimir Levenshtein 이 1965년도에 고안한 알고리즘이라고 합니다.

 

https://en.wikipedia.org/wiki/Levenshtein_distance

Levenshtein distance - Wikipedia

 

 

 

Levenshtein Distance 는 두 문자열 s1, s2 에 대하여 s1 을 s2 로 바꾸기 위해 삽입(insert), 삭제(delete), 수정(modify) 연산을 얼마나 수행했는지를 통해 두 문자열 간의 유사도를 측정해요.

 

삽입, 삭제, 수정에 대한 연산은 아래와 같아요.

 

 

삽입(insert)

 

s1 : ab
s2 : abc

 

인 경우, s1 에 c 를 삽입함으로써 두 문자열은 같아질 수 있다.

 

여기서 Levenshtein Distance 는 1이 된다.

 

 

삭제(delete)

 

s1 : wxyz
s2 : xy

 

인 경우, s1 에서 w 와 z 를 삭제함으로써 두 문자열은 같아질 수 있다.

 

여기서 Levenshtein Distance 는 2가 된다.

 

 

수정(modify)

 

s1 : pqr
s2 : pwr

 

인 경우, s1 에서 q 를 w 로 수정함으로써 두 문자열은 같아질 수 있다.

 

여기서 Levenshtein Distance 는 1이 된다.

 

 

 

Levenshtein Distance 는 Dynamic Programming 을 이용하여 구현하는데요.

 

Dynamic Programming 은 티끌 모아 태산 이라고 볼 수 있을 것 같아요.

(줄여서 DP 라고 부를께요)

 

점화식을 이용해서 작은 문제를 해결하고 얻은 결과값들을 모아서 결국에는 풀어야 되는 큰 문제를 해결하는 알고리즘이예요.

 

Levenshtein Distance 을 어떻게 DP로 구현하는지 먼저 그림으로 알아볼게요.

 

아래는 입력값으로 주어진 두 문자열이예요.

 

s1 => abcdab
s2 => acbdcf

 

DP 는 표를 그려서 생각해보면 큰 도움이 되는데요. 표에 정리해보면 아래와 같아요.

 

표에서 0행과 0열은 문자가 없는 빈 문자열을 의미해요.

 

그리고 (0, 0) 은 0으로 초기화 해줍니다.

 

0 열은 's1 문자열'에서 '빈 문자열'로 만드는 연산의 횟수를 의미하는데요.

 

한 마디로 삭제연산을 몇 번 수행했는지를 입력해주면 되요.

0 행은 '빈 문자열' 에서 's2 문자열'로 만드는 연산의 횟수를 의미해요.

 

삽입연산을 몇 번 수행했는지를 입력해주면 되겠죠.

 

 

이렇게 해서 0 행과 0 열의 초기화가 끝났어요.

 

그러면 이제 d[row][col] 의 값을 구하는 점화식을 세워야 하는데요.

 

먼저 s1[row-1] 의 값과 s2[col-1] 의 값이 같은 경우와 다른 경우를 나눠서 봐야해요.

 

s1[row-1] == s2[col-1]

 

비교하는 두 문자가 같은 경우엔 연산을 수행할 필요가 없기 때문에 d[row-1][col-1] 를 그대로 가져와요.

 

d[row][col] = d[row-1][col-1]

 

s1[row-1] != s2[col-1]

 

비교하는 두 문자가 다른 경우에는 연산을 수행해줘야 하는데요.

 

여기서 최소연산을 구하는 것이기 때문에 총 연산 횟수가 적은 값을 선택합니다.

 

1. 삽입(insert) : d[row][col - 1] + 1
2. 삭제(delete) : d[row - 1][col] + 1
3. 수정(modify) : d[row - 1][col - 1] + 1

위 세 연산의 값 중 가장 작은 값을 d[row][col] 에 초기화해줍니다.

 

 

 

(1, 1) 을 보면 비교하는 s1, s2 의 문자가 둘 다 a 예요.

 

그래서 연산을 해 줄 필요가 없고 (0, 0) 에 있는 값을 그대로 가져와요.

 

 

(1, 2) 를 볼까요 s1 은 a 이고 s2 는 c 인데요. 두 문자가 다르기 때문에 연산을 해줘야하는 걸 알 수 있어요.

 

그러면 삽입, 삭제, 수정 세 연산에 대한 총 연산횟수를 구해보면 각각

 

  - 삽입 : 1 (d[1][1] + 1)

  - 삭제 : 3 (d[0][2] + 1)

  - 수정 : 2 (d[0][1] + 1)

 

로 삽입 연산을 수행한 총 연산횟수 1로 세팅해줍니다.

 

이와 마찬가지로 1행에 대해 연산을 수행해주면 아래와 같이 계산되요.

 

1열에 대해서도 연산을 적용해보면 아래와 같이 계산됩니다.

이렇게 행과 열을 번갈아가며 모두 채우면 (6, 6) 까지 계산이 끝나게 되는데요.

 

그 결과는 아래와 같아요.

 

맨 오른쪽 아래에 있는 값이 DP를 통해 구하는 값인데요.

 

이렇게 Levenshtein Distance 결과로 4를 얻었습니다.

 

적용된 연산을 보면 수정만 4번이 수행된 것을 알 수 있어요.

 

s1 : abcdab -> s2 : acbdcf

 

 

 

아래는 알고리즘을 구현한 코드예요. 

 

public class Main {
    public static void main(String[] args) {
        String s1 = "abcdab";
        String s2 = "acbdcf";

        int[][] editDistance = new int[s1.length() + 1][s2.length() + 1];

        // 0열 초기화 (원본문자열 -> 공백 연산횟수)
        for(int row=1;row<s1.length() + 1;row++) {
            editDistance[row][0] = row;
        }

        // 0행 초기화 (공백 -> 목표문자열 연산횟수)
        for(int col=1;col<s2.length() + 1;col++) {
            editDistance[0][col] = col;
        }

        for(int row = 1; row < s1.length() + 1; row++) {
            for (int col = 1; col < s2.length() + 1; col++) {
                // Skip
                if(s1.charAt(row-1) == s2.charAt(col-1)) {
                    editDistance[row][col] = editDistance[row-1][col-1];
                }
                // Modify
                else {
                    editDistance[row][col] = editDistance[row-1][col-1] + 1;
                }
                // Insert
                if(editDistance[row][col-1] + 1 < editDistance[row][col]) {
                    editDistance[row][col] = editDistance[row][col-1] + 1;
                }
                // Delete
                if(editDistance[row - 1][col] + 1 < editDistance[row][col]) {
                    editDistance[row][col] = editDistance[row - 1][col] + 1;
                }
            }
        }

        print(editDistance, s1, s2);
        System.out.print(editDistance[s1.length()][s2.length()]);
    }

    public static void print(int[][] editDistance, String s1, String s2) {
        for(int row = 0; row < s1.length() + 1; row++) {
            for (int col = 0; col < s2.length() + 1; col++) {
                System.out.print(editDistance[row][col]);
            }
            System.out.println();
        }
        System.out.println();
    }
}

 

이렇게 Levenshtein Distance 에 대해서 알아보았습니다.

 

끝까지 읽어주셔서 감사합니다.