Jaro-Winkler distance: Difference between revisions
Content deleted Content added
→{{header|Swift}}: Separated Vlang entry. |
Added Sidef |
||
(6 intermediate revisions by 5 users not shown) | |||
Line 2:
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 76:
{{trans|Python}}
<
V MISSPELLINGS = [‘accomodate’,
‘definately’,
Line 123:
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)))</
{{out}}
Line 155:
=={{header|Elm}}==
Author: zh5
<
Line 317:
else
result
</syntaxhighlight>
=={{header|ALGOL 68}}==
Line 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 457:
print( ( newline ) )
OD
FI</
{{out}}
<pre>
Line 535:
=={{header|C++}}==
{{trans|Swift}}
<
#include <cstdlib>
#include <fstream>
Line 638:
}
return EXIT_SUCCESS;
}</
{{out}}
Line 718:
=={{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 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 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 889:
fmt.Println()
}
}</
{{out}}
Line 967:
Implementation:
<
Eq=. (x=/y)*(<.<:-:x>.&#y)>:|x -/&i.&# y
xM=. (+./"1 Eq)#x
Line 981:
simj=. x jaro y
-.simj + l*p*-.simj
}}</
Task example:
<
words=. <;._2 fread '/usr/share/dict/words'
for_word. ;:'accomodate definately goverment occured publically recieve seperate untill wich' do.
Line 1,040:
0.0533333 winch
0.0533333 witch
</syntaxhighlight>
=={{header|Java}}==
{{trans|C++}}
<
import java.util.*;
Line 1,152:
}
}
}</
{{out}}
Line 1,236:
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.
<
def length_of_common_prefix($s1; $s2):
Line 1,267:
(.[] | "\(.[0] | lpad(21)) : \(.[-1] * 1000 | round / 1000)") ;
task</
{{out}}
Invocation: jq -rRn -f program.jq unixdict.txt
Line 1,322:
=={{header|Julia}}==
<
const words = read("linuxwords.txt", String) |> split .|> strip
Line 1,372:
end
end
</
<pre>
Close dictionary words ( distance < 0.15 using Jaro-Winkler distance) to 'accomodate' are:
Line 1,448:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
JWD[a_][b_]:=Experimental`JaroWinklerDistance[a,b]
dict=DictionaryLookup[];
Line 1,459:
TakeSmallestBy[dict->{"Element","Value"},JWD["seperate"],5]//Grid
TakeSmallestBy[dict->{"Element","Value"},JWD["untill"],5]//Grid
TakeSmallestBy[dict->{"Element","Value"},JWD["wich"],5]//Grid</
{{out}}
<pre>accommodate 0.0181818
Line 1,517:
=={{header|Nim}}==
{{trans|Go}}
<
func jaroSim(s1, s2: string): float =
Line 1,589:
echo &"{c.dist:0.4f} {c.word}"
if i == 5: break
echo()</
{{out}}
Line 1,662:
=={{header|Perl}}==
<
use warnings;
use List::Util qw(min max head);
Line 1,714:
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 1,781:
=={{header|Phix}}==
Uses jaro() from [[Jaro_distance#Phix]] (reproduced below for your convenience) and the standard unix_dict()
<!--<
<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>
Line 1,858:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
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 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 2,009:
using the unixdict.txt file from www.puzzlers.org
<syntaxhighlight lang="raku"
return 0 if $s eq $t;
Line 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 2,136:
=={{header|Rust}}==
{{trans|Python}}
<
use std::io::{self, BufRead};
Line 2,246:
Err(error) => eprintln!("{}", error),
}
}</
{{out}}
Line 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 2,415 ⟶ 2,504:
} catch {
print(error.localizedDescription)
}</
{{out}}
Line 2,493 ⟶ 2,582:
</pre>
=={{header|
{{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 {
Line 2,611 ⟶ 2,894:
println('')
}
}</
{{out}}
Line 2,689 ⟶ 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 2,761 ⟶ 3,044:
for (c in closest.take(6)) Fmt.print("$0.4f $s", c[1], c[0])
System.print()
}</
{{out}}
|