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.


 
DEFINE STRING="CHAR ARRAY" ; sys.act
DEFINE ASCII_SpaceBar="32"
 
INT FUNC JaroDistance(STRING str1, str2)
  STRING Z(15)
  INT S1, S2, J, M, N, L, I, K, skip, Max, Min
  INT Result
  Result=0
  S1=str1(0)
  S2=str2(0)
  IF S1>S2 THEN
    SCopy(Z,str1)
    SCopy(str1,str2)
    SCopy(str2,Z)
    M=S1
    S1=S2
    S2=M
  FI
  J=1 M=0 N=0 L=S2/2 SCopy(Z,str2)
  FOR I=1 TO S1 DO
    skip=0
    IF str1(I)=str2(J) THEN
      M==+1
      str2(J)=ASCII_SpaceBar
      skip=1
    FI
    IF skip=0 THEN
      Max=1
      IF Max<(I-L) THEN Max=I-L FI
      Min=S2
      IF Min>(I+L-1) THEN Min=I+L-1 FI
      FOR K=Max TO Min DO
        IF str1(I)=str2(K) THEN
          N==+1
          M==+1
          str2(K)=ASCII_SpaceBar
          IF K>J THEN J=K FI
        FI
      OD
    FI
    IF J<S2 THEN J==+1 FI
  OD
  IF M=0 THEN
    Result=0 ; Jaro distance
  ELSE
    N=N/2
    Result=((M*100)/S1+(M*100)/S2+(((M-N)*100)/M))/3 ; Jaro distance
  FI
;  Min=S1 IF Min>S2 THEN Min=S2 FI
;  M=Min IF M>3 THEN M=3 FI
;  M==+1 L=0 SCopy(str2,Z)
;  IF M>Min THEN M=Min FI
;  FOR I=1 TO M DO
;    IF str1(I)=str2(I) THEN
;      L==+1
;    ELSE
;      EXIT
;    FI
;  OD
;  Result=Result*100 + (((L*100)/10)*(100 - Result)) ; Jaro Winkler distance
;  Result=(Result+49)/100
RETURN(Result)
 
PROC MAIN()
  INT result
  STRING Word_1(15), Word_2(15)
  PUT(125)
  PUTE()
 
  SCopy(Word_1,"MARTHA") SCopy(Word_2,"MARHTA")
  PrintF("%S - %S%E",Word_1,Word_2)
  result=JaroDistance(Word_1,Word_2)
  PrintF("Jaro Distance=%U%E%E",result)
 
  SCopy(Word_1,"DIXON") SCopy(Word_2,"DICKSONX")
  PrintF("%S - %S%E",Word_1,Word_2)
  result=JaroDistance(Word_1,Word_2)
  PrintF("Jaro Distance=%U%E%E",result)
 
  SCopy(Word_1,"JELLYFISH") SCopy(Word_2,"SMELLYFISH")
  PrintF("%S - %S%E",Word_1,Word_2)
  result=JaroDistance(Word_1,Word_2)
  PrintF("Jaro Distance=%U%E%E",result)
RETURN
 