문자열 매칭 및 비교 알고리즘 (2): Levenshtein Distance (편집 거리)

1. Levenshtein Distance란?

Levenshtein Distance는 두 문자열 간의 유사도(Similarity)를 측정하기 위한 알고리즘으로, 한 문자열을 다른 문자열로 바꾸기 위해 필요한 최소 연산 횟수(편집 거리, Edit Distance)를 계산한다. 이때 허용되는 연산은 다음 세 가지다.

1. 문자 삽입 (Insertion)
2. 문자 삭제 (Deletion)
3. 문자 교체 (Substitution)

예를 들어, 문자열 "kitten"을 "sitting"으로 바꾸는 최소 편집 거리는 3이다.

• k → s (교체)
• e → i (교체)
• 끝에 g 추가 (삽입)

2. 알고리즘의 동작 원리

Levenshtein Distance는 동적 계획법(Dynamic Programming)을 활용하여 2차원 배열(dp 테이블)을 구성한다. 이 배열의 각 셀 dp[i][j]는 문자열 A의 길이 i와 문자열 B의 길이 j까지의 최소 편집 거리를 의미한다.

2.1 점화식

• 문자열 A의 길이: n, 문자열 B의 길이: m
• 초기 조건
  • dp[0][j] = j (빈 문자열에서 B[0...j]까지 삽입)
  • dp[i][0] = i (A[0...i]에서 빈 문자열로 삭제)
• 점화식

if A[i - 1] == B[j - 1]:
    dp[i][j] = dp[i - 1][j - 1]
else:
    dp[i][j] = min(
        dp[i - 1][j] + 1,    // 삭제
        dp[i][j - 1] + 1,    // 삽입
        dp[i - 1][j - 1] + 1 // 교체
    )

3. 구현 (Java)

public class LevenshteinDistance {
    public static int compute(String a, String b) {
        int n = a.length();
        int m = b.length();
        int[][] dp = new int[n + 1][m + 1];

        for (int i = 0; i <= n; i++) dp[i][0] = i;
        for (int j = 0; j <= m; j++) dp[0][j] = j;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(
                        Math.min(dp[i - 1][j], dp[i][j - 1]),
                        dp[i - 1][j - 1]
                    ) + 1;
                }
            }
        }

        return dp[n][m];
    }

    public static void main(String[] args) {
        String a = "kitten";
        String b = "sitting";
        System.out.println("Levenshtein 거리: " + compute(a, b));
    }
}

4. 성능 분석

구분	복잡도
시간 복잡도	O(n × m)
공간 복잡도	O(n × m) (최적화 시 O(min(n, m)))

 

n은 문자열 A의 길이, m은 문자열 B의 길이를 의미한다.

5. Levenshtein Distance의 활용 사례

• 자동 완성 및 오타 수정: 사용자가 잘못 입력한 단어를 유사한 단어로 교정
• 자연어 처리(NLP): 단어 간 유사도 측정, 텍스트 정렬
• 검색 엔진: 비슷한 검색어 추천
• 유전자 서열 비교: DNA, RNA 서열 간의 유사성 비교

6. LCS와의 차이점

항목	LCS	Levenshtein Distance
목적	가장 긴 공통 부분 수열 찾기	최소 편집 거리 계산
허용 연산	삭제만 허용	삽입, 삭제, 교체 모두 허용
결과	수열 (문자열) 길이	정수 (변환에 필요한 연산 횟수)

7. 결론

Levenshtein Distance는 문자열 간 유사도를 정량적으로 측정할 수 있는 강력한 도구이다. 오타 수정, 검색 보정, 텍스트 비교 등 다양한 분야에서 활용되며, NLP나 바이오인포매틱스에서도 중요한 역할을 한다. 문자열 매칭 문제를 해결할 때 꼭 알아야 할 필수 알고리즘 중 하나다.