편집 거리라고도 하는 Levenshtein 거리는 두 문자열 간의 유사성을 평가하기 위한 기본 측정항목입니다. 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 작업 수를 계산합니다. 이러한 작업에는 다음이 포함됩니다.

1. 삽입: 문자를 추가합니다.
2. 삭제: 캐릭터를 제거합니다.
3. 대체: 한 문자를 다른 문자로 대체합니다.

이 개념은 철자 검사, 퍼지 검색, DNA 서열 비교와 같은 많은 현대 응용 프로그램의 핵심입니다.

수학적 개념

길이가 (n)과 (m)인 두 문자열(A)과 (B) 사이의 Levenshtein 거리는 동적 프로그래밍 접근 방식을 사용하여 계산할 수 있습니다. 크기가 ((n 1) \times (m 1))인 행렬( D )을 정의합니다. 여기서 각 항목( D[i][j] )은 ( A )의 첫 번째 ( i ) 문자를 변환하는 데 드는 최소 비용을 나타냅니다. ( B )의 첫 번째 ( j ) 문자로 변환합니다.

반복 관계는 다음과 같습니다.

파이썬 구현

다음은 Levenshtein 거리를 계산하는 간단한 Python 구현입니다.

def levenshtein_distance(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m   1) for _ in range(n   1)]

    for i in range(n   1):
        for j in range(m   1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1   min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

    return dp[n][m]

# Example usage
print(levenshtein_distance("kitten", "sitting"))  # Output: 3

실제 응용

1. 맞춤법 검사

맞춤법 검사기는 Levenshtein 거리를 사용하여 오타 수정을 제안합니다. 예를 들어 helo를 입력하면 hello 또는 Hero가 제안될 수 있습니다.

2. 퍼지 검색

검색 엔진에서 Levenshtein은 사용자가 오타나 철자 오류를 범하는 경우에도 결과를 반환하도록 도와줍니다.

3. DNA 비교

생물정보학에서 이 거리는 각 작업이 잠재적인 돌연변이를 나타내는 두 DNA 서열 간의 유사성을 측정하는 데 도움이 됩니다.

4. 인증 및 사기 탐지

신원 사기를 탐지하는 시스템은 작은 텍스트 차이를 고려하여 사용자 입력을 기존 기록과 비교할 수 있습니다.

최적화: 메모리가 감소된 Levenshtein 거리

클래식 알고리즘은 메모리 집약적일 수 있는 전체 행렬을 사용합니다. 다행히도 각 행( D[i][j] )은 ( D[i-1][j] )에만 의존하므로 두 행의 메모리만 사용하도록 최적화할 수 있습니다. ( D[i][j-1] ) 및 ( D[i-1][j-1] ).

def optimized_levenshtein(a, b):
    n, m = len(a), len(b)
    prev = list(range(m   1))
    curr = [0] * (m   1)

    for i in range(1, n   1):
        curr[0] = i
        for j in range(1, m   1):
            insert = curr[j - 1]   1
            delete = prev[j]   1
            substitute = prev[j - 1]   (0 if a[i - 1] == b[j - 1] else 1)
            curr[j] = min(insert, delete, substitute)
        prev, curr = curr, prev

    return prev[m]

# Example usage
print(optimized_levenshtein("kitten", "sitting"))  # Output: 3

결론

Levenshtein 거리는 다양한 분야에서 널리 사용되는 강력하고 다재다능한 도구입니다. 이해하기 쉽지만 최적화 및 복잡한 응용 프로그램은 최신 시스템에서의 가치를 강조합니다.

추가 탐색을 위해 전치를 설명하는 Damerau-Levenshtein 거리와 같은 변형을 고려하세요. 이제 이 도구를 프로젝트에 통합하거나 깊은 이해로 동료들에게 깊은 인상을 남길 수 있습니다!

Levenshtein 거리에 대한 질문이나 아이디어가 있나요? 댓글로 공유해주세요! ?