Levenshtein Distance: 텍스트 유사성 측정을 위한 궁극적인 가이드

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

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

이 개념은 철자 교정, 퍼지 검색, DNA 비교 등 다양한 최신 응용 프로그램의 핵심입니다.

수학적 개념

각각 길이가 (n)과 (m)인 두 줄 (A)와 (B) 사이의 레벤슈타인 거리는 동적 접근 방식을 사용하여 계산할 수 있습니다. ((n 1) x (m 1)) 차원의 행렬(D)을 정의합니다. 여기서 각 (D[i][j])는 (A)의 (i) 첫 번째 문자를 다음 문자로 변환하는 데 드는 최소 비용을 나타냅니다. (j) (B)의 첫 번째 문자.

반복 공식은 다음과 같습니다.

Python으로 구현

다음은 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]

# Exemple d'utilisation
print(levenshtein_distance("kitten", "sitting"))  # Sortie : 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 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]

# Exemple d'utilisation
print(levenshtein_distance("kitten", "sitting"))  # Sortie : 3

결론

Levenshtein 거리는 여러 분야에서 강력하고 다재다능하며 널리 사용되는 도구입니다. 이해하기 쉽지만 복잡한 최적화 및 적용은 현대 시스템에서 그 가치를 입증합니다.

더 자세히 살펴보면 전치를 고려하는 Damerau-Levenshtein 거리와 같은 변형을 고려할 수도 있습니다. 이제 이 도구를 프로젝트에 통합하거나 심층적인 지식으로 동료에게 깊은 인상을 남길 수 있습니다!

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

위 내용은 Levenshtein Distance: 텍스트 유사성 측정을 위한 궁극적인 가이드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!