'2015/05'에 해당되는 글 1건

  1. 2015.05.24 String distance(1) : Jaro–Winkler distance

String distance(1) : Jaro–Winkler distance

ㅍㄺㄻ 2015. 5. 24. 06:54

Jaro–Winkler distance

문자열 s_1 과 s_2 사이의 Jaro distance d_j 의 정의는

d_j = \left\{ \begin{array}{l l} 0 & \text{if }m = 0\\ \frac{1}{3}\left(\frac{m}{|s_1|} + \frac{m}{|s_2|} + \frac{m-t}{m}\right) & \text{otherwise} \end{array} \right.

여기에서 :

  • m 은 두 문자열에서 공통적으로 존재하는 문자의 수
  • t 는 두 문자열에 공통적으로 존재하나, 인덱스가 다른 문자의 수의 반

Jaro–Winkler distance d_w 는:

d_w = d_j + (\ell p (1 - d_j))

여기서:

  • d_j s_1 와 s_2 사이의 jaro distance
  • \ell 는 두 문자열의 공통 접두사의 길이로 최대 4개까지만 인정
  • p 는 고정된 scaling factor 공통 접두사가 있을경우 점수를 상향조정하기위해 사용하는 상수이다. p 는 0.25를 넘으면 안된다(넘으면 거리값이 1을 초과할수도 있음) Winkler's work 에서 표준적인 값은 p = 0.1 이다

Example

주어진 문자열 s_1 MARTHA 와 s_2  MARHTA 가 있을 때:

  • m = 6
  • |s_1| = 6
  • |s_2| = 6
  • s_1 T/H 와 s_2 의 H/T가 공통적으로 존재하나 순서가 다른 문자이므로,   t = \frac{2}{2} = 1

따라서 Jaro score 는:

d_j = \frac{1}{3}\left(\frac{6}{6} + \frac{6}{6} + \frac{6-1}{6}\right) = 0.944

Jaro–Winkler score 를 계산하기 위해 p = 0.1로 설정하고, 공통 접두사는 MAR 이므로:

  • \ell = 3

따라서:

d_w = 0.944 + (3 * 0.1 (1 - 0.944)) = 0.961



출처 : http://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance

'ㅍㄺㄻ' 카테고리의 다른 글

String distance(1) : Jaro–Winkler distance  (0) 2015.05.24
테스트  (0) 2015.01.24
Posted by 라나킴
트랙백 0개, 댓글 0개가 달렸습니다

댓글을 달아 주세요