레벤슈타인 거리

레벤슈타인 거리(영어: Levenshtein distance)는 두 문자열 사이의 최소 편집 거리를 나타내는 개념으로, 하나의 문자열을 다른 문자열로 바꾸기 위해 필요한 삽입, 삭제, 치환 연산의 최소 횟수를 의미한다. 편집 거리(edit distance)라고도 불린다.

개요

레벤슈타인 거리는 1965년 러시아의 과학자 블라디미르 레벤슈타인(Vladimir Levenshtein)이 처음 제안한 개념으로, 문자열 간의 유사성을 측정하는 대표적인 알고리즘 중 하나이다. 이 거리 값이 작을수록 두 문자열은 더 유사한 것으로 간주된다.

정의

레벤슈타인 거리에서 허용되는 편집 연산은 다음과 같다:

• 삽입: 한 문자를 문자열의 임의 위치에 삽입
• 삭제: 문자열의 한 문자를 제거
• 치환: 문자열의 한 문자를 다른 문자로 대체

예를 들어, "kitten"을 "sitting"으로 바꾸기 위한 최소 연산 수는 3이며, 이에 따라 두 단어의 레벤슈타인 거리는 3이다.

점화식

D(X, Y) =

• max(m, n)                         if m == 0 or n == 0
• D(X', Y')                         if X[m] == Y[n]
• 1 + min(
  • D(X', Y),     # 삭제 (delete X)
  • D(X, Y'),     # 삽입 (insert into X)
  • D(X', Y')     # 치환 (replace X)
• )                                 if X[m] != Y[n]

1. 기저 조건 (Base Case): 둘 중 하나라도 빈 문자열이면
   • max(m, n)번 편집해야 하므로 D(X, Y) = max(m, n)
2. 마지막 문자가 같을 때:
   • 편집 없이 넘어가도 되므로 D(X, Y) = D(X', Y')
3. 마지막 문자가 다를 때:
   • 최소 편집 연산을 선택해야 하므로 1 + min(delete, insert, replace) 중 최솟값을 사용

알고리즘

레벤슈타인 거리는 보통 동적 계획법(Dynamic Programming)을 통해 계산된다. 두 문자열 A와 B의 길이를 각각 m, n이라 할 때, 크기 (m+1)×(n+1)의 2차원 배열을 사용하여 다음과 같이 구해진다.

자세한 내용은 레벤슈타인 거리 단계별 추적 소스코드 참고

		e	l	o	n	g	a	t	e
	0	1	2	3	4	5	6	7	8
l	1	1	1	2	3	4	5	6	7
e	2	1	2	2	3	4	5	6	6
n	3	2	2	3	2	3	4	5	6
g	4	3	3	3	3	2	3	4	5
t	5	4	4	4	4	3	3	3	4
h	6	5	5	5	5	4	4	4	4
e	7	6	6	6	6	5	5	5	4
n	8	7	7	7	6	6	6	6	5

파이썬 구현

재귀적 구현

def levenshtein_recursive(x, y):

    m, n = len(x), len(y)

    if m == 0 or n == 0:

        return max(m, n)

    if x[-1] == y[-1]:

        return levenshtein_recursive(x[:-1], y[:-1])

    return 1 + min(

        levenshtein_recursive(x[:-1], y),     # 삭제

        levenshtein_recursive(x, y[:-1]),     # 삽입

        levenshtein_recursive(x[:-1], y[:-1]) # 치환

    )

동적 계획법 구현

중복 호출을 피하고 성능을 개선하기 위해 2차원 배열을 활용한 동적 계획법 방식이 일반적으로 사용된다.

def levenshtein_dp(a, b):

    m, n = len(a), len(b)

    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):

        dp[i][0] = i

    for j in range(n + 1):

        dp[0][j] = j

    for i in range(1, m + 1):

        for j in range(1, n + 1):

            cost = 0 if a[i - 1] == b[j - 1] else 1

            dp[i][j] = min(

                dp[i - 1][j] + 1,        # 삭제

                dp[i][j - 1] + 1,        # 삽입

                dp[i - 1][j - 1] + cost  # 치환

            )

    return dp[m][n]

응용

레벤슈타인 거리는 다음과 같은 분야에서 활용된다:

• 철자 교정 시스템
• 유전자 서열 분석
• 자연어 처리에서 유사 문장 판별
• 정보 검색 및 검색어 자동완성

관련 알고리즘

레벤슈타인 거리와 유사한 알고리즘으로는 다음이 있다:

• 다메라우-레벤슈타인 거리
• 해밍 거리
• 자로-윙클러 거리

이들 알고리즘은 허용 연산이나 가중치, 성능 최적화 등에서 차이를 보인다.

같이 보기

• 다메라우-레벤슈타인 거리
• 해밍 거리
• 동적 계획법
• 자연어 처리

참고 문헌

• Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions and reversals. *Soviet Physics Doklady*, 10(8), 707–710.