두개의 문자열이 있을때, 얼마나 유사한지를 백분율의 개념인 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 사이의 값으로 반환된다.
