문자열 매칭 및 비교 알고리즘 (3): Jaro-Winkler Similarity

1. Jaro-Winkler Similarity란?

Jaro-Winkler Similarity는 두 문자열 간의 유사도를 측정하기 위한 알고리즘으로, 특히 오타나 철자 오류가 있는 문자열 비교에 효과적이다. 미국 인구조사국에서 이름 매칭을 위해 처음 개발되었으며, 이후 Winkler가 접두사 일치 보정을 추가하여 현재의 Jaro-Winkler 알고리즘으로 확장되었다.

이 알고리즘은 문자의 일치 정도, 순서, 위치 등을 고려하여 문자열이 얼마나 비슷한지를 0.0(완전히 다름)부터 1.0(완전히 같음)까지의 점수로 반환한다.

2. 알고리즘의 동작 원리

Jaro-Winkler Similarity는 기본 Jaro 유사도를 계산한 뒤, 공통 접두사의 길이에 따라 가중치를 더해 최종 유사도를 계산한다.

3. 예제

문자열 A	문자열 B	유사도 결과
MARTHA	MARHTA	0.961
DIXON	DICKSONX	0.813
CRATE	TRACE	0.733

 

이처럼 철자 순서가 살짝 다르거나 일부 문자가 누락된 경우에도 높은 유사도를 반환한다.

4. Java 구현 예시

public class JaroWinkler {
    public static double jaroSimilarity(String s1, String s2) {
        if (s1.equals(s2)) return 1.0;

        int len1 = s1.length();
        int len2 = s2.length();

        int matchDistance = Integer.max(len1, len2) / 2 - 1;
        boolean[] s1Matches = new boolean[len1];
        boolean[] s2Matches = new boolean[len2];

        int matches = 0;
        for (int i = 0; i < len1; i++) {
            int start = Math.max(0, i - matchDistance);
            int end = Math.min(i + matchDistance + 1, len2);
            for (int j = start; j < end; j++) {
                if (s2Matches[j]) continue;
                if (s1.charAt(i) != s2.charAt(j)) continue;
                s1Matches[i] = true;
                s2Matches[j] = true;
                matches++;
                break;
            }
        }

        if (matches == 0) return 0.0;

        int transpositions = 0;
        int k = 0;
        for (int i = 0; i < len1; i++) {
            if (!s1Matches[i]) continue;
            while (!s2Matches[k]) k++;
            if (s1.charAt(i) != s2.charAt(k)) transpositions++;
            k++;
        }

        double jaro = ((double) matches / len1 +
                       (double) matches / len2 +
                       ((double) matches - transpositions / 2.0) / matches) / 3.0;

        // Jaro-Winkler 보정
        int prefix = 0;
        for (int i = 0; i < Math.min(4, Math.min(len1, len2)); i++) {
            if (s1.charAt(i) == s2.charAt(i)) prefix++;
            else break;
        }

        return jaro + (prefix * 0.1 * (1 - jaro));
    }

    public static void main(String[] args) {
        System.out.println(jaroSimilarity("MARTHA", "MARHTA")); // 0.961
    }
}

5. 성능 분석

항목	값
시간 복잡도	O(n) (n은 문자열 길이)
공간 복잡도	O(n)
반환 값 범위	0.0 (완전 불일치) ~ 1.0 (완전 일치)

6. 활용 사례

• 사람 이름 비교: 인구조사, 고객 데이터 정합성 검사 등
• 검색 엔진의 오타 보정
• 데이터 중복 제거: 주소, 기업명, 사용자 이름 등의 유사도 비교
• 자연어 처리(NLP): 문장 유사도 기반 문서 클러스터링

7. 결론

Jaro-Winkler Similarity는 철자 오류나 단순한 오타에 강인한 문자열 유사도 측정 알고리즘이다. 정밀한 검색이 필요한 분야, 특히 사람 이름이나 주소, 이메일 주소 등에서 널리 사용된다. 계산 방식은 비교적 간단하면서도 높은 정확도를 제공하며, 다양한 텍스트 매칭 문제에 효과적으로 활용할 수 있다.