레벤슈타인 거리 편집하기

'''레벤슈타인 거리(영어: Levenshtein distance)'''는 두 문자열 사이의 최소 편집 거리를 나타내는 개념으로, 하나의 문자열을 다른 문자열로 바꾸기 위해 필요한 삽입, 삭제, 치환 연산의 최소 횟수를 의미한다. '''편집 거리(edit distance)'''라고도 불린다.
==개요==
레벤슈타인 거리는 1965년 러시아의 과학자 블라디미르 레벤슈타인(Vladimir Levenshtein)이 처음 제안한 개념으로, 문자열 간의 유사성을 측정하는 대표적인 알고리즘 중 하나이다. 이 거리 값이 작을수록 두 문자열은 더 유사한 것으로 간주된다.
==정의==
레벤슈타인 거리에서 허용되는 편집 연산은 다음과 같다:
*삽입: 한 문자를 문자열의 임의 위치에 삽입
*삭제: 문자열의 한 문자를 제거
*치환: 문자열의 한 문자를 다른 문자로 대체
예를 들어, "kitten"을 "sitting"으로 바꾸기 위한 최소 연산 수는 3이며, 이에 따라 두 단어의 레벤슈타인 거리는 3이다.

== 점화식 ==
<blockquote>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]
</blockquote>

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

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

자세한 내용은 [[레벤슈타인 거리 단계별 추적 소스코드]] 참고
{| class="wikitable"
! !! !!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
|}
==파이썬 구현==
=== 재귀적 구현===
<syntaxhighlight lang="python">

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]) # 치환

    )

</syntaxhighlight>
=== 동적 계획법 구현===
중복 호출을 피하고 성능을 개선하기 위해 2차원 배열을 활용한 동적 계획법 방식이 일반적으로 사용된다.<syntaxhighlight lang="python">

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]

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