jaro-winkler similarity(jaro-winkler distance)

프로젝트 중 알게된 edit distance 비교 방법이 있어서 정리해본다.

(사실 매번 Damerau–Levenshtein distance만 사용했었다...)

jaro similarity(jaro distance)

jaro distance는 두 단어간의 transpositions에 집중한 알고리즘이다.

(insertion, deletion, substitution은 고려하지 않음)

transposition은 간단히 위치 교환이라고 생각하면 된다.

아래와 같이 두 단어가 있을 때, transpositions은 총 2회 발생한다.

(a=> b, b => a)

word1  : a ---- b

word2 : b ---- a

jaro distance는 두 단어가 비슷할수록 1에 가까운 값을 가지고, 다를수록 0에 가까운 값을 가진다.

(두 단어가 같으면 1, 다르면 0이다)

s1, s2는 각 문자열을 의미하고

|s1|은 s1의 길이를 의미하고

m은 match된 문자 개수를 의미하고

t는 transposition이 필요한 개수의 절반을 의미한다.

ex)

CRATE, TRACE

s1의 길이는 5

s2의 길이는 5

m의 개수는 3

t는 transposition이 2번 필요한데, 그 절반이니 2/2 = 1

1/3 * ( 5/5 + 5/5 + (3-1)/3) = 0.62

추가로 matching이라고 판단하는 범위는 같은 위치이거나 혹은 아래 범위내에서만 매칭이라고 본다.

(아무래도 너무 멀리 있으면 안되서... 그런 것 같다)

jaro-winkler similarity(jaro-winkler distance)

jaro-winkler의 경우는 prefix matching에 대한 가중치를 추가한 것으로

이렇게 생겼다.

simj는 jaro distance를 의미하고

l은 prefix lengnth(최대 4)

p는 scaling factor인데 0.1이 기본값이고, 0.25가 최대값이다(0.25를 넘게 주면 similarity가 1을 넘을 수 있다).

distance를 구할 때는 dw = 1 - simw 이다.

참고

wiki : https://en.wikipedia.org/wiki/Jaro–Winkler_distance

잘 정리해놓은 블로그(한글) : http://qtqtlanakim.tistory.com/11

apache common code : http://commons.apache.org/proper/commons-text/jacoco/org.apache.commons.text.similarity/JaroWinklerDistance.java.html