레벤슈타인 거리: 두 판 사이의 차이

IT 위키
(새 문서: '''레벤슈타인 거리(영어: Levenshtein distance)'''는 두 문자열 사이의 최소 편집 거리를 나타내는 개념으로, 하나의 문자열을 다른 문자열로 바꾸기 위해 필요한 삽입, 삭제, 치환 연산의 최소 횟수를 의미한다. '''편집 거리(edit distance)'''라고도 불린다. ==개요== 레벤슈타인 거리는 1965년 러시아의 과학자 블라디미르 레벤슈타인(Vladimir Levenshtein)이 처음 제안한 개념으로,...)
 
편집 요약 없음
8번째 줄: 8번째 줄:
*치환: 문자열의 한 문자를 다른 문자로 대체
*치환: 문자열의 한 문자를 다른 문자로 대체
예를 들어, "kitten"을 "sitting"으로 바꾸기 위한 최소 연산 수는 3이며, 이에 따라 두 단어의 레벤슈타인 거리는 3이다.
예를 들어, "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차원 배열을 사용하여 다음 점화식으로 값을 구한다.
레벤슈타인 거리는 보통 동적 계획법(Dynamic Programming)을 통해 계산된다. 두 문자열 A와 B의 길이를 각각 m, n이라 할 때, 크기 (m+1)×(n+1)의 2차원 배열을 사용하여 다음 점화식으로 값을 구한다.
17번째 줄: 37번째 줄:
초기 조건으로는 D(0,0) = 0이며, 각 행과 열의 첫 번째 값을 순차적으로 증가하는 정수로 설정한다.
초기 조건으로는 D(0,0) = 0이며, 각 행과 열의 첫 번째 값을 순차적으로 증가하는 정수로 설정한다.
==파이썬 구현==
==파이썬 구현==
다음은 레벤슈타인 거리를 계산하는 간단한 파이썬 함수의 예시이다.<syntaxhighlight lang="python">
===재귀적 구현===
def levenshtein_distance(a, b):
<syntaxhighlight lang="python">
    m, n = len(a), len(b)
 
    dp = [[0] * (n + 1) for _ in range(m + 1)]
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  # 치환


    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):
    return dp[m][n]
        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>
</syntaxhighlight>
==응용==
==응용==

2025년 5월 8일 (목) 13:27 판

레벤슈타인 거리(영어: 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차원 배열을 사용하여 다음 점화식으로 값을 구한다.

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_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.

각주

원본 주소 "https://itwiki.kr/index.php?title=레벤슈타인_거리&oldid=40882"