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.


defmodule Jaro do
  def distance(s, t) when is_binary(s) and is_binary(t), do:
    distance(to_charlist(s), to_charlist(t))
  def distance(x, x), do: 1.0
  def distance(s, t) do
    s_len = length(s)
    t_len = length(t)
    {s_matches, t_matches, matches} = matching(s, t, s_len, t_len)
    if matches == 0 do
      0.0
    else
      {k, transpositions} = transposition(s, t, s_matches, t_matches)
      ((matches / s_len) +
       (matches / t_len) +
       ((matches - transpositions/2) / matches)) / 3
    end
  end
 
  defp matching(s, t, s_len, t_len) do
    match_distance = div(max(s_len, t_len), 2) - 1
    ac0 = {List.duplicate(false, s_len), List.duplicate(false, t_len), 0}
    Enum.reduce(0..s_len-1, ac0, fn i,acc ->
      j_start = max(0, i-match_distance)
      j_end = min(i+match_distance, t_len-1)
      Enum.reduce_while(j_start..j_end, acc, fn j,{sm,tm,m} ->
        if Enum.at(tm, j) or Enum.at(s, i) != Enum.at(t, j) do
          {:cont, {sm, tm, m}}
        else
          {:halt, { List.replace_at(sm, i, true),
                    List.replace_at(tm, j, true),
                    m + 1 }}
        end
      end)
    end)
  end
 
  defp transposition(s, t, s_matches, t_matches) do
    Enum.reduce(0..length(s)-1, {0,0}, fn i,{k,transpositions} ->
      if Enum.at(s_matches, i) do
        k = k + (Enum.drop(t_matches, k)
                 |> Enum.take_while(fn matche -> not matche end)
                 |> length)
        if Enum.at(s, i) == Enum.at(t, k), do: {k+1, transpositions},
                                         else: {k+1, transpositions+1}
      else
        {k, transpositions}
      end
    end)
  end
end
 
~w( MARTHA    MARHTA
    DIXON     DICKSONX
    JELLYFISH SMELLYFISH )c
|> Enum.chunk(2)
|> Enum.each(fn [s,t] ->
     :io.format "jaro(~s, ~s) = ~.10f~n", [inspect(s), inspect(t), Jaro.distance(s, t)]
   end)