user
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 {\displaystyle d\_{j}}}
   of two given strings   

s

1
{\displaystyle {\displaystyle s\_{1}}}
   and   

s

2
{\displaystyle {\displaystyle s\_{2}}}
   is

:   d

    j
    =

    {

    0


    if 
    m
    =
    0

    1
    3

    (

    m


    |

    s

    1

    |
    +


    m


    |

    s

    2

    |
    +

    m
    −
    t
    m
    )


    otherwise

    {\displaystyle {\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 {\displaystyle m}}
     is the number of *matching characters*;
* t
  {\displaystyle {\displaystyle t}}
     is half the number of *transpositions*.

Two characters from   

s

1
{\displaystyle {\displaystyle s\_{1}}}
   and   

s

2
{\displaystyle {\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 {\displaystyle \left\lfloor {\frac {\max(|s\_{1}|,|s\_{2}|)}{2}}\right\rfloor -1}}
 characters.

Each character of   

s

1
{\displaystyle {\displaystyle s\_{1}}}
   is compared with all its matching characters in   

s

2
{\displaystyle {\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 {\displaystyle s\_{1}}}
   *DWAYNE*   and   

s

2
{\displaystyle {\displaystyle s\_{2}}}
   *DUANE*   we find:

* m
  =
  4
  {\displaystyle {\displaystyle m=4}}
* |

  s

  1

  |
  =
  6
  {\displaystyle {\displaystyle |s\_{1}|=6}}
* |

  s

  2

  |
  =
  5
  {\displaystyle {\displaystyle |s\_{2}|=5}}
* t
  =
  0
  {\displaystyle {\displaystyle t=0}}

We find a Jaro score of:

:   d

    j
    =


    1
    3

    (

    4
    6
    +


    4
    5
    +

    4
    −
    0
    4
    )
    =
    0.822
    {\displaystyle {\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.
assistant
(formerly Perl 6)

**Translation of**: Perl

```
sub jaro ($s, $t) {
    return 1 if $s eq $t;

    my $s-len = + my @s = $s.comb;
    my $t-len = + my @t = $t.comb;
    my $match-distance = ($s-len max $t-len) div 2 - 1;

    my ($matches, @s-matches, @t-matches);
    for ^@s -> $i {
        my $start = 0 max $i - $match-distance;
        my $end   = $i + $match-distance min ($t-len - 1);

        for $start .. $end -> $j {
            next if @t-matches[$j] or @s[$i] ne @t[$j];
            (@s-matches[$i], @t-matches[$j]) = (1, 1);
            $matches++ and last;
        }
    }
    return 0 unless $matches;

    my ($k, $transpositions) = (0, 0);
    for ^@s -> $i {
        next unless @s-matches[$i];
        $k++ until  @t-matches[$k];
        $transpositions++ if @s[$i] ne @t[$k];
        $k++;
    }

    ( $matches/$s-len + $matches/$t-len + (($matches - $transpositions/2) / $matches) ) / 3
}

say jaro(.key, .value).fmt: '%.3f' for
    'MARTHA' => 'MARHTA', 'DIXON' => 'DICKSONX', 'JELLYFISH' => 'SMELLYFISH',
    'I repeat myself' => 'I repeat myself', '' => '';

```

Output:

```
0.944
0.767
0.896
1.000
1.000
```