[카테고리:] 미분류

두개의 문자열이 있을때, 얼마나 유사한지를 백분율의 개념인 0~1사이의 값으로 확인할 수 있을까? 즉 똑같은 문자열이라면 1을 전혀 다른 문자열이라면 0이라는 값으로 말이다. 구글링해보니 edit distance 계산을 통해 얻을 수 있단다. 가장 일반적은 구현체는 Levenshtein의 Distance Algorithm이라고 하고, 그 구현 함수는 다음과 같다. (출처: http://rosettacode.org/wiki/Levenshtein_distance#Java)

private double similarity(String s1, String s2) {
    String longer = s1, shorter = s2;
	
    if (s1.length() < s2.length()) {
        longer = s2; 
        shorter = s1;
    }
	
    int longerLength = longer.length();
    if (longerLength == 0) return 1.0;

    return (longerLength - editDistance(longer, shorter)) / (double) longerLength;
}

private int editDistance(String s1, String s2) {
	s1 = s1.toLowerCase();
    s2 = s2.toLowerCase();
    int[] costs = new int[s2.length() + 1];
    
    for (int i = 0; i <= s1.length(); i++) {
        int lastValue = i;
        for (int j = 0; j <= s2.length(); j++) {
            if (i == 0) {
            	costs[j] = j;
            } else {
                if (j > 0) {
                    int newValue = costs[j - 1];
                    
                    if (s1.charAt(i - 1) != s2.charAt(j - 1)) {
                    	newValue = Math.min(Math.min(newValue, lastValue), costs[j]) + 1;
                    }
                    
                    costs[j - 1] = lastValue;
                    lastValue = newValue;
                }
            }
        }
        
        if (i > 0) costs[s2.length()] = lastValue;
    }
    
    return costs[s2.length()];
}

사용은 similarity 함수에 비교할 문자열 2개를 지정하면 비슷한 정도가 0~1 사이의 값으로 반환된다.