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.


 
program Jaro_distance;
 
uses SysUtils, Math;
 
//converted from C source by /u/bleuge
function ssJaroWinkler(s1, s2: string): double;
var
  l1, l2, match_distance, matches, i, k, trans: integer;
  bs1, bs2: array[1..255] of boolean; //used to avoid getmem, max string length is 255
begin
  l1 := length(s1);
  l2 := length(s2);
  fillchar(bs1, sizeof(bs1), 0); //set booleans to false
  fillchar(bs2, sizeof(bs2), 0);
  if l1 = 0 then
    if l2 = 0 then
      exit(1)
    else
      exit(0);
  match_distance := (max(l1, l2) div 2) - 1;
  matches := 0;
  trans := 0;
  for i := 1 to l1 do
  begin
    for k := max(1, i - match_distance) to min(i + match_distance, l2) do
    begin
      if bs2[k] then
        continue;
      if s1[i] <> s2[k] then
        continue;
      bs1[i] := true;
      bs2[k] := true;
      inc(matches);
      break;
    end;
  end;
  if matches = 0 then
    exit(0);
  k := 1;
  for i := 1 to l1 do
  begin
    if (bs1[i] = false) then
      continue;
    while (bs2[k] = false) do
      inc(k);
    if s1[i] <> s2[k] then
      inc(trans);
    inc(k);
  end;
  trans := trans div 2;
  result := ((matches / l1) + (matches / l2) + ((matches - trans) / matches)) / 3;
end;
 
begin
//test
  writeln(formatfloat('0.######', ssJaroWinkler('DWAYNE', 'DUANE')));
  writeln(formatfloat('0.######', ssJaroWinkler('MARTHA', 'MARHTA')));
  writeln(formatfloat('0.######', ssJaroWinkler('DIXON', 'DICKSONX')));
  writeln(formatfloat('0.######', ssJaroWinkler('JELLYFISH', 'SMELLYFISH')));
  {$IFNDEF LINUX}readln;{$ENDIF}
end.