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

👉 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는 특히 짧은 문자열의 유사도 측정에 더 유용