user
The Jaro-Winkler distance is a metric for measuring the edit distance between words.
It is similar to the more basic Levenshtein distance but the Jaro distance also accounts
for transpositions between letters in the words. With the Winkler modification to the Jaro
metric, the Jaro-Winkler distance also adds an increase in similarity for words which
start with the same letters (prefix).

The Jaro-Winkler distance is a modification of the Jaro similarity metric, which
measures the similarity between two strings. The Jaro similarity is 1.0 when strings are
identical and 0 when strings have no letters in common. Distance measures such as the
Jaro distance or Jaro-Winkler distance, on the other hand, are 0 when strings are
identical and 1 when they have no letters in common.

The Jaro similarity between two strings s1 and s2, simj, is defined as

:   simj = 0     if m is 0.
:   simj = ( (m / length of s1) + (m / length of s2) + (m - t) / m ) / 3     otherwise.

Where:

* m
  {\displaystyle {\displaystyle m}}
     is the number of *matching characters (the same character within max(|s1|, |s2|)/2 - 1 of one another)*;
* t
  {\displaystyle {\displaystyle t}}
     is half the number of *transpositions (a shared character placed in different positions)*.

The Winkler modification to Jaro is to check for identical prefixes of the strings.

If we define the number of initial (prefix) characters in common as:

*l* = the length of a common prefix between strings, up to 4 characters

and, additionally, select a multiplier (Winkler suggested 0.1) for the relative importance of the
prefix for the word similarity:

*p*    =   0.1

The Jaro-Winkler similarity can then be defined as

simw = simj + *l**p*(1 - simj)

Where:

* simj   is the Jaro similarity.
* *l*   is the number of matching characters at the beginning of the strings, up to 4.
* *p*   is a factor to modify the amount to which the prefix similarity affects the metric.

Winkler suggested this be 0.1.

The Jaro-Winkler distance between strings, which is 0.0 for identical strings, is then defined as

dw = 1 - simw

String metrics such as Jaro-Winkler distance are useful in applications such as spelling checkers,
because letter transpositions are common typing errors and humans tend to misspell the middle portions
of words more often than their beginnings. This may help a spelling checker program to generate
better alternatives for misspelled word replacement.

The task

Using a dictionary of your choice and the following list of 9 commonly misspelled words:

"accomodate", "definately", "goverment​", "occured", "publically", "recieve​", "seperate", "untill", "wich​"

* Calculate the Jaro-Winkler distance between the misspelled word and words in the dictionary.

* Use this distance to list close alternatives (at least two per word) to the misspelled words.

* Show the calculated distances between the misspelled words and their potential replacements.

See also
:   * Wikipedia page: Jaro–Winkler distance.
    * Comparing string similarity algorithms. Comparison of algorithms on Medium
assistant
**Works with**: Rakudo version 2020.07

A minor modification of the Jaro distance task entry.

using the unixdict.txt file from www.puzzlers.org

```
sub jaro-winkler ($s, $t) {

    return 0 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 @s_matches;
    my @t_matches;
    my $matches = 0;

    for ^@s -> $i {

        my $start = 0 max $i - $match_distance;
        my $end = $i + $match_distance min ($t_len - 1);

        for $start .. $end -> $j {
            @t_matches[$j] and next;
            @s[$i] eq @t[$j] or next;
            @s_matches[$i] = 1;
            @t_matches[$j] = 1;
            $matches++;
            last;
        }
    }

    return 1 if $matches == 0;

    my $k              = 0;
    my $transpositions = 0;

    for ^@s -> $i {
        @s_matches[$i] or next;
        until @t_matches[$k] { ++$k }
        @s[$i] eq @t[$k] or ++$transpositions;
        ++$k;
    }

    my $prefix = 0;

    ++$prefix if @s[$_] eq @t[$_] for ^(min 4, $s_len, $t_len);

    my $jaro = ($matches / $s_len + $matches / $t_len +
        (($matches - $transpositions / 2) / $matches)) / 3;

    1 - ($jaro + $prefix * .1 * ( 1 - $jaro) )
}


my @words =  './unixdict.txt'.IO.slurp.words;

for <accomodate definately goverment occured publically recieve seperate untill wich>
   -> $word {

   my %result = @words.race.map: { $_ => jaro-winkler($word, $_) };

   say "\nClosest 5 dictionary words with a Jaro-Winkler distance < .15 from $word:";

   printf "%15s : %0.4f\n", .key, .value for %result.grep({ .value < .15 }).sort({+.value, ~.key}).head(5);
}

```

Output:

```
Closest 5 dictionary words with a Jaro-Winkler distance < .15 from accomodate:
    accommodate : 0.0182
      accordant : 0.1044
       accolade : 0.1136
      acclimate : 0.1219
    accompanist : 0.1327

Closest 5 dictionary words with a Jaro-Winkler distance < .15 from definately:
         define : 0.0800
       definite : 0.0850
        defiant : 0.0886
     definitive : 0.1200
      designate : 0.1219

Closest 5 dictionary words with a Jaro-Winkler distance < .15 from goverment:
         govern : 0.0667
       governor : 0.1167
      governess : 0.1175
     governance : 0.1330
       coverlet : 0.1361

Closest 5 dictionary words with a Jaro-Winkler distance < .15 from occured:
       occurred : 0.0250
          occur : 0.0571
      occurrent : 0.0952
        occlude : 0.1056
      concurred : 0.1217

Closest 5 dictionary words with a Jaro-Winkler distance < .15 from publically:
         public : 0.0800
    publication : 0.1327
           pull : 0.1400
       pullback : 0.1492

Closest 5 dictionary words with a Jaro-Winkler distance < .15 from recieve:
        receive : 0.0333
        relieve : 0.0667
          reeve : 0.0762
      receptive : 0.0852
      recessive : 0.0852

Closest 5 dictionary words with a Jaro-Winkler distance < .15 from seperate:
      desperate : 0.0708
       separate : 0.0917
      temperate : 0.1042
       selenate : 0.1167
           sept : 0.1167

Closest 5 dictionary words with a Jaro-Winkler distance < .15 from untill:
          until : 0.0333
           till : 0.1111
     huntsville : 0.1333
        instill : 0.1357
         unital : 0.1422

Closest 5 dictionary words with a Jaro-Winkler distance < .15 from wich:
          winch : 0.0533
          witch : 0.0533
          which : 0.0600
        wichita : 0.0857
         switch : 0.1111
```