[딥러닝] 레벤슈타인 거리 Levenshtein Distance 해설, 정리, 요약

---

안녕하세요, HELLO

 

Edit Distance라고도 하는 Levenshtein Distance는 두 문자열 간의 차이를 측정하는 데 사용되는 방법입니다. 이는 한 문자열을 다른 문자열로 변환하는 데, 필요한 단일 문자 편집(삽입, 삭제 또는 대체)의 최소 수를 의미합니다. Levenshtein Distance는 1965년 알고리즘을 처음 소개한 러시아 수학자 Vladimir Levenshtein의 이름을 따서 명명되었습니다.

 

오늘은 Levenshtein distance에 대해서 정리하고자 합니다.

---

CHAPTER 1. 'Levenshtein Distance' 개요

 

CHAPTER 2. 'Levenshtein Distance' 사용

 

반응형

 

CHAPTER 1. 'Levenshtein Distance' 개요

 

 

두 문자열 간의 차이를 측정하기 위해서, 두 문자열 s와 t 사이의 Levenshtein 거리는 s의 마지막 문자를 t로 변환하기 위해 수행할 수 있는 세 가지 가능한 작업을 고려하여 재귀적으로 계산할 수 있습니다.

 

• 삽입: s 끝에 문자를 삽입하여 s를 t로 변환
• 삭제: s의 마지막 문자를 삭제하여 s를 t로 변환
• 대체: s의 마지막 문자를 다른 문자로 대체하여 s를 t로 변환

 

 

lev(s, t) = 
    if len(s) == 0: len(t)
    elif len(t) == 0: len(s)
    else:
        cost = 0 if s[-1] == t[-1] else 1
        return min(lev(s[:-1], t) + 1,   # deletion
                   lev(s, t[:-1]) + 1,   # insertion
                   lev(s[:-1], t[:-1]) + cost)  # substitution

 

위 재귀 함수, Levenshtein 계산은 중복 계산을 피하고 성능을 향상하기 위해 효과적으로 메모리를 사용할 수 있습니다. 결과 알고리즘은 전산 생물학, 자연어 처리 및 문자열 일치가 중요한 기타 분야에서 일반적으로 사용됩니다.

 

 

CHAPTER 2. 'Levenshtein Distance' 사용

 

Levenshtein 거리는 다음과 같은 다양한 목적을 위해 언어 모델링 및 기타 모델에 유용할 수 있습니다.

 

1. 철자 교정: 철자가 틀린 단어가 주어지면 Levenshtein 거리를 사용하여 철자까지의 거리가 낮은 단어를 찾아 가능한 올바른 철자를 제안할 수 있습니다.
2. 음성 인식: Levenshtein 거리는 인식된 음성 전사를 참조 전사와 비교하여 인식 시스템의 정확도를 평가하는 데 사용할 수 있습니다.
3. 기계 번역: Levenshtein 거리는 통계적 기계 번역 모델의 전처리 단계로 소스 언어와 대상 언어의 해당 단어를 정렬하는 데 사용할 수 있습니다.
4. DNA 분석: Levenshtein 거리는 DNA 서열을 비교하고 이들 사이의 유사점과 차이점을 식별하는 데 사용할 수 있습니다.

전반적으로 Levenshtein 거리는 문자열 간의 유사성 또는 차이점을 측정하는 것이 중요한 다양한 영역에서 유용한 도구입니다.

---

■ 마무리

 

'레벤슈타인 거리 Levenshtein Distance'에 대해서 정리해봤습니다.

 

그럼 오늘 하루도 즐거운 나날 되길 기도하겠습니다

좋아요와 댓글 부탁드립니다 :)

 

감사합니다.