레벤슈타인 거리

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

개요

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

정의

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

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

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

알고리즘

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

D(i, j) =

• D(i-1, j) + 1 (삭제)
• D(i, j-1) + 1 (삽입)
• D(i-1, j-1) + cost (치환, 단 cost는 문자가 다르면 1, 같으면 0)

초기 조건으로는 D(0,0) = 0이며, 각 행과 열의 첫 번째 값을 순차적으로 증가하는 정수로 설정한다.

파이썬 구현

다음은 레벤슈타인 거리를 계산하는 간단한 파이썬 함수의 예시이다.

def levenshtein_distance(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.