[ 개념 ] 50. Levenshtein(편집 거리) 알고리즘

> Levenshtein 알고리즘

---

편집 거리 알고리즘 (edit distance)

Levenshtein distance 는 string 간 형태적 유사도를 정의하는 척도입니다. 만약 우리가 단어 사전을 가지고 있고, 사전에 등록되지 않은 단어가 발생한다면 Levenshtein distance 가 가장 가까운 단어로 치환함으로써 오탈자를 교정할 수 있습니다. 그러나 Levenshtein distance 는 계산 비용이 비쌉니다. 이 때 간단한 inverted index 를 이용하여 비슷할 가능성이 있는 단어 후보만을 추린 뒤 몇 번의 Levenshtein distance 를 계산함으로써 효율적으로 오탈자를 교정할 수 있습니다.

String 간의 형태적 유사도를 정의하는 척도를 string distance 라 합니다. Edit distance 라는 별명을 지닌 Levenshtein distance 는 대표적인 string distance 입니다.

Levenshtein distance 는 한 string s1s1 을 s2s2 로 변환하는 최소 횟수를 두 string 간의 거리로 정의합니다. s1s1 = ‘꿈을꾸는아이’ 에서 s2s2 = ‘아이오아이’ 로 바뀌기 위해서는 (꿈을꾸 -> 아이오) 로 바뀌고, 네번째 글자 ‘는’ 이 제거되면 됩니다. Levenshtein distance 에서는 이처럼 string 을 변화하기 위한 edit 방법을 세 가지로 분류합니다

1. delete: ‘점심을먹자 →→ 점심먹자’ 로 바꾸기 위해서는 을 을 삭제해야 합니다.
2. insert: ‘점심먹자 →→ 점심을먹자’ 로 바꾸기 위해서는 반대로 을 을 삽입해야 합니다.
3. substitution: ‘점심먹자 →→ 점심먹장’ 로 바꾸기 위해서는 자를 장 으로 치환해야 합니다.

이를 위해 동적 프로그래밍 (dynamic programming) 이 이용됩니다. d[0,0] 은 s1,s2s1,s2 의 첫 글자가 같으면 0, 아니면 1로 초기화 합니다. 글자가 다르면 substitution cost 가 발생한다는 의미입니다. 그리고 그 외의 d[0,j]에 대해서는 d[0,j] = d[0,j-1] + 1 의 비용으로 초기화 합니다. 한글자씩 insertion 이 일어났다는 의미입니다. 이후에는 좌측, 상단, 좌상단의 값을 이용하여 거리 행렬 d 를 업데이트 합니다. 그 규칙은 아래와 같습니다.

d[i,j] = Math.min(d[i-1,j] + deletion cost, Math.min(d[i,j-1] + insertion cost, d[i-1,j-1] + substitution cost)

예를 들어 "FLOMAX"와 "VOLMAX" 사이의 Levenshtein 거리는 3입니다. 세 가지 편집이 하나씩 이루어지고 그 미만으로 편집할 수 있는 방법이 없기 때문입니다.

"GILY"와 "GELLY"사이의 Levenshtein 거리는 2입니다.

"HONDA"와 "HYUNDAI" 사이의 Levenshtein 거리는 3입니다.

Dynamic Programming으로 접근

이 Levenshtein 알고리즘은 다른 문자열을 얻기 위해 한 문자열을 수정하는 데 필요한 최소 편집 작업 수를 계산합니다. 이를 계산하는 가장 일반적인 방법은 동적 프로그래밍 방식입니다.

1. 행렬은 (m, n) 셀에서 하나의 m- 문자 접두사와 다른 단어의 n- 접두사 사이의 Levenshtein 거리를 측정하여 초기화됩니다.
2. 매트릭스는 왼쪽 상단에서 오른쪽 하단 모서리까지 채울 수 있습니다.
3. 각각의 수평 또는 수직 점프는 각각 삽입 또는 삭제에 해당합니다.
4. 비용은 일반적으로 각 작업에 대해 1로 설정됩니다.
5. 행과 열의 두 문자가 일치하면 0과 일치하지 않으면 대각선 점프는 하나의 비용이 발생할 수 있습니다. 각 셀은 항상 로컬 비용을 최소화합니다.
6. 이렇게하면 오른쪽 아래 모서리에있는 숫자가 두 단어 사이의 Levenshtein 거리입니다.

"HONDA"와 "HYUNDAI"를 비교 해보겠습니다.

이제 Levenshtein 알고리즘을 자바코드로 구현해봅시다.

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int n, m = 0;
    static long dist[][];
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        dist = new long[n + 1][m + 1];

        String input = br.readLine();
        String answer = br.readLine();

        long cnt = levenshtein(input, answer);
        System.out.println(cnt);
    }

    static long levenshtein(String origin, String pattern) {
        for (int i = 1; i <= origin.length(); ++i) {
            dist[i][0] = i;
        }
        for (int j = 1; j <= pattern.length(); ++j) {
            dist[0][j] = j;
        }

        for (int j = 1; j <= pattern.length(); ++j) {
            for (int i = 1; i <= origin.length(); ++i) {
                if (origin.charAt(i - 1) == pattern.charAt(j - 1)) {
                    dist[i][j] = dist[i - 1][j - 1];
                } else {
                    dist[i][j] = Math.min(dist[i - 1][j - 1] + 1, Math.min(dist[i][j - 1] + 1, dist[i - 1][j] + 1));
                }
            }
        }
        return dist[origin.length()][pattern.length()];
    }
}

사용 사례

대부분의 문자열 매칭에서 우리의 목표는 적은 수의 차이가 예상되는 상황에서 긴 텍스트에서 짧은 문자열에 대한 일치여부를 찾는 것입니다. 예를 들어 문자열 중 하나는 일반적으로 짧고 다른 하나는 임의로 깁니다. 여기에는 맞춤법 검사기, 광학 문자 인식을위한 수정 시스템 및 번역 메모리를 기반으로 한 자연어 번역을 지원하는 소프트웨어와 같은 광범위한 응용 프로그램이 있습니다.

Levenshtein 거리는 두 개의 긴 문자열 사이에서도 계산할 수 있습니다. 그러나 이를 계산하는 데 드는 비용은 두 문자열 길이의 곱에 거의 비례하므로 비효율적이며 비현실적입니다. 따라서 Levenshtein이 사용되는 경우 비교 속도를 높이기 위해 일반적으로 비교 하는 문자열이 짧다는 것이 특징입니다.

하지만 Inverted index 를 이용하면 최소한 비슷할 수 있는 단어들만을 후보로 추린 뒤, 소수의 후보에 대해서만 계산 비용이 비싼 Levenshtein distance 를 계산함으로써, 효율적인 오탈자 교정을 할 수 있습니다.

- BOJ[20542] : 받아쓰기

https://www.acmicpc.net/problem/20542

참조

https://lovit.github.io/nlp/2018/09/04/levenshtein_inverted_index/

https://www.cuelogic.com/blog/the-levenshtein-algorithm