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.


function jaro(string str1, str2)
    str1 = trim(upper(str1))
    str2 = trim(upper(str2))
    integer len1 = length(str1),
            len2 = length(str2),
            match_distance = floor(max(len1,len2)/2)-1,
            match_count = 0,
            half_transposed = 0
 
    if len1==0 then return len2==0 end if
 
    -- count the number of matches
    sequence m1 = repeat(false,len1),
             m2 = repeat(false,len2)
    for i=1 to len1 do
        for k=max(1,i-match_distance)
           to min(len2,i+match_distance) do
            if not m2[k] then
                if str1[i]=str2[k] then
                    m1[i] = true
                    m2[k] = true
                    match_count += 1
                    exit
                end if
            end if
        end for
    end for
 
    if match_count==0 then return 0 end if
 
    -- count the number of half-transpositions
    integer k = 1
    for i=1 to len1 do
        if m1[i] then
            while not m2[k] do k += 1 end while
            half_transposed += (str1[i]!=str2[k])
            k += 1
        end if
    end for
    integer transpositions = floor(half_transposed/2),
            not_transposed = match_count - transpositions
    --
    -- return the average of:
    --   percentage/fraction of the first string matched,
    --   percentage/fraction of the second string matched, and
    --   percentage/fraction of matches that were not transposed.
    --
    return (match_count/len1 + 
            match_count/len2 + 
            not_transposed/match_count)/3
end function
 
constant testcouples = {{"CRATE","TRACE"},
                        {"JONES","JOHNSON"},
                        {"ABCVWXYZ","CABVWXYZ"},
                        {"DWAYNE","DUANE"},
                        {"MARTHA", "MARHTA"},
                        {"DIXON", "DICKSONX"},
                        {"JELLYFISH", "SMELLYFISH"}}
 
for i=1 to length(testcouples) do
    string {s1, s2} = testcouples[i]
    printf(1,"%f <== jaro(\"%s\", \"%s\")\n",{jaro(s1,s2),s1,s2})
end for
