1. 레벤슈타인 거리 (Levenshtein distance), 편집 거리 (Edit Distance)
ㅇ 두 단어(문자열) 사이의 유사성을 측정하는 방법으로써,
- 서로다른 두 단어가 같아지려면 편집해야하는 연산 횟수
ㅇ 창안자 : 1965년 블라디미르 레벤슈타인이 고안
ㅇ 용도 (활용) : 단어 유사도 측정, 철자 오타 교정, DNA 서열 비교 등
ㅇ 편집 연산의 종류 및 거리
- 삽입 (Insertion) : 한 문자를 삽입
- 삭제 (Deletion) : 한 문자를 삭제
- 대치 (Substitution) : 한 문자를 다른 문자로 치환
* 레벤슈타인 거리 : 두 단어가 같아지기 위한 세 연산의 최소 수행 횟수
ㅇ 例) "kitten" → "sitting"
- kitten → sitten (k→s 치환) (1회)
- sitten → sittin (e→i 치환) (2회)
- sittin → sitting (g 삽입) (3회)
* 따라서, 레벤슈타인 거리 = 3
ㅇ 거리값 의미
- 값이 0 이면, 두 문자열이 완전히 같음
- 값이 클수록, 문자열 차이가 큼