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.


/*REXX program computes the  Jaro distance  between two strings  (or a list of strings).*/
@.=                                              /*define a default for the  @.  array. */
parse arg @.1                                    /*obtain an optional character string. */
if @.1=''  then do;  @.1= 'MARTHA     MARHTA'    /*Nothing specified?  Use the defaults.*/
                     @.2= 'DIXON      DICKSONX'
                     @.3= 'JELLYFISH  SMELLYFISH'
                     @.4= 'DWAYNE     DUANE'
                end                              /* [↑] embedded blanks are shown as is.*/
 
       do j=1  while @.j\==''                    /*process all the strings in the list. */
       d= jaroD(@.j)
       say 'Jaro distance is  '       format(d, , 8)        " for strings:  "         @.j
       end   /*j*/                               /* └──── digits past the decimal point.*/
exit 0                                           /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
jaroD: procedure; arg s.1 s.2 .;       L1= length(s.1);      L2= length(s.2);      m= 0
       if L1==0 | L2==0  then return 0           /*check if any string is a null string.*/
       f= max(L1, L2) % 2   -   1                /*calculate furthest distanced allowed.*/
       r.= 0                                     /* [↓]  see if the char is near enough.*/
            do k=1  for L1;   p= pos( substr(s.1, k, 1), s.2,  max(1, k-f) )
            r.k= p
            if p\==0 & abs(p-k)<=f  then m= m+1  /*if near enough, count it as a match. */
                                    else r.k= 0  /*       ··· otherwise, don't count it.*/
            end   /*k*/
       t= 0
            do o=1  for L1;         om= o - 1;       if  r.o==0  |  r.om==0  then iterate
            if pos( substr(s.1, o, 1), s.2)==0  then iterate
            if r.o<r.om  then t= t + 1
            end   /*o*/                          /* [↑]  count number of transpositions.*/
 
       if m==0  then return 0
                     return (m/L1  +  m/L2  +  (m-t)/m)   /   3