Levenshtein Distance, Jaro-Winkler 알고리즘 : 문자열 유사도 측정

LeeYulhee·2023년 11월 28일
0

👉 Levenshtein Distance (편집 거리) 알고리즘


  • 설명
    • 두 문자열 사이의 Levenshtein 거리는 한 문자열을 다른 문자열로 변환하기 위해 필요한 최소한의 단일 문자 편집(삽입, 삭제, 대체) 수
  • 사용 사례
    • 오타 수정, DNA 염기 서열 분석, 언어학에서 단어 유사도 측정 등
  • 계산 방법
    • 동적 프로그래밍
      • 문자열을 행렬의 행과 열로 사용하여 각 셀에 최소 편집 비용을 계산
    • 재귀적 접근
      • 가능하지만 효율성이 떨어질 수 있음
  • 예시
    • "kitten"에서 "sitting"으로 변환하는 데 필요한 최소 편집 횟수는 3회
      • k → s, e → i, n 추가



👉 Jaro-Winkler 알고리즘


  • 설명
    • 두 문자열의 유사도를 0과 1 사이의 값으로 측정
    • 1은 완전한 일치를, 0은 전혀 다름을 나타냄
  • 사용 사례
    • 주로 이름과 같은 짧은 문자열의 유사도를 측정하는 데 사용
  • 계산 방법
    • Jaro 유사도
      • 일치하는 문자와 트랜스포지션(문자 위치의 반전)을 기반으로 함
    • Winkler 확장
      • 두 문자열의 접두사가 같을수록 높은 점수를 부여
  • 예시
    • "martha"와 "marhta"의 Jaro 유사도는 높지만, "martha"와 "marht"의 Jaro-Winkler 점수는 접두사가 다르기 때문에 낮음



👉 비교


  • Levenshtein 거리는 편집 횟수를 기반으로 하는 반면, Jaro-Winkler는 문자열의 일치 정도와 접두사의 유사성을 중시
  • Levenshtein은 더 일반적이고 다양한 길이의 문자열에 적합한 반면, Jaro-Winkler는 특히 짧은 문자열의 유사도 측정에 더 유용
profile
끝없이 성장하고자 하는 백엔드 개발자입니다.

0개의 댓글

관련 채용 정보