편집 거리 알고리즘 이해하기

편집 거리 (Edit Distance) 에 대해

단어 “둥굴랭”과 단어 “둥굴레차” 가 오타와 정타 관계 구나 라는 것을 ‘사람’이라면 직관적으로 인지할 수 있다. 하지만 ‘컴퓨터’는 어떻게 판단할 수 있을까? 이렇게 두 문자열 사이의 유사도를 수치화할 수 있는 방법 중의 하나로 편집거리 알고리즘을 사용한다.

편집 거리는 문자열 A 가 문자열 B와 동일하게 되기 위한 최소 변경(삽입, 삭제, 대체) 횟수를 말한다.

 

예를 들어 [둥굴랭] 와 [둥굴레차] 의 편집 거리를 구해보자.

[둥굴랭] 이 [둥굴레차] 가 되기 위해서는

1. ‘랭’을 ‘레’로 대체
2. ‘차’ 는 삭제

하면 [둥굴레차] 가 되므로 이 둘의 편집 거리는 2이다.

※ 편집 거리 알고리즘을 수학자 Vladimir Levenshtein 이 고안했다고 해서 Levenshtein distance 라고도 불린다.

※ 이제부터 ‘문자열 A 가 문자열 B 와 동일하게 되기 위함’이란 의미를 간단하게 A → B 로 표기하겠다.

편집 거리 알고리즘

위키피디아에서 제공하는 편집 거리 알고리즘은 위와 같다. 2차원 배열에 값을 채워넣는 형태이며 위쪽 칸(deletion), 왼쪽 칸(insertion), 대각선 칸(substitution) 값 중 최소값을 취하고 있다. (지금 당장은 이해 안 해도 된다! 아래로 쭉쭉 넘어가자)

이를 그림으로 나타내보면 아래와 같고

다음 2가지 규칙을 활용해 숫자를 채워 넣으며, 우측 하단 값이 구하고자 하는 편집 거리이다.

① 비교하는 글자가 동일하면 대각선 값 그대로

② 비교하는 글자가 다르면 옆,대각선,위 중 최소값 + 1

이제 글을 계속 읽는다면

• 왜 왼쪽은 삽입, 대각선쪽은 치환, 위쪽은 삭제라고 하는지 알 수 있다.
• 왜 글자가 같으면 대각선 위 값을 그대로 가지는지 알 수 있다.
• 왜 글자가 다르면 왼쪽, 대각선쪽, 위쪽 중 최소값에 1을 더하는지 알 수 있다.

알고리즘 이해하기

컴퓨터는 사람과는 다르게 직관적인 판단이란 게 없으므로 모든 경우의 수를 다 따져봐야 한다. 이 와중에 도움을 줄 수 있는 것이 동적 프로그래밍 기법이다. 동적 프로그래밍은 큰 문제를 작은 문제로 쪼갠 후에 작은 문제의 최적화된 답을 찾고 그 답을 기반으로 점차 문제를 확장해 최종적으로 가장 큰 문제의 답을 정의하는 방법이다.

예를 들어 둥굴랭 → 둥굴레차 를 바로 구하기는 어려우니 둥 → 둥 은 최소 몇 번의 단계가 필요하지? 둥 → 둥굴 은 최소 몇 번의 단계가 필요하지? … 이렇게 작은 문제로 시작해 최종적으로 둥굴랭 → 둥굴레차 는 몇 번의 단계가 필요한지 계산하는 방법이다.

편집 거리를 구할 때 2차원 배열을 사용하면 사람이 표현하기도 쉽고 연산에도 용이하다. 2차원 배열을 활용한 둥굴랭 → 둥굴레차 의 편집 거리는 우측 하단의 값인 2 이며, 나머지 값은 해를 구하기 위한 과정일 뿐이다.

숫자의 의미를 이해해보자

숫자들은 1행부터 다음 행씩 행 단위 순으로 채운다. 1행은 둥 → 둥굴레차 여정의 횟수, 2행은 둥굴 → 둥굴레차 여정의 횟수를 의미한다. 1행부터 자세하게 살펴볼까?

1행 채우기

[1]번 칸

• 둥 → 둥 으로 갈 수 있는 최소 단계
• 이미 동일하므로 변경할 것이 없어 0이다.
• 최종 값: 0

[2]번 칸

• 둥 → 둥굴 로 갈 수 있는 최소 단계
• 둥 → 둥 까지는 [1]번 칸 에서 이미 최소 단계가 0이라고 나왔으므로 소거한다. 소거 후: (빈값) → 굴
• (빈값) → 굴 로 가는 방법은 ‘굴’을 삽입하는 한 단계면 되므로 1을 더한다.
• 최종 값: 1 (= 1 + [1]번 칸 값 0)

[3]번 칸

• 둥 → 둥굴레 로 갈 수 있는 최소 단계
• 둥 → 둥굴 까지는 [2]번 칸 에서 이미 최소 단계가 1이라고 나왔으므로 소거한다. 소거 호: (빈값) → 레
• (빈값) → 레 로 가는 방법은 ‘레’를 삽입하는 한 단계면 되므로 1을 더한다.
• 최종 값: 2 (= 1 + [2]번 칸 값 1)

[4]번 칸

• 둥 → 둥굴레차 로 갈 수 있는 최소 단계
• 둥 → 둥굴레 까지는 [3]번 칸 에서 이미 최소 단계가 2이라고 나왔으므로 소거한다. 소거 후: (빈값) → 차
• (빈값) → 차 로 가는 방법은 ‘차’를 삽입하는 한 단계면 되므로 1을 더한다.
• 최종 값: 3 (= 1 + [3]번 칸 값 2)

2행 채우기

[5]번 칸

• 둥굴 → 둥 으로 갈 수 있는 최소 단계
• 둥 → 둥 까지는 [1]번 칸 에서 이미 최소 단계가 0이라고 나왔으므로 소거한다. 소거 후: 굴 → (빈값)
• 굴 → (빈값) 으로 가는 방법은 ‘굴’를 삭제하는 한 단계면 되므로 1을 더한다.
• 최종 값: 1 (= 1 + [1]번 칸 값 0)

[6]번 칸

• 둥굴 → 둥굴 로 갈 수 있는 최소 단계
• [6]번 칸 을 기준으로 왼쪽 ([5]번 칸), 대각선쪽 ([1]번 칸), 위쪽 ([2]번 칸) 칸을 활용해 셋 중 최소 단계를 택한다.
• 왼쪽 ([5]번 칸) 을 활용할 경우
  • 둥굴 → 둥 으로 가는 단계는 1이라고 정해졌으므로 둥굴 → 둥굴 에서 해당 글자를 소거한다. 소거 후: (빈값) → 굴
  • (빈값) → 굴 로 가는 방법은 ‘굴’를 삽입하는 한 단계면 되므로 1을 더한다.
  • 값: 2 (= 1 + [5]번 칸 값 1)
• 대각선쪽 ([1]번 칸) 을 활용할 경우
  • 둥 → 둥 으로 가는 단계는 0이라고 정해졌으므로 둥굴 → 둥굴 에서 해당 글자를 소거한다. 소거 후: 굴 → 굴
  • 굴 → 굴 으로 가는 방법은 이미 동일하므로 변경할 것이 없어 0이다.
  • 값: 0 (= 0 + [1]번 칸 값 0)
• 위쪽 ([2]번 칸) 을 활용할 경우
  • 둥 → 둥굴 로 가는 단계는 1이라고 정해졌으므로 둥굴 → 둥굴 에서 해당 글자를 소거한다. 소거 후: 굴 → (빈값)
  • 굴 → (빈값) 로 가는 방법은 ‘굴’를 삭제하는 한 단계면 되므로 1을 더한다.
  • 값: 2 (= 1 + [2]번 칸 값 1)
• 이 3가지 방법 중 최소를 가지는 방법은 대각선쪽 ([1]번 칸)을 활용하는 경우이다.
• 최종 값: 0 (= 0 + [1]번 칸 값 0)

[7]번 칸

• 둥굴 → 둥굴레 로 갈 수 있는 최소 단계
• [7]번 칸 을 기준으로 왼쪽 ([6]번 칸), 대각선쪽 ([2]번 칸), 위쪽 ([3]번 칸) 칸을 활용해 셋 중 최소 단계를 택한다.
• 왼쪽 ([6]번 칸) **을 활용할 경우
  • 둥굴 → 둥굴 로 가는 단계는 1이라고 정해졌으므로 둥굴 → 둥굴레 에서 해당 글자를 소거한다. 소거 후: (빈값) → 레
  • (빈값) → 레 로 가는 방법은 ‘레’를 삽입하는 한 단계면 되므로 1을 더한다.
  • 값: 1 (= 1 + [6]번 칸 값 0)
• 대각선쪽 ([2]번 칸) 을 활용할 경우
  • 둥 → 둥굴 로 가는 단계는 1이라고 정해졌으므로 둥굴 → 둥굴레 에서 해당 글자를 소거한다. 소거 후: 굴 → 레
  • 굴 → 레 로 가는 방법은 ‘굴’을 ‘레’ 로 치환하는 한 단계면 되므로 1을 더한다.
  • 값: 2 (= 1 + [2]번 칸 값 1)
• 위쪽 ([3]번 칸) 을 활용할 경우
  • 둥 → 둥굴레 로 가는 단계는 2이라고 정해졌으므로 둥굴 → 둥굴레에서 해당 글자를 소거한다. 소거 후: 굴 → (빈값)
  • 굴 → (빈값) 으로 가는 방법은 ‘굴’를 삭제하는 한 단계면 되므로 1을 더한다.
  • 값: 3 (= 1 + [3]번 칸 값 2)
• 이 3가지 방법 중 최소를 가지는 방법은 왼쪽 ([6]번 칸) 을 활용하는 경우이다.
• 최종 값: 1 (= 1 + [6]번 칸 값 0)

[8]번 칸 부터는 반복되는 내용에 길이가 너무 길어질거 같으니 직접 구해보자..!

이제 규칙을 찾아보자

● [6]번 칸 과 [7]번 칸 을 구하는 과정을 살펴보면, 방향과 변경 방법이 일관됨을 확인할 수 있다.

• 왼쪽 칸을 활용하면, 삽입이다.
• 대각선쪽 칸을 활용하면, 치환이다.
• 위쪽 칸을 활용하면, 삭제다.

⇒ 왼쪽은 삽입, 대각선쪽은 치환, 위쪽은 삭제

● 비교하는 글자가 같으면, 해당 글자는 이미 동일하므로 변경할 것이 없어 0이다. 행과 열이 동일한 칸(M[i, i])은 대각선 위가 최소값이므로 최종값 = 0 + 대각선 위쪽 칸 값 이 되어 대각선 위쪽 값을 그대로 따라간다.

⇒ 비교하는 글자가 같으면 대각선 위 값을 그대로 가짐

● 비교하는 글자가 다르면, 이미 작은 문제를 해결한 왼쪽, 대각선위쪽, 위쪽 값에 한 단계(삽입, 치환, 삭제) 를 추가로 해주므로 그 중 최소값 +1 이 해당 칸의 최종값이다.

⇒ 비교하는 글자가 다르면 왼쪽, 대각선쪽, 위쪽 중 최소값에 1을 더함

편집 거리 알고리즘은 띡하고 나온게 아니라 위의 규칙들을 수식이나 코드로 옮겨놓은 것 뿐이다.

편집 거리 알고리즘 구현 (JAVA)

public static int getEditDistance(char[] fromChar, char[] toChar) {
        int fromSize = fromWord.length();
        int toSize = toWord.length();
        int[][] matrix = new int[fromSize][toSize];

        matrix[0][0] =  fromChar[0] == toChar[0] ? 0 : 1;

        for (int i = 1; i < fromSize; i++) {
            matrix[i][0] = matrix[i-1][0] + 1;
        }

        for (int i = 1; i < toSize; i++) {
            matrix[0][i] = matrix[0][i-1] + 1;
        }

        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[i].length; j++) {
                if(fromChar[i] == toChar[j]) {
                    matrix[i][j] = matrix[i-1][j-1];
                    continue;
                }
                matrix[i][j] = Math.min(matrix[i-1][j-1]+1, Math.min(matrix[i-1][j]+1, matrix[i][j-1]+1));
            }
        }
        return matrix[fromSize-1][toSize-1];
    }

※ 위키피디아 알고리즘을 100% 동일하게 구현한 것은 아니나 편집 거리 알고리즘을 표현하는 방법은 동일하다.

 

레퍼런스

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

https://lovit.github.io/nlp/2018/08/28/levenshtein_hangle/

https://madplay.github.io/post/levenshtein-distance-edit-distance

편집 거리 알고리즘 이해하기

글 읽어주셔서 언제나 감사합니다. 좋은 피드백, 개선 피드백 너무나도 환영합니다.