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.


 func jaroWinklerMatch(_ s: String, _ t: String) -> Double {
    let s_len: Int = s.count
    let t_len: Int = t.count
 
    if s_len == 0 && t_len == 0 {
        return 1.0
    }
 
    if s_len == 0 || t_len == 0 {
        return 0.0
    }
 
    var match_distance: Int = 0
 
    if s_len == 1 && t_len == 1 {
        match_distance = 1
    } else {
        match_distance = ([s_len, t_len].max()!/2) - 1
    }
 
 
    var s_matches = [Bool]()
    var t_matches = [Bool]()
 
    for _ in 1...s_len {
        s_matches.append(false)
    }
 
    for _ in 1...t_len {
        t_matches.append(false)
    }
 
    var matches: Double = 0.0
    var transpositions: Double = 0.0
 
    for i in 0...s_len-1 {
 
        let start = [0, (i-match_distance)].max()!
        let end = [(i + match_distance), t_len-1].min()!
 
        if start > end {
            break
        }
 
        for j in start...end {
 
            if t_matches[j] {
                continue
            }
 
            if s[String.Index.init(encodedOffset: i)] != t[String.Index.init(encodedOffset: j)] {
                continue
            }
            // We must have a match
            s_matches[i] = true
            t_matches[j] = true
            matches += 1
            break
        }
    }
 
    if matches == 0 {
        return 0.0
    }
 
    var k = 0
    for i in 0...s_len-1 {
        if !s_matches[i] {
            continue
        }
        while !t_matches[k] {
            k += 1
        }
        if s[String.Index.init(encodedOffset: i)] != t[String.Index.init(encodedOffset: k)] {
 
            transpositions += 1
        }
 
        k += 1
    }
 
    let top = (matches / Double(s_len)) + (matches / Double(t_len)) + (matches - (transpositions / 2)) / matches
    return top/3
}
 
print("DWAYNE/DUANE:", jaroWinklerMatch("DWAYNE", "DUANE"))
print("MARTHA/MARHTA:", jaroWinklerMatch("MARTHA", "MARHTA"))
print("DIXON/DICKSONX:", jaroWinklerMatch("DIXON", "DICKSONX"))
print("JELLYFISH/SMELLYFISH:", jaroWinklerMatch("JELLYFISH", "SMELLYFISH"))
 