The Jaro distance is a measure of edit distance between two strings; its inverse, called the Jaro similarity, is a measure of two strings' similarity: the higher the value, the more similar the strings are. The score is normalized such that   0   equates to no similarities and   1   is an exact match.



Definition
The Jaro similarity   




d

j




{\displaystyle d_{j}}

   of two given strings   




s

1




{\displaystyle s_{1}}

   and   




s

2




{\displaystyle s_{2}}

   is

 




d

j


=

{




0



if 

m
=
0






1
3



(


m


|


s

1



|




+


m


|


s

2



|




+



m
−
t

m


)




otherwise









{\displaystyle 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.}


Where:

 



m


{\displaystyle m}

   is the number of matching characters;
 



t


{\displaystyle t}

   is half the number of transpositions.


Two characters from   




s

1




{\displaystyle s_{1}}

   and   




s

2




{\displaystyle s_{2}}

   respectively, are considered matching only if they are the same and not farther apart than   




⌊



max
(

|


s

1



|

,

|


s

2



|

)

2


⌋

−
1


{\displaystyle \left\lfloor {\frac {\max(|s_{1}|,|s_{2}|)}{2}}\right\rfloor -1}

 characters.

Each character of   




s

1




{\displaystyle s_{1}}

   is compared with all its matching characters in   




s

2




{\displaystyle s_{2}}

. Each difference in position is half a transposition; that is, the number of transpositions is half the number of characters which are common to the two strings but occupy different positions in each one.



Example
Given the strings   




s

1




{\displaystyle s_{1}}

   DWAYNE   and   




s

2




{\displaystyle s_{2}}

   DUANE   we find:

 



m
=
4


{\displaystyle m=4}


 




|


s

1



|

=
6


{\displaystyle |s_{1}|=6}


 




|


s

2



|

=
5


{\displaystyle |s_{2}|=5}


 



t
=
0


{\displaystyle t=0}




We find a Jaro score of:

 




d

j


=


1
3



(


4
6


+


4
5


+



4
−
0

4


)

=
0.822


{\displaystyle d_{j}={\frac {1}{3}}\left({\frac {4}{6}}+{\frac {4}{5}}+{\frac {4-0}{4}}\right)=0.822}




Task
Implement the Jaro algorithm and show the similarity scores for each of the following pairs:

 ("MARTHA", "MARHTA")
 ("DIXON", "DICKSONX")
 ("JELLYFISH", "SMELLYFISH")


 See also
 Jaro–Winkler distance on Wikipedia.


 
# syntax: GAWK -f JARO_DISTANCE.AWK
BEGIN {
    main("DWAYNE","DUANE")
    main("MARTHA","MARHTA")
    main("DIXON","DICKSONX")
    main("JELLYFISH","SMELLYFISH")
    exit(0)
}
function main(str1,str2) {
    printf("%9.7f '%s' '%s'\n",jaro(str1,str2),str1,str2)
}
function jaro(str1,str2,  begin,end,i,j,k,leng1,leng2,match_distance,matches,str1_arr,str2_arr,transpositions) {
    leng1 = length(str1)
    leng2 = length(str2)
    if (leng1 == 0 && leng2 == 0) { # both strings are empty
      return(1)
    }
    if (leng1 == 0 || leng2 == 0) { # only one string is empty
      return(0)
    }
    match_distance = int(max(leng1,leng2)/2-1)
    for (i=1; i<=leng1; i++) { # find matches
      begin = int(max(0,i-match_distance))
      end = int(min(i+match_distance+1,leng2))
      for (j=begin; j<=end; j++) {
        if (str2_arr[j]) { continue }
        if (substr(str1,i,1) != substr(str2,j,1)) { continue }
        str1_arr[i] = 1
        str2_arr[j] = 1
        matches++
        break
      }
    }
    if (matches == 0) {
      return(0)
    }
    k = 0
    for (i=1; i<=leng1; i++) { # count transpositions
      if (!str1_arr[i]) { continue }
      while (!str2_arr[k]) {
        k++
      }
      if (substr(str1,i,1) != substr(str2,k,1)) {
        transpositions++
      }
      k++
    }
    transpositions /= 2
    return((matches/leng1)+(matches/leng2)+((matches-transpositions)/matches))/3
}
function max(x,y) { return((x > y) ? x : y) }
function min(x,y) { return((x < y) ? x : y) }
 