레벤슈타인 거리 편집하기

'''레벤슈타인 거리(영어: 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이며, 각 행과 열의 첫 번째 값을 순차적으로 증가하는 정수로 설정한다.
==파이썬 구현==
다음은 레벤슈타인 거리를 계산하는 간단한 파이썬 함수의 예시이다.<syntaxhighlight lang="python">
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]
</syntaxhighlight>
==응용==
레벤슈타인 거리는 다음과 같은 분야에서 활용된다:
*철자 교정 시스템
*유전자 서열 분석
*자연어 처리에서 유사 문장 판별
*정보 검색 및 검색어 자동완성
==관련 알고리즘==
레벤슈타인 거리와 유사한 알고리즘으로는 다음이 있다:
*다메라우-레벤슈타인 거리
*해밍 거리
*자로-윙클러 거리
이들 알고리즘은 허용 연산이나 가중치, 성능 최적화 등에서 차이를 보인다.
==같이 보기==
*[[다메라우-레벤슈타인 거리]]
*[[해밍 거리]]
*[[동적 계획법]]
*[[자연어 처리]]
==참고 문헌==
*Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions and reversals. *Soviet Physics Doklady*, 10(8), 707–710.
==각주==
[[분류:알고리즘]]
[[분류:동적 계획법]]