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.


 
       identification division.
       program-id. JaroDistance.
 
       environment division.
       configuration section.
       repository.
           function length intrinsic
           function trim intrinsic
           function max intrinsic
           function min intrinsic
           .
 
       data division.
       working-storage section.
       77  s                      pic x(255).
       77  t                      pic x(255).
       77  s-length               pic 9(3).
       77  t-length               pic 9(3).
       77  i                      pic 9(3).
       77  j                      pic 9(3).
       77  k                      pic 9(3).
       77  start-pos              pic 9(3).
       77  end-pos                pic 9(3).
       77  match-distance         pic 9(3).
       77  matches                pic 9(3).
       77  transpositions         pic 9(3).
       77  distance               pic 9v9(8).
 
       01  jaro-table.
           05 filler              occurs 255.
              10 filler           pic 9(1).
                 88 s-matches     value 1 when set to false is 0.
              10 filler           pic 9(1).
                 88 t-matches     value 1 when set to false is 0.
 
       procedure division.
       main.
           move "MARTHA" to s
           move "MARHTA" to t
           perform jaro-calc-and-show
           move "DIXON" to s
           move "DICKSONX" to t
           perform jaro-calc-and-show
           move "JELLYFISH" to s
           move "SMELLYFISH" to t
           perform jaro-calc-and-show
           stop run
           .
       jaro-calc-and-show.
           perform jaro-distance
           display trim(s) " -> " trim(t) ", distance=" distance
           .           
       jaro-distance.
           move length(trim(s)) to s-length
           move length(trim(t)) to t-length
           if s-length = zeros and t-length = zeros
              move 1 to distance
              exit paragraph
           end-if
 
           compute match-distance = max(s-length, t-length) / 2 - 1
           move low-values to jaro-table
           move zeros to matches
           move zeros to transpositions
           perform varying i from 1 by 1 until i > s-length
              move max(1, i - match-distance) to start-pos
              move min(i + match-distance, t-length) to end-pos
              perform varying j from start-pos by 1 until j > end-pos
                 if t-matches(j) or s(i:1) <> t(j:1) 
                    exit perform cycle
                 end-if,
                 set s-matches(i), t-matches(j) to true
                 add 1 to matches
                 exit perform
              end-perform
           end-perform
           if matches = zeros
              move matches to distance
              exit paragraph
           end-if
 
           move 1 to k
           perform varying i from 1 by 1 until i > s-length
              if not s-matches(i)
                 exit perform cycle
              end-if
              perform until t-matches(k)
                 add 1 to k
              end-perform
              if s(i:1) <> t(k:1)
                 add 1 to transpositions
              end-if
              add 1 to k
           end-perform
 
           compute distance = ((matches / s-length) + (matches / t-length) +
                               ((matches - transpositions / 2) / matches)) / 3
           .
 