Levenshtein Distance, Jaro-Winkler 알고리즘 : 문자열 유사도 측정
👉 Levenshtein Distance (편집 거리) 알고리즘
- 설명
- 두 문자열 사이의 Levenshtein 거리는 한 문자열을 다른 문자열로 변환하기 위해 필요한 최소한의 단일 문자 편집(삽입, 삭제, 대체) 수
- 사용 사례
- 오타 수정, DNA 염기 서열 분석, 언어학에서 단어 유사도 측정 등
- 계산 방법
- 동적 프로그래밍
- 문자열을 행렬의 행과 열로 사용하여 각 셀에 최소 편집 비용을 계산
- 재귀적 접근
- 예시
- "kitten"에서 "sitting"으로 변환하는 데 필요한 최소 편집 횟수는 3회
👉 Jaro-Winkler 알고리즘
- 설명
- 두 문자열의 유사도를 0과 1 사이의 값으로 측정
- 1은 완전한 일치를, 0은 전혀 다름을 나타냄
- 사용 사례
- 주로 이름과 같은 짧은 문자열의 유사도를 측정하는 데 사용
- 계산 방법
- Jaro 유사도
- 일치하는 문자와 트랜스포지션(문자 위치의 반전)을 기반으로 함
- Winkler 확장
- 두 문자열의 접두사가 같을수록 높은 점수를 부여
- 예시
- "martha"와 "marhta"의 Jaro 유사도는 높지만, "martha"와 "marht"의 Jaro-Winkler 점수는 접두사가 다르기 때문에 낮음
👉 비교
- Levenshtein 거리는 편집 횟수를 기반으로 하는 반면, Jaro-Winkler는 문자열의 일치 정도와 접두사의 유사성을 중시
- Levenshtein은 더 일반적이고 다양한 길이의 문자열에 적합한 반면, Jaro-Winkler는 특히 짧은 문자열의 유사도 측정에 더 유용