Jaro-Winkler distance: Difference between revisions
Content deleted Content added
SqrtNegInf (talk | contribs) Added Perl example |
Added Sidef |
||
(22 intermediate revisions by 15 users not shown) | |||
Line 1:
{{
The Jaro-Winkler distance is a metric for measuring the edit distance between words.
It is similar to the more basic
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
Line 73:
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">V WORDS = File(‘linuxwords.txt’).read_lines()
V MISSPELLINGS = [‘accomodate’,
‘definately’,
‘goverment’]
F jaro_winkler_distance(=st1, =st2)
I st1.len < st2.len
(st1, st2) = (st2, st1)
V len1 = st1.len
V len2 = st2.len
I len2 == 0
R 0.0
V delta = max(0, len2 I/ 2 - 1)
V flag = (0 .< len2).map(_ -> 0B)
[Char] ch1_match
L(ch1) st1
V idx1 = L.index
L(ch2) st2
V idx2 = L.index
I idx2 <= idx1 + delta & idx2 >= idx1 - delta & ch1 == ch2 & !(flag[idx2])
flag[idx2] = 1B
ch1_match.append(ch1)
L.break
V matches = ch1_match.len
I matches == 0
R 1.0
V transpositions = 0
V idx1 = 0
L(ch2) st2
V idx2 = L.index
I flag[idx2]
transpositions += (ch2 != ch1_match[idx1])
idx1++
V jaro = (Float(matches) / len1 + Float(matches) / len2 + (matches - transpositions / 2) / matches) / 3.0
V commonprefix = 0
L(i) 0 .< min(4, len2)
commonprefix += (st1[i] == st2[i])
R 1.0 - (jaro + commonprefix * 0.1 * (1 - jaro))
F within_distance(maxdistance, stri, maxtoreturn)
V arr = :WORDS.filter(w -> jaro_winkler_distance(@stri, w) <= @maxdistance)
arr.sort(key' x -> jaro_winkler_distance(@stri, x))
R I arr.len <= maxtoreturn {arr} E arr[0 .< maxtoreturn]
L(STR) MISSPELLINGS
print("\nClose dictionary words ( distance < 0.15 using Jaro-Winkler distance) to \" "STR" \" are:\n Word | Distance")
L(w) within_distance(0.15, STR, 5)
print(‘#14 | #.4’.format(w, jaro_winkler_distance(STR, w)))</syntaxhighlight>
{{out}}
<pre>
Close dictionary words ( distance < 0.15 using Jaro-Winkler distance) to " accomodate " are:
Word | Distance
accommodate | 0.0182
accommodated | 0.0333
accommodates | 0.0333
accommodating | 0.0815
accommodation | 0.0815
Close dictionary words ( distance < 0.15 using Jaro-Winkler distance) to " definately " are:
Word | Distance
definitely | 0.0400
defiantly | 0.0422
define | 0.0800
definite | 0.0850
definable | 0.0872
Close dictionary words ( distance < 0.15 using Jaro-Winkler distance) to " goverment " are:
Word | Distance
government | 0.0533
govern | 0.0667
governments | 0.0697
movement | 0.0810
governmental | 0.0833
</pre>
=={{header|Elm}}==
Author: zh5
<syntaxhighlight lang="elm">module JaroWinkler exposing (similarity)
commonPrefixLength : List a -> List a -> Int -> Int
commonPrefixLength xs ys counter =
case ( xs, ys ) of
( x :: xs_, y :: ys_ ) ->
if x == y then
commonPrefixLength xs_ ys_ (counter + 1)
else
counter
_ ->
counter
similarity : String -> String -> Float
similarity s1 s2 =
let
chars1 =
String.toList s1
chars2 =
String.toList s2
jaroScore =
jaro chars1 chars2
l =
toFloat <| min (commonPrefixLength chars1 chars2 0) 4
p =
0.1
in
jaroScore + (l * p * (1.0 - jaroScore))
containtsInNextN : Int -> a -> List a -> Bool
containtsInNextN i a items =
case ( i, items ) of
( 0, _ ) ->
False
( _, [] ) ->
False
( _, item :: rest ) ->
if item == a then
True
else
containtsInNextN (i - 1) a rest
exists : Int -> Int -> List a -> a -> Bool
exists startAt endAt items i =
if endAt < startAt then
False
else if startAt == 0 then
case items of
first :: rest ->
if i == first then
True
else
exists 0 (endAt - 1) rest i
[] ->
False
else
exists 0 (endAt - startAt) (List.drop startAt items) i
existsInWindow : a -> List a -> Int -> Int -> Bool
existsInWindow item items offset radius =
let
startAt =
max 0 (offset - radius)
endAt =
min (offset + radius) (List.length items - 1)
in
exists startAt endAt items item
transpositions : List a -> List a -> Int -> Int
transpositions xs ys counter =
case ( xs, ys ) of
( [], _ ) ->
counter
( _, [] ) ->
counter
( x :: xs_, y :: ys_ ) ->
if x /= y then
transpositions xs_ ys_ (counter + 1)
else
transpositions xs_ ys_ counter
commonItems : List a -> List a -> Int -> List a
commonItems items1 items2 radius =
items1
|> List.indexedMap
(\index item ->
if existsInWindow item items2 index radius then
[ item ]
else
[]
)
|> List.concat
jaro : List Char -> List Char -> Float
jaro chars1 chars2 =
let
minLenth =
min (List.length chars1) (List.length chars2)
matchRadius =
minLenth // 2 + (minLenth |> modBy 2)
c1 =
commonItems chars1 chars2 matchRadius
c2 =
commonItems chars2 chars1 matchRadius
c1length =
toFloat (List.length c1)
c2length =
toFloat (List.length c2)
mismatches =
transpositions c1 c2 0
transpositionScore =
(toFloat mismatches + abs (c1length - c2length)) / 2.0
s1length =
toFloat (List.length chars1)
s2length =
toFloat (List.length chars2)
tLength =
max c1length c2length
result =
(c1length / s1length + c2length / s2length + (tLength - transpositionScore) / tLength) / 3.0
in
if isNaN result then
0.0
else
result
</syntaxhighlight>
=={{header|ALGOL 68}}==
Line 81 ⟶ 326:
<br>
Prints the 6 closest matches regarddless of their distance (i.e. we don't restrict it to matches closer that 0.15).
<
IF STRING s1 = sp1[ AT 0 ];
STRING s2 = sp2[ AT 0 ];
Line 212 ⟶ 457:
print( ( newline ) )
OD
FI</
{{out}}
<pre>
Line 286 ⟶ 531:
0.1111 twitch
0.1111 switch
</pre>
=={{header|C++}}==
{{trans|Swift}}
<syntaxhighlight lang="cpp">#include <algorithm>
#include <cstdlib>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
auto load_dictionary(const std::string& path) {
std::ifstream in(path);
if (!in)
throw std::runtime_error("Cannot open file " + path);
std::string line;
std::vector<std::string> words;
while (getline(in, line))
words.push_back(line);
return words;
}
double jaro_winkler_distance(std::string str1, std::string str2) {
size_t len1 = str1.size();
size_t len2 = str2.size();
if (len1 < len2) {
std::swap(str1, str2);
std::swap(len1, len2);
}
if (len2 == 0)
return len1 == 0 ? 0.0 : 1.0;
size_t delta = std::max(size_t(1), len1/2) - 1;
std::vector<bool> flag(len2, false);
std::vector<char> ch1_match;
ch1_match.reserve(len1);
for (size_t idx1 = 0; idx1 < len1; ++idx1) {
char ch1 = str1[idx1];
for (size_t idx2 = 0; idx2 < len2; ++idx2) {
char ch2 = str2[idx2];
if (idx2 <= idx1 + delta && idx2 + delta >= idx1
&& ch1 == ch2 && !flag[idx2]) {
flag[idx2] = true;
ch1_match.push_back(ch1);
break;
}
}
}
size_t matches = ch1_match.size();
if (matches == 0)
return 1.0;
size_t transpositions = 0;
for (size_t idx1 = 0, idx2 = 0; idx2 < len2; ++idx2) {
if (flag[idx2]) {
if (str2[idx2] != ch1_match[idx1])
++transpositions;
++idx1;
}
}
double m = matches;
double jaro = (m/len1 + m/len2 + (m - transpositions/2.0)/m)/3.0;
size_t common_prefix = 0;
len2 = std::min(size_t(4), len2);
for (size_t i = 0; i < len2; ++i) {
if (str1[i] == str2[i])
++common_prefix;
}
return 1.0 - (jaro + common_prefix * 0.1 * (1.0 - jaro));
}
auto within_distance(const std::vector<std::string>& words,
double max_distance, const std::string& str,
size_t max_to_return) {
using pair = std::pair<std::string, double>;
std::vector<pair> result;
for (const auto& word : words) {
double jaro = jaro_winkler_distance(word, str);
if (jaro <= max_distance)
result.emplace_back(word, jaro);
}
std::stable_sort(result.begin(), result.end(),
[](const pair& p1, const pair& p2) { return p1.second < p2.second; });
if (result.size() > max_to_return)
result.resize(max_to_return);
return result;
}
int main() {
try {
auto words(load_dictionary("linuxwords.txt"));
std::cout << std::fixed << std::setprecision(4);
for (auto str : {"accomodate", "definately", "goverment",
"occured", "publically", "recieve",
"seperate", "untill", "wich"}) {
std::cout << "Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to '"
<< str << "' are:\n Word | Distance\n";
for (const auto& pair : within_distance(words, 0.15, str, 5)) {
std::cout << std::setw(14) << pair.first << " | "
<< std::setw(6) << pair.second << '\n';
}
std::cout << '\n';
}
} catch (const std::exception& ex) {
std::cerr << ex.what() << '\n';
return EXIT_FAILURE;
}
return EXIT_SUCCESS;
}</syntaxhighlight>
{{out}}
<pre>
Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to 'accomodate' are:
Word | Distance
accommodate | 0.0182
accommodated | 0.0333
accommodates | 0.0333
accommodating | 0.0815
accommodation | 0.0815
Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to 'definately' are:
Word | Distance
definitely | 0.0400
defiantly | 0.0422
define | 0.0800
definite | 0.0850
definable | 0.0872
Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to 'goverment' are:
Word | Distance
government | 0.0533
govern | 0.0667
governments | 0.0697
movement | 0.0810
governmental | 0.0833
Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to 'occured' are:
Word | Distance
occurred | 0.0250
occur | 0.0571
occupied | 0.0786
occurs | 0.0905
accursed | 0.0917
Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to 'publically' are:
Word | Distance
publicly | 0.0400
public | 0.0800
publicity | 0.1044
publication | 0.1327
biblically | 0.1400
Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to 'recieve' are:
Word | Distance
receive | 0.0333
received | 0.0625
receiver | 0.0625
receives | 0.0625
relieve | 0.0667
Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to 'seperate' are:
Word | Distance
desperate | 0.0708
separate | 0.0917
temperate | 0.1042
separated | 0.1144
separates | 0.1144
Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to 'untill' are:
Word | Distance
until | 0.0333
untie | 0.1067
untimely | 0.1083
till | 0.1111
Antilles | 0.1264
Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to 'wich' are:
Word | Distance
witch | 0.0533
which | 0.0600
switch | 0.1111
twitch | 0.1111
witches | 0.1143
</pre>
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Jaro_distance#F.23 Jaro Distance (F#)]
<
// Calculate Jaro-Winkler Similarity of 2 Strings. Nigel Galloway: August 7th., 2020
let Jw P n g=let L=float(let i=Seq.map2(fun n g->n=g) n g in (if Seq.length i>4 then i|>Seq.take 4 else i)|>Seq.takeWhile id|>Seq.length)
Line 299 ⟶ 727:
["accomodate";"definately";"goverment";"occured";"publically";"recieve";"seperate";"untill";"wich"]|>
List.iter(fun n->printfn "%s" n;fN n|>Array.take 5|>Array.iter(fun n->printf "%A" n);printfn "\n")
</syntaxhighlight>
{{out}}
<pre>
Line 332 ⟶ 760:
=={{header|Go}}==
This uses unixdict and borrows code from the [[Jaro_distance#Go]] task. Otherwise it is a translation of the Wren entry.
<
import (
Line 461 ⟶ 889:
fmt.Println()
}
}</
{{out}}
Line 533 ⟶ 961:
0.1111 switch
0.1111 twitch
</pre>
=={{header|J}}==
Implementation:
<syntaxhighlight lang="j">jaro=: {{
Eq=. (x=/y)*(<.<:-:x>.&#y)>:|x -/&i.&# y
xM=. (+./"1 Eq)#x
yM=. (+./"2 Eq)#y
M=. xM <.&# yM
T=. -: +/ xM ~:&(M&{.) yM
3%~ (M%#x) + (M%#y) + (M-T)%M
}}
jarowinkler=: {{
p=. 0.1
l=. +/*/\x =&((4<.x<.&#y)&{.) y
simj=. x jaro y
-.simj + l*p*-.simj
}}</syntaxhighlight>
Task example:
<syntaxhighlight lang="j">task=: {{
words=. <;._2 fread '/usr/share/dict/words'
for_word. ;:'accomodate definately goverment occured publically recieve seperate untill wich' do.
b=.d<:close=. 2{/:~d=. word jarowinkler every words
echo (;word),':'
echo ' ',.(":,.b#d),.' ',.>b#words
echo''
end.
}}
task''
accomodate:
0.0681818 accommodate
0.0945455 accorporate
0.0703704 commodate
definately:
0.0422222 defiantly
0.0622222 definably
0.0622222 definedly
goverment:
0.0833333 govern
0.0644444 government
0.0944444 governmental
occured:
0.105556 occlude
0.0571429 occur
0.0952381 occursive
publically:
0.08 public
0.0747222 publicity
0.0525 publicly
recieve:
0.0592593 reachieve
0.0333333 receive
0.0392857 recidive
seperate:
0.0145833 separate
0.0405093 separates
0.0458333 septate
untill:
0.0333333 until
0 untill
0.0333333 untrill
wich:
0.04 wicht
0.0533333 winch
0.0533333 witch
</syntaxhighlight>
=={{header|Java}}==
{{trans|C++}}
<syntaxhighlight lang="java">import java.io.*;
import java.util.*;
public class JaroWinkler {
public static void main(String[] args) {
try {
List<String> words = loadDictionary("linuxwords.txt");
String[] strings = {
"accomodate", "definately", "goverment", "occured",
"publically", "recieve", "seperate", "untill", "wich"
};
for (String string : strings) {
System.out.printf("Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to '%s' are:\n"
+ " Word | Distance\n", string);
for (StringDistance s : withinDistance(words, 0.15, string, 5)) {
System.out.printf("%14s | %.4f\n", s.word, s.distance);
}
System.out.println();
}
} catch (Exception e) {
e.printStackTrace();
}
}
private static class StringDistance implements Comparable<StringDistance> {
private StringDistance(String word, double distance) {
this.word = word;
this.distance = distance;
}
public int compareTo(StringDistance s) {
return Double.compare(distance, s.distance);
}
private String word;
private double distance;
}
private static List<StringDistance> withinDistance(List<String> words,
double maxDistance, String string, int max) {
List<StringDistance> result = new ArrayList<>();
for (String word : words) {
double distance = jaroWinklerDistance(word, string);
if (distance <= maxDistance)
result.add(new StringDistance(word, distance));
}
Collections.sort(result);
if (result.size() > max)
result = result.subList(0, max);
return result;
}
private static double jaroWinklerDistance(String string1, String string2) {
int len1 = string1.length();
int len2 = string2.length();
if (len1 < len2) {
String s = string1;
string1 = string2;
string2 = s;
int tmp = len1;
len1 = len2;
len2 = tmp;
}
if (len2 == 0)
return len1 == 0 ? 0.0 : 1.0;
int delta = Math.max(1, len1 / 2) - 1;
boolean[] flag = new boolean[len2];
Arrays.fill(flag, false);
char[] ch1Match = new char[len1];
int matches = 0;
for (int i = 0; i < len1; ++i) {
char ch1 = string1.charAt(i);
for (int j = 0; j < len2; ++j) {
char ch2 = string2.charAt(j);
if (j <= i + delta && j + delta >= i && ch1 == ch2 && !flag[j]) {
flag[j] = true;
ch1Match[matches++] = ch1;
break;
}
}
}
if (matches == 0)
return 1.0;
int transpositions = 0;
for (int i = 0, j = 0; j < len2; ++j) {
if (flag[j]) {
if (string2.charAt(j) != ch1Match[i])
++transpositions;
++i;
}
}
double m = matches;
double jaro = (m / len1 + m / len2 + (m - transpositions / 2.0) / m) / 3.0;
int commonPrefix = 0;
len2 = Math.min(4, len2);
for (int i = 0; i < len2; ++i) {
if (string1.charAt(i) == string2.charAt(i))
++commonPrefix;
}
return 1.0 - (jaro + commonPrefix * 0.1 * (1.0 - jaro));
}
private static List<String> loadDictionary(String path) throws IOException {
try (BufferedReader reader = new BufferedReader(new FileReader(path))) {
List<String> words = new ArrayList<>();
String word;
while ((word = reader.readLine()) != null)
words.add(word);
return words;
}
}
}</syntaxhighlight>
{{out}}
<pre>
Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to 'accomodate' are:
Word | Distance
accommodate | 0.0182
accommodated | 0.0333
accommodates | 0.0333
accommodating | 0.0815
accommodation | 0.0815
Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to 'definately' are:
Word | Distance
definitely | 0.0400
defiantly | 0.0422
define | 0.0800
definite | 0.0850
definable | 0.0872
Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to 'goverment' are:
Word | Distance
government | 0.0533
govern | 0.0667
governments | 0.0697
movement | 0.0810
governmental | 0.0833
Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to 'occured' are:
Word | Distance
occurred | 0.0250
occur | 0.0571
occupied | 0.0786
occurs | 0.0905
accursed | 0.0917
Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to 'publically' are:
Word | Distance
publicly | 0.0400
public | 0.0800
publicity | 0.1044
publication | 0.1327
biblically | 0.1400
Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to 'recieve' are:
Word | Distance
receive | 0.0333
received | 0.0625
receiver | 0.0625
receives | 0.0625
relieve | 0.0667
Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to 'seperate' are:
Word | Distance
desperate | 0.0708
separate | 0.0917
temperate | 0.1042
separated | 0.1144
separates | 0.1144
Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to 'untill' are:
Word | Distance
until | 0.0333
untie | 0.1067
untimely | 0.1083
till | 0.1111
Antilles | 0.1264
Close dictionary words (distance < 0.15 using Jaro-Winkler distance) to 'wich' are:
Word | Distance
witch | 0.0533
which | 0.0600
switch | 0.1111
twitch | 0.1111
witches | 0.1143
</pre>
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
This entry, which uses unixdict.txt, borrows the implementation in jq of the Jaro similarity measure as defined at
[[Jaro_similarity#jq]]; since it is quite long, it is not repeated here.
<syntaxhighlight lang="jq"># See [[Jaro_similarity#jq]] for the implementation of jaro/2
def length_of_common_prefix($s1; $s2):
if ($s1|length) > ($s2|length) then length_of_common_prefix($s2; $s1)
else ($s1|explode) as $x1
| ($s2|explode) as $x2
| first( range(0;$x1|length) | select( $x1[.] != $x2[.] )) // ($x1|length)
end;
# Output: the Jaro-WInkler distance using 0.1 as the common-prefix multiplier
def jaro_winkler($s1; $s2):
if $s1 == $s2 then 0
else jaro($s1; $s2) as $j
| length_of_common_prefix($s1[:4]; $s2[:4]) as $l
| 1 - ($j + 0.1 * $l * (1 - $j))
end ;
# Input: an array of words
# Output: [[match, distance] ...]
def candidates($word; $threshold):
map(jaro_winkler($word; . ) as $x | select($x <= $threshold) | [., $x] );
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
def task:
[inputs] # the dictionary
| ("accomodate", "definately", "goverment", "occured", "publically", "recieve", "seperate", "untill", "wich") as $word
| candidates($word; 0.15) | sort_by(.[-1]) | .[:5]
| "Matches for \($word|lpad(10)): Distance",
(.[] | "\(.[0] | lpad(21)) : \(.[-1] * 1000 | round / 1000)") ;
task</syntaxhighlight>
{{out}}
Invocation: jq -rRn -f program.jq unixdict.txt
<pre>
Matches for accomodate: Distance
accommodate : 0.018
accordant : 0.104
accolade : 0.114
acclimate : 0.122
accompanist : 0.133
Matches for definately: Distance
define : 0.08
definite : 0.085
defiant : 0.089
definitive : 0.12
deflate : 0.127
Matches for goverment: Distance
govern : 0.08
governor : 0.13
governess : 0.133
governance : 0.149
Matches for occured: Distance
occurred : 0.025
occur : 0.057
occurrent : 0.095
occlude : 0.106
concurred : 0.122
Matches for publically: Distance
public : 0.08
publication : 0.133
Matches for recieve: Distance
receive : 0.063
reeve : 0.1
relieve : 0.105
recife : 0.108
recipe : 0.108
Matches for seperate: Distance
desperate : 0.079
separate : 0.092
temperate : 0.116
sept : 0.117
septate : 0.131
Matches for untill: Distance
until : 0.033
till : 0.111
huntsville : 0.133
unital : 0.142
Matches for wich: Distance
winch : 0.107
witch : 0.107
which : 0.12
wichita : 0.126
</pre>
=={{header|Julia}}==
<
const words = read("linuxwords.txt", String) |> split .|> strip
Line 586 ⟶ 1,372:
end
end
</
<pre>
Close dictionary words ( distance < 0.15 using Jaro-Winkler distance) to 'accomodate' are:
Line 660 ⟶ 1,446:
wick | 0.11664
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[JWD]
JWD[a_][b_]:=Experimental`JaroWinklerDistance[a,b]
dict=DictionaryLookup[];
TakeSmallestBy[dict->{"Element","Value"},JWD["accomodate"],5]//Grid
TakeSmallestBy[dict->{"Element","Value"},JWD["definately"],5]//Grid
TakeSmallestBy[dict->{"Element","Value"},JWD["goverment"],5]//Grid
TakeSmallestBy[dict->{"Element","Value"},JWD["occured"],5]//Grid
TakeSmallestBy[dict->{"Element","Value"},JWD["publically"],5]//Grid
TakeSmallestBy[dict->{"Element","Value"},JWD["recieve"],5]//Grid
TakeSmallestBy[dict->{"Element","Value"},JWD["seperate"],5]//Grid
TakeSmallestBy[dict->{"Element","Value"},JWD["untill"],5]//Grid
TakeSmallestBy[dict->{"Element","Value"},JWD["wich"],5]//Grid</syntaxhighlight>
{{out}}
<pre>accommodate 0.0181818
accommodated 0.0333333
accommodates 0.0333333
accommodation 0.0815385
accommodating 0.0815385
definitely 0.04
defiantly 0.0422222
definably 0.0622222
definitively 0.07
define 0.08
government 0.0422222
governments 0.0585859
govern 0.0666667
governmental 0.0722222
governs 0.0952381
occurred 0.025
occur 0.0571429
occupied 0.0785714
occurs 0.0904762
cured 0.0952381
publicly 0.04
public 0.08
publican 0.085
publicans 0.104444
publicity 0.10444
receive 0.0333333
receives 0.0625
received 0.0625
receiver 0.0625
reeve 0.0761905
desperate 0.0787037
separate 0.0916667
separateness 0.106944
sprat 0.1125
separated 0.114352
until 0.0333333
untiled 0.0904762
untiles 0.0904762
unlit 0.0977778
untypically 0.106061
winch 0.0533333
witch 0.0533333
which 0.06
switch 0.111111
twitch 0.111111</pre>
=={{header|Nim}}==
{{trans|Go}}
<syntaxhighlight lang="nim">import lenientops
func jaroSim(s1, s2: string): float =
if s1.len == 0 and s2.len == 0: return 1
if s1.len == 0 or s2.len == 0: return 0
let matchDistance = max(s1.len, s2.len) div 2 - 1
var s1Matches = newSeq[bool](s1.len)
var s2Matches = newSeq[bool](s2.len)
var matches = 0
for i in 0..s1.high:
for j in max(0, i - matchDistance)..min(i + matchDistance, s2.high):
if not s2Matches[j] and s1[i] == s2[j]:
s1Matches[i] = true
s2Matches[j] = true
inc matches
break
if matches == 0: return 0
var transpositions = 0.0
var k = 0
for i in ..s1.high:
if not s1Matches[i]: continue
while not s2Matches[k]: inc k
if s1[i] != s2[k]: transpositions += 0.5
inc k
result = (matches / s1.len + matches / s2.len + (matches - transpositions) / matches) / 3
func jaroWinklerDist(s, t: string): float =
let ls = s.len
let lt = t.len
var lmax = if ls < lt: ls else: lt
if lmax > 4: lmax = 4
var l = 0
for i in 0..<lmax:
if s[i] == t[i]: inc l
let js = jaroSim(s, t)
let p = 0.1
let ws = js + float(l) * p * (1 - js)
result = 1 - ws
when isMainModule:
import algorithm, sequtils, strformat
type Wd = tuple[word: string; dist: float]
func `<`(w1, w2: Wd): bool =
if w1.dist < w2.dist: true
elif w1.dist == w2.dist: w1.word < w2.word
else: false
const Misspelt = ["accomodate", "definately", "goverment", "occured",
"publically", "recieve", "seperate", "untill", "wich"]
let words = toSeq("unixdict.txt".lines)
for ms in Misspelt:
var closest: seq[Wd]
for word in words:
if word.len == 0: continue
let jwd = jaroWinklerDist(ms, word)
if jwd < 0.15:
closest.add (word, jwd)
echo "Misspelt word: ", ms, ":"
closest.sort()
for i, c in closest:
echo &"{c.dist:0.4f} {c.word}"
if i == 5: break
echo()</syntaxhighlight>
{{out}}
<pre>Misspelt word: accomodate:
0.0182 accommodate
0.1044 accordant
0.1136 accolade
0.1219 acclimate
0.1327 accompanist
0.1333 accord
Misspelt word: definately:
0.0800 define
0.0850 definite
0.0886 defiant
0.1200 definitive
0.1219 designate
0.1267 deflate
Misspelt word: goverment:
0.0667 govern
0.1167 governor
0.1175 governess
0.1330 governance
0.1361 coverlet
0.1367 sovereignty
Misspelt word: occured:
0.0250 occurred
0.0571 occur
0.0952 occurrent
0.1056 occlude
0.1217 concurred
0.1429 cure
Misspelt word: publically:
0.0800 public
0.1327 publication
0.1400 pull
0.1492 pullback
Misspelt word: recieve:
0.0333 receive
0.0667 relieve
0.0762 reeve
0.0852 receptive
0.0852 recessive
0.0905 recife
Misspelt word: seperate:
0.0708 desperate
0.0917 separate
0.1042 temperate
0.1167 selenate
0.1167 sept
0.1167 sewerage
Misspelt word: untill:
0.0333 until
0.1111 till
0.1333 huntsville
0.1357 instill
0.1422 unital
Misspelt word: wich:
0.0533 winch
0.0533 witch
0.0600 which
0.0857 wichita
0.1111 switch
0.1111 twitch</pre>
=={{header|Perl}}==
<
use warnings;
use List::Util qw(min max head);
Line 712 ⟶ 1,712:
$J{$_} = jaro_winkler($word, $_) for @words;
print "\nClosest 5 dictionary words with a Jaro-Winkler distance < .15 from '$word':\n";
printf "%15s : %0.4f\n", $_, $J{$_}
for head 5, sort { $J{$a} <=> $J{$b} or $a cmp $b } grep { $J{$_} < 0.15 } keys %J;
}</
{{out}}
<pre style="height:40ex">Closest 5 dictionary words with a Jaro-Winkler distance < .15 from 'accomodate':
Line 780 ⟶ 1,780:
=={{header|Phix}}==
Uses jaro() from [[Jaro_distance#Phix]] (reproduced below for your convenience) and
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">function</span> <span style="color: #000000;">jaro</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">str1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">str2</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">str1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">trim</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">upper</span><span style="color: #0000FF;">(</span><span style="color: #000000;">str1</span><span style="color: #0000FF;">))</span>
<span style="color: #000000;">str2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">trim</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">upper</span><span style="color: #0000FF;">(</span><span style="color: #000000;">str2</span><span style="color: #0000FF;">))</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">len1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">str1</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">len2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">str2</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">match_distance</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">len1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">len2</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">match_count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">half_transposed</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">len1</span><span style="color: #0000FF;">==</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">len2</span><span style="color: #0000FF;">==</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000080;font-style:italic;">-- count the number of matches</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">m1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">len1</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">m2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">len2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">len1</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">match_distance</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">to</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">len2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">match_distance</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">m2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">str1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">str2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">m1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #000000;">m2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #000000;">match_count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">match_count</span><span style="color: #0000FF;">==</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000080;font-style:italic;">-- count the number of half-transpositions</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">len1</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">m1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">while</span> <span style="color: #008080;">not</span> <span style="color: #000000;">m2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">do</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">half_transposed</span> <span style="color: #0000FF;">+=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">str1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">str2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">transpositions</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">half_transposed</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">not_transposed</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">match_count</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">transpositions</span>
<span style="color: #000080;font-style:italic;">--
-- return the average of:
-- percentage/fraction of the first string matched,
-- percentage/fraction of the second string matched, and
-- percentage/fraction of matches that were not transposed.
--</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">match_count</span><span style="color: #0000FF;">/</span><span style="color: #000000;">len1</span> <span style="color: #0000FF;">+</span>
<span style="color: #000000;">match_count</span><span style="color: #0000FF;">/</span><span style="color: #000000;">len2</span> <span style="color: #0000FF;">+</span>
<span style="color: #000000;">not_transposed</span><span style="color: #0000FF;">/</span><span style="color: #000000;">match_count</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">3</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">jaroWinklerDist</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">lm</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">({</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">),</span><span style="color: #000000;">4</span><span style="color: #0000FF;">}),</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_eq</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">lm</span><span style="color: #0000FF;">],</span><span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">lm</span><span style="color: #0000FF;">]))</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">jaro</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">))*(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">l</span><span style="color: #0000FF;">*</span><span style="color: #000000;">0.1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">mispelt</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"accomodate"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"definately"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"goverment"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"occured"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"publically"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"recieve"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"seperate"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"untill"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"wich"</span><span style="color: #0000FF;">},</span>
<span style="color: #000000;">words</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">unix_dict</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">jwds</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">words</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mispelt</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">ms</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mispelt</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nMisspelt word: %s :\n"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ms</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">words</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">jwds</span><span style="color: #0000FF;">[</span><span style="color: #000000;">w</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">jaroWinklerDist</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ms</span><span style="color: #0000FF;">,</span><span style="color: #000000;">words</span><span style="color: #0000FF;">[</span><span style="color: #000000;">w</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tags</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">custom_sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">jwds</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">words</span><span style="color: #0000FF;">)))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">6</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">tj</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tags</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
<span style="color: #000080;font-style:italic;">-- if jwds[tj]>0.15 then exit end if</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%0.4f %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">jwds</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tj</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">words</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tj</span><span style="color: #0000FF;">]})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
Output identical to <del>Go/Wren</del> Algol68
=={{header|Python}}==
<
Test Jaro-Winkler distance metric.
linuxwords.txt is from http://users.cs.duke.edu/~ola/ap/linuxwords
Line 875 ⟶ 1,928:
for w in within_distance(0.15, STR, 5):
print('{:>14} | {:6.4f}'.format(w, jaro_winkler_distance(STR, w)))
</
<pre>
Close dictionary words ( distance < 0.15 using Jaro-Winkler distance) to " accomodate " are:
Line 956 ⟶ 2,009:
using the unixdict.txt file from www.puzzlers.org
<syntaxhighlight lang="raku"
return 0 if $s eq $t;
Line 1,017 ⟶ 2,070:
printf "%15s : %0.4f\n", .key, .value for %result.grep({ .value < .15 }).sort({+.value, ~.key}).head(5);
}</
{{out}}
<pre>Closest 5 dictionary words with a Jaro-Winkler distance < .15 from accomodate:
Line 1,083 ⟶ 2,136:
=={{header|Rust}}==
{{trans|Python}}
<
use std::io::{self, BufRead};
Line 1,193 ⟶ 2,246:
Err(error) => eprintln!("{}", error),
}
}</
{{out}}
Line 1,270 ⟶ 2,323:
</pre>
=={{header|Sidef}}==
Reusing the ''jaro()'' function from the [[Jaro_similarity#Sidef|Jaro similarity]] task.
<syntaxhighlight lang="ruby">func jaro_winkler_distance(s,t) {
var jaro_similarity = jaro(s, t)
var prefix = 0
for i in (0 .. min(3, s.len, t.len)) {
s.char(i) == t.char(i) ? ++prefix : break
}
1 - (prefix * 0.1 * (1 - jaro_similarity) + jaro_similarity)
}
# usage:
# sidef script.sf < unixdict.txt
var words = ARGF.slurp.words
%w(accomodate definately goverment occured publically recieve seperate untill wich).each {|word|
var result = Hash(words.map { (_, jaro_winkler_distance(word, _)) }...)
say "\nClosest 5 dictionary words with a Jaro-Winkler distance < .15 from #{word}:"
result.grep {|_,v| v < .15 }.sort_by{|_,v| v }.head(5).each_2d {|k,v|
printf("%15s : %0.4f\n", k, v)
}
}</syntaxhighlight>
{{out}}
<pre style="height:40ex">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
deflate : 0.1267
Closest 5 dictionary words with a Jaro-Winkler distance < .15 from goverment:
govern : 0.0667
governor : 0.1167
governess : 0.1175
governance : 0.1330
goer : 0.1481
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
Closest 5 dictionary words with a Jaro-Winkler distance < .15 from recieve:
receive : 0.0333
reeve : 0.0762
relieve : 0.0762
recessive : 0.0852
receptive : 0.0852
Closest 5 dictionary words with a Jaro-Winkler distance < .15 from seperate:
desperate : 0.0787
separate : 0.0917
temperate : 0.1157
sept : 0.1167
septate : 0.1306
Closest 5 dictionary words with a Jaro-Winkler distance < .15 from untill:
until : 0.0333
till : 0.1111
huntsville : 0.1333
unital : 0.1422
Closest 5 dictionary words with a Jaro-Winkler distance < .15 from wich:
witch : 0.0533
winch : 0.0533
which : 0.0600
wichita : 0.0857
twitch : 0.1111</pre>
=={{header|Swift}}==
{{trans|Rust}}
<
func loadDictionary(_ path: String) throws -> [String] {
Line 1,362 ⟶ 2,504:
} catch {
print(error.localizedDescription)
}</
{{out}}
Line 1,438 ⟶ 2,580:
witches | 0.1143
</pre>
=={{header|Typescript}}==
{{trans|Java}}
<syntaxhighlight lang="typescript">
var fs = require('fs')
// Jaro Winkler Distance Formula
function jaroDistance(string1: string, string2: string): number{
// Compute Jaro-Winkler distance between two string
// Swap strings if string1 is shorter than string 2
if (string1.length < string2.length){
const tempString: string = string1;
string1 = string2;
string2 = tempString
}
let len1: number = string1.length
let len2: number = string2.length
if (!len2){
return 0.0
}
const delta: number = Math.max(1, len1 / 2.0) - 1.0;
// Flags for transpositions
let flag: boolean[] = Array(len2).fill(false)
let ch1Match: string[] = Array(len1).fill('')
// Count number of matching characters
let matches = 0
// Check if characters on both string matches
for (let i: number = 0; i < len1; i++){
const ch1: string = string1[i]
for (let j = 0; j < len2; j++){
const ch2: string = string2[j]
if (j <= i + delta && j + delta >= 1 && ch1 == ch2 && !flag[j]){
flag[j] = true
ch1Match[matches++] = ch1;
break;
}
}
}
if (!matches){
return 1.0
}
// Count number of transpositions (shared characters placed in different positions)
let transpositions: number = 0.0
for (let i: number = 0, j: number = 0; j < len2; j++){
if (flag[j]){
if (string2[j] != ch1Match[i]){
transpositions++
}
i++
}
}
const m: number = matches
// Jaro Similarity Formula simj = ( (m / length of s1) + (m / length of s2) + (m - t) / m ) / 3
const jaro: number = (m / len1 + m / len2 + (m - transpositions / 2.0) / m) / 3.0
// Length of common prefix between string up to 4 characters
let commonPrefix: number = 0.0
len2 = Math.min(4, len2)
for (let i: number = 0; i < len2; i++){
if (string1[i] == string2[i]){
commonPrefix++
}
}
// Jaro Winkler Distance Formula simw = simj + lp(1 - simj)
return 1.0 - (jaro + commonPrefix * 0.1 * (1.0 - jaro))
}
// Compute Jaro Winkler Distance for every word on the dictionary against the misspelled word
function withinDistance(words: string[] ,maxDistance: number, string: string, maxToReturn: number): (string | number)[][]{
let result: (string | number)[][] = new Array()
words.forEach(word =>{
const distance = jaroDistance(word, string)
// check if computed jaro winkler distance is within the set distance parameter
if (distance <= maxDistance){
const tuple = [distance, word]
result.push(tuple)
}
})
result.sort()
// Limit of matches set to maxtoReturn
return result.length <= maxToReturn ? result : result.slice(0, maxToReturn)
}
function loadDictionary(fileName: string): string[]{
let words: string[] = new Array()
try{
//attacomsian.com/blog/reading-a-file-line-by-line-in-nodejs
const data = fs.readFileSync(fileName, 'utf-8')
const lines: string[] = data.split(/\r?\n/)
lines.forEach(line => {
words.push(line)
})
return words
}
catch(error){
console.log("Error reading dictionary")
}
}
function main(): void{
try {
const misspellings = [
"accomodate",
"definately",
"goverment",
"occured",
"publically",
"recieve",
"seperate",
"untill",
"wich"
]
//unixdict.txt from users.cs.duke.edu/~ola/ap/linuxwords
let words: string[] = loadDictionary("unixdict.txt")
misspellings.forEach(spelling =>{
console.log("Misspelling:", spelling)
const closeWord = withinDistance(words, 0.15, spelling, 5)
closeWord.forEach(word =>{
console.log((word[0] as number).toFixed(4) + " " + word[1])
})
console.log("")
})
}
catch(error) {
console.log("Error on main")
}
}
main();
</syntaxhighlight>
{{out}}
<pre>
Misspelling: accomodate
0.0364 accommodate
0.0515 accommodated
0.0515 accommodates
0.0979 accommodating
0.0979 accommodation
Misspelling: definately
0.0564 definitely
0.0586 defiantly
0.0909 define
0.0977 definite
0.1013 defiant
Misspelling: goverment
0.0533 government
0.0667 govern
0.0697 governments
0.0833 governmental
0.0952 governs
Misspelling: occured
0.0250 occurred
0.0571 occur
0.0786 occupied
0.0905 occurs
0.0917 accursed
Misspelling: publically
0.0400 publicly
0.0800 public
0.1044 publicity
0.1327 publication
0.1400 biblically
Misspelling: recieve
0.0333 receive
0.0625 received
0.0625 receiver
0.0625 receives
0.0667 relieve
Misspelling: seperate
0.0708 desperate
0.1042 temperate
0.1083 separate
0.1167 repeated
0.1167 sept
Misspelling: untill
0.0333 until
0.1067 untie
0.1083 untimely
0.1111 till
0.1264 Antilles
Misspelling: wich
0.0533 witch
0.0600 which
0.1111 switch
0.1111 twitch
0.1143 witches
</pre>
=={{header|V (Vlang)}}==
{{trans|Go}}
<syntaxhighlight lang="v (vlang)">import os
fn jaro_sim(str1 string, str2 string) f64 {
if str1.len == 0 && str2.len == 0 {
return 1
}
if str1.len == 0 || str2.len == 0 {
return 0
}
mut match_distance := str1.len
if str2.len > match_distance {
match_distance = str2.len
}
match_distance = match_distance/2 - 1
mut str1_matches := []bool{len: str1.len}
mut str2_matches := []bool{len: str2.len}
mut matches := 0.0
mut transpositions := 0.0
for i in 0..str1.len {
mut start := i - match_distance
if start < 0 {
start = 0
}
mut end := i + match_distance + 1
if end > str2.len {
end = str2.len
}
for k in start..end {
if str2_matches[k] {
continue
}
if str1[i] != str2[k] {
continue
}
str1_matches[i] = true
str2_matches[k] = true
matches++
break
}
}
if matches == 0 {
return 0
}
mut k := 0
for i in 0.. str1.len {
if !str1_matches[i] {
continue
}
for !str2_matches[k] {
k++
}
if str1[i] != str2[k] {
transpositions++
}
k++
}
transpositions /= 2
return (matches/f64(str1.len) +
matches/f64(str2.len) +
(matches-transpositions)/matches) / 3
}
fn jaro_winkler_dist(s string, t string) f64 {
ls := s.len
lt := t.len
mut lmax := lt
if ls < lt {
lmax = ls
}
if lmax > 4 {
lmax = 4
}
mut l := 0
for i in 0 .. lmax {
if s[i] == t[i] {
l++
}
}
js := jaro_sim(s, t)
p := 0.1
ws := js + f64(l)*p*(1-js)
return 1 - ws
}
struct Wd {
word string
dist f64
}
fn main() {
misspelt := [
"accomodate", "definately", "goverment", "occured", "publically",
"recieve", "seperate", "untill", "wich",
]
words := os.read_lines('unixdict.txt')?
for ms in misspelt {
mut closest := []Wd{}
for word in words {
if word == "" {
continue
}
jwd := jaro_winkler_dist(ms, word)
if jwd < 0.15 {
closest << Wd{word, jwd}
}
}
println("Misspelt word: $ms:")
closest.sort(a.dist<b.dist)
for i, c in closest {
println("${c.dist:.4f} ${c.word}")
if i == 5 {
break
}
}
println('')
}
}</syntaxhighlight>
{{out}}
<pre>
Misspelt word: accomodate :
0.0182 accommodate
0.1044 accordant
0.1136 accolade
0.1219 acclimate
0.1327 accompanist
0.1333 accord
Misspelt word: definately :
0.0800 define
0.0850 definite
0.0886 defiant
0.1200 definitive
0.1219 designate
0.1267 deflate
Misspelt word: goverment :
0.0667 govern
0.1167 governor
0.1175 governess
0.1330 governance
0.1361 coverlet
0.1367 sovereignty
Misspelt word: occured :
0.0250 occurred
0.0571 occur
0.0952 occurrent
0.1056 occlude
0.1217 concurred
0.1429 cure
Misspelt word: publically :
0.0800 public
0.1327 publication
0.1400 pull
0.1492 pullback
Misspelt word: recieve :
0.0333 receive
0.0667 relieve
0.0762 reeve
0.0852 receptive
0.0852 recessive
0.0905 recife
Misspelt word: seperate :
0.0708 desperate
0.0917 separate
0.1042 temperate
0.1167 selenate
0.1167 sewerage
0.1167 sept
Misspelt word: untill :
0.0333 until
0.1111 till
0.1333 huntsville
0.1357 instill
0.1422 unital
Misspelt word: wich :
0.0533 winch
0.0533 witch
0.0600 which
0.0857 wichita
0.1111 switch
0.1111 twitch
</pre>
Line 1,444 ⟶ 2,972:
{{libheader|Wren-sort}}
This uses unixdict and borrows code from the [[Jaro_distance#Wren]] task.
<
import "./fmt" for Fmt
import "./sort" for Sort
var jaroSim = Fn.new { |s1, s2|
Line 1,516 ⟶ 3,044:
for (c in closest.take(6)) Fmt.print("$0.4f $s", c[1], c[0])
System.print()
}</
{{out}}
|