Jaro similarity: Difference between revisions
Add C# implementation
(added python) |
(Add C# implementation) |
||
| (136 intermediate revisions by 49 users not shown) | |||
Line 1:
{{task}}
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
: <math>d_j = \left\{
Line 14 ⟶ 16:
Where:
* <math>m</math> is the number of ''matching characters''
* <math>t</math> is half the number of ''transpositions''
Two characters from <math>s_1</math> and <math>s_2</math> respectively, are considered ''matching'' only if they are the same and not farther apart than <math>\left\lfloor\frac{\max(|s_1|,|s_2|)}{2}\right\rfloor-1</math> characters.
Each character of <math>s_1</math> is compared with all its matching characters in <math>s_2</math>. 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 <math>s_1</math> ''DWAYNE'' and <math>s_2</math> ''DUANE'' we find:
* <math>m = 4</math>
Line 41 ⟶ 42:
;Task
Implement the Jaro
* ("MARTHA", "MARHTA")
Line 50 ⟶ 51:
; See also
* [[wp:Jaro-Winkler_distance|Jaro–Winkler distance]] on Wikipedia.
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F jaro(s, t)
V s_len = s.len
V t_len = t.len
I s_len == 0 & t_len == 0
R 1.0
V match_distance = (max(s_len, t_len) I/ 2) - 1
V s_matches = [0B] * s_len
V t_matches = [0B] * t_len
V matches = 0
V transpositions = 0
L(i) 0 .< s_len
V start = max(0, i - match_distance)
V end = min(i + match_distance + 1, t_len)
L(j) start .< end
I t_matches[j]
L.continue
I s[i] != t[j]
L.continue
s_matches[i] = 1B
t_matches[j] = 1B
matches++
L.break
I matches == 0
R 0.0
V k = 0
L(i) 0 .< s_len
I !s_matches[i]
L.continue
L !t_matches[k]
k++
I s[i] != t[k]
transpositions++
k++
R ((Float(matches) / s_len) +
(Float(matches) / t_len) +
((matches - transpositions / 2) / matches)) / 3
L(s, t) [(‘MARTHA’, ‘MARHTA’),
(‘DIXON’, ‘DICKSONX’),
(‘JELLYFISH’, ‘SMELLYFISH’)]
print(‘jaro('#.', '#.') = #.10’.format(s, t, jaro(s, t)))</syntaxhighlight>
{{out}}
<pre>
jaro('MARTHA', 'MARHTA') = 0.9444444444
jaro('DIXON', 'DICKSONX') = 0.7666666667
jaro('JELLYFISH', 'SMELLYFISH') = 0.8962962963
</pre>
=={{header|Action!}}==
<syntaxhighlight lang="action">
DEFINE STRING="CHAR ARRAY" ; sys.act
DEFINE ASCII_SpaceBar="32"
INT FUNC JaroDistance(STRING str1, str2)
STRING Z(15)
INT S1, S2, J, M, N, L, I, K, skip, Max, Min
INT Result
Result=0
S1=str1(0)
S2=str2(0)
IF S1>S2 THEN
SCopy(Z,str1)
SCopy(str1,str2)
SCopy(str2,Z)
M=S1
S1=S2
S2=M
FI
J=1 M=0 N=0 L=S2/2 SCopy(Z,str2)
FOR I=1 TO S1 DO
skip=0
IF str1(I)=str2(J) THEN
M==+1
str2(J)=ASCII_SpaceBar
skip=1
FI
IF skip=0 THEN
Max=1
IF Max<(I-L) THEN Max=I-L FI
Min=S2
IF Min>(I+L-1) THEN Min=I+L-1 FI
FOR K=Max TO Min DO
IF str1(I)=str2(K) THEN
N==+1
M==+1
str2(K)=ASCII_SpaceBar
IF K>J THEN J=K FI
FI
OD
FI
IF J<S2 THEN J==+1 FI
OD
IF M=0 THEN
Result=0 ; Jaro distance
ELSE
N=N/2
Result=((M*100)/S1+(M*100)/S2+(((M-N)*100)/M))/3 ; Jaro distance
FI
; Min=S1 IF Min>S2 THEN Min=S2 FI
; M=Min IF M>3 THEN M=3 FI
; M==+1 L=0 SCopy(str2,Z)
; IF M>Min THEN M=Min FI
; FOR I=1 TO M DO
; IF str1(I)=str2(I) THEN
; L==+1
; ELSE
; EXIT
; FI
; OD
; Result=Result*100 + (((L*100)/10)*(100 - Result)) ; Jaro Winkler distance
; Result=(Result+49)/100
RETURN(Result)
PROC MAIN()
INT result
STRING Word_1(15), Word_2(15)
PUT(125)
PUTE()
SCopy(Word_1,"LIGITA") SCopy(Word_2,"LIGA")
PrintF("%S - %S%E",Word_1,Word_2)
result=JaroDistance(Word_1,Word_2)
PrintF("Jaro Distance=%U%E%E",result)
SCopy(Word_1,"ZEILANE") SCopy(Word_2,"ZEIDONE")
PrintF("%S - %S%E",Word_1,Word_2)
result=JaroDistance(Word_1,Word_2)
PrintF("Jaro Distance=%U%E%E",result)
SCopy(Word_1,"JELLYFISH") SCopy(Word_2,"SMELLYFISH")
PrintF("%S - %S%E",Word_1,Word_2)
result=JaroDistance(Word_1,Word_2)
PrintF("Jaro Distance=%U%E%E",result)
RETURN
</syntaxhighlight>
{{out}}
<pre>MARTHA, MARHTA: 94
DIXON, DICKSONX: 76
JELLYFISH, SMELLYFISH: 89
</pre>
=={{header|Ada}}==
<syntaxhighlight lang="ada">with Ada.Text_IO;
procedure Jaro_Distances is
type Jaro_Measure is new Float;
function Jaro_Distance (Left, Right : in String) return Jaro_Measure
is
Left_Matches : array (Left'Range) of Boolean := (others => False);
Right_Matches : array (Right'Range) of Boolean := (others => False);
Matches : Natural := 0;
Transpositions : Natural := 0;
begin
if Left'Length = 0 and Right'Length = 0 then
return 1.000;
end if;
declare
Match_Distance : constant Natural := Natural'Max (Left'Length, Right'Length) / 2 - 1;
begin
for L in Left'Range loop
declare
First : constant Natural := Natural'Max (Right'First, Right'First + L - Left'First - Match_Distance);
Last : constant Natural := Natural'Min (L - Left'First + Match_Distance + Right'First, Right'Last);
begin
for R in First .. Last loop
if
not Right_Matches (R) and
Left (L) = Right (R)
then
Left_Matches (L) := True;
Right_Matches (R) := True;
Matches := Matches + 1;
exit;
end if;
end loop;
end;
end loop;
end;
if Matches = 0 then
return 0.000;
end if;
declare
R : Natural := Right'First;
begin
for L in Left'Range loop
if Left_Matches (L) then
while not Right_Matches (R) loop
R := R + 1;
end loop;
if Left (L) /= Right (R) then
Transpositions := Transpositions + 1;
end if;
R := R + 1;
end if;
end loop;
end;
declare
Match : constant Float := Float (Matches);
Term_1 : constant Float := Match / Float (Left'Length);
Term_2 : constant Float := Match / Float (Right'Length);
Term_3 : constant Float := (Match - Float (Transpositions) / 2.0) / Match;
begin
return Jaro_Measure ((Term_1 + Term_2 + Term_3) / 3.0);
end;
end Jaro_Distance;
procedure Show_Jaro (Left, Right : in String)
is
package Jaro_IO is
new Ada.Text_IO.Float_IO (Jaro_Measure);
use Ada.Text_IO;
Distance : constant Jaro_Measure := Jaro_Distance (Left, Right);
begin
Jaro_IO.Put (Distance, Fore => 1, Aft => 5, Exp => 0);
Set_Col (10); Put (Left);
Set_Col (22); Put (Right);
New_Line;
end Show_Jaro;
S1 : constant String := " MARTHA VS MARHTA ";
begin
Show_Jaro ("DWAYNE", "DUANE");
Show_Jaro ("DIXON", "DICKSONX");
Show_Jaro ("JELLYFISH", "SMELLYFISH");
Show_Jaro (S1 (3 .. 8), S1 (13 .. 18));
end Jaro_Distances;</syntaxhighlight>
{{out}}
<pre>0.82222 DWAYNE DUANE
0.76667 DIXON DICKSONX
0.89630 JELLYFISH SMELLYFISH
0.94444 MARTHA MARHTA</pre>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program jarodist.s */
/* Constantes */
.equ BUFFERSIZE, 100
.equ STDIN, 0 @ Linux input console
.equ STDOUT, 1 @ Linux output console
.equ EXIT, 1 @ Linux syscall
.equ READ, 3 @ Linux syscall
.equ WRITE, 4 @ Linux syscall
.equ SIZESTRING, 256
/* Initialized data */
.data
szCarriageReturn: .asciz "\n"
szMessResult: .ascii " Jaro distance * 1000 = " @ message result
sMessValeur: .fill 12, 1, ' '
.asciz "\n"
szMessDeb: .asciz "For : "
szMessSep: .asciz " and "
szString1: .asciz "DWAYNE"
szString1A: .asciz "DUANE"
szString2: .asciz "MARTHA"
szString2A: .asciz "MARHTA"
szString3: .asciz "DIXON"
szString3A: .asciz "DICKSONX"
szString4: .asciz "JELLYFISH"
szString4A: .asciz "SMELLYFISH"
/* UnInitialized data */
.bss
iTabString1: .skip 4 * SIZESTRING
iTabString2: .skip 4 * SIZESTRING
sBuffer: .skip BUFFERSIZE
/* code section */
.text
.global main
main: @ entry of program
ldr r0,iAdrszString1 @ address string 1
ldr r1,iAdrszString1A @ address string 2
bl preparation @ compute jaro distance
ldr r0,iAdrszString2 @ address string 1
ldr r1,iAdrszString2A @ address string 2
bl preparation @ compute jaro distance
ldr r0,iAdrszString3 @ address string 1
ldr r1,iAdrszString3A @ address string 2
bl preparation @ compute jaro distance
ldr r0,iAdrszString4 @ address string 1
ldr r1,iAdrszString4A @ address string 2
bl preparation @ compute jaro distance
100: @ standard end of the program
mov r0, #0 @ return code
pop {fp,lr} @restaur 2 registers
mov r7, #EXIT @ request to exit program
swi 0 @ perform the system call
iAdrsMessValeur: .int sMessValeur
iAdrsBuffer: .int sBuffer
iAdrszMessResult: .int szMessResult
iAdrszCarriageReturn: .int szCarriageReturn
iAdrszMessDeb: .int szMessDeb
iAdrszMessSep: .int szMessSep
iAdrszString1: .int szString1
iAdrszString1A: .int szString1A
iAdrszString2: .int szString2
iAdrszString2A: .int szString2A
iAdrszString3: .int szString3
iAdrszString3A: .int szString3A
iAdrszString4: .int szString4
iAdrszString4A: .int szString4A
/******************************************************************/
/* preparation compute */
/******************************************************************/
/* r0 contains the address of the first string */
/* r1 contains the address of the second string */
preparation:
push {r2,lr} @ save registers
mov r2,r0 @ save first address
ldr r0,iAdrszMessDeb @ display the two strings
bl affichageMess
mov r0,r2
bl affichageMess
ldr r0,iAdrszMessSep
bl affichageMess
mov r0,r1
bl affichageMess
mov r0,r2 @ address string 1
@ and r1 contains address string 2
bl jaroDistance @ compute jaro distance
@ conversion register to string
ldr r1,iAdrsMessValeur
bl conversion10 @ conversion register to string
ldr r0,iAdrszMessResult
bl affichageMess @ display message
100:
pop {r2,lr} @ restaur registers
bx lr @ return
/******************************************************************/
/* Compute Jaro distance */
/******************************************************************/
/* r0 contains the address of the first string */
/* r1 contains the address of the second string */
/* r0 returns jaro distance * 1000 because not use float compute !!! */
jaroDistance:
push {r1-r11,lr} @ save registers
mov r6,r0 @ save address string 1
bl strLength @ size string
cmp r0,#0 @ empty string ?
beq 100f
mov r4,r0
mov r0,r1
bl strLength @ size string 2
cmp r0,#0 @ empty string ?
beq 100f
mov r5,r0
mov r2,#0 @ initialisation tables 1 and 2
mov r3,#0
ldr r7,iadriTabString1
ldr r8,iadriTabString2
1: @loop start
str r3,[r7,r2,lsl #2]
str r3,[r8,r2,lsl #2]
add r2,#1
cmp r2,#SIZESTRING
blt 1b
cmp r4,r5 @ compute match distance
lsrle r3,r5,#1 @ length max / 2
lsrgt r3,r4,#1
sub r3,#1 @ - 1
sub r4,#1 @ last index string 1
sub r5,#1 @ last index string 2
mov r11,#0 @ match counter
mov r2,#0 @ index loop
2: @ loop match
subs r7,r2,r3
movlt r7,#0 @ compute start
add r8,r2,r3
add r8,#1
cmp r8,r5
movgt r8,r5 @ compute end
3:
ldr r10,iadriTabString2 @ load element table 2 at location r7
ldr r9,[r10,r7,lsl #2]
cmp r9,#0 @ if not zero continue
bne 4f
ldrb r9,[r6,r2] @ compare characters of two strings
ldrb r10,[r1,r7]
cmp r9,r10
bne 4f @ not equal
ldr r10,iadriTabString2 @ match
mov r9,#1 @ store 1 in two tables
str r9,[r10,r7,lsl #2]
ldr r10,iadriTabString1
str r9,[r10,r2,lsl #2]
add r11,#1 @ increment counter match
b 5f @ end loop 2
4:
add r7,#1 @ following character string 2
cmp r7,r8 @ end ?
ble 3b
5:
add r2,#1 @ following character string 1
cmp r2,r4 @ end string ?
ble 2b
cmp r11,#0 @ return if 0 match
moveq r0,#0
beq 100f
/* compute transposition */
mov r2,#0 @ loop indice
mov r3,#0 @ indice string 2
mov r7,#0 @ counter transposition
6:
ldr r10,iadriTabString1 @ character match ?
ldr r9,[r10,r2,lsl #2]
cmp r9,#0
beq 8f @ no
ldr r10,iadriTabString2
7:
ldr r9,[r10,r3,lsl #2] @ yes, search match in table 2
cmp r9,#0
addeq r3,#1
beq 7b
ldrb r9,[r6,r2] @ compare characters
ldrb r10,[r1,r3]
cmp r9,r10
addne r7,#1 @ not equals add 1 to counter
add r3,#1 @ following characters string 2
8:
add r2,#1 @ following characters string 1
cmp r2,r4 @ end string ?
ble 6b @ no loop
lsr r7,#1 @ counter / 2
/* Final */
mov r6,#1000 @ factor 1000 for not use float compute !!!
mul r9,r6,r11 @ compute match * 1000
mul r7,r6,r7 @ compute transposition * 1000
mov r0,r9 @ match
add r1,r4,#1 @ size string 1
bl division
mov r8,r2
mov r0,r9 @ match
add r1,r5,#1 @ size string 2
bl division
add r8,r2
sub r0,r9,r7 @ compute match - transposition
mov r1,r11 @ match
bl division
add r8,r2
mov r0,r8 @ division total / 3
mov r1,#3
bl division
mov r0,r2 @ return value
100:
pop {r1-r11,lr} @ restaur registers
bx lr @ return
iadriTabString1: .int iTabString1
iadriTabString2: .int iTabString2
/******************************************************************/
/* display text with size calculation */
/******************************************************************/
/* r0 contains the address of the message */
affichageMess:
push {r0,r1,r2,r7,lr} @ save registres
mov r2,#0 @ counter length
1: @ loop length calculation
ldrb r1,[r0,r2] @ read octet start position + index
cmp r1,#0 @ if 0 its over
addne r2,r2,#1 @ else add 1 in the length
bne 1b @ and loop
@ so here r2 contains the length of the message
mov r1,r0 @ address message in r1
mov r0,#STDOUT @ code to write to the standard output Linux
mov r7, #WRITE @ code call system "write"
svc #0 @ call systeme
pop {r0,r1,r2,r7,lr} @ restaur des 2 registres */
bx lr @ return
/******************************************************************/
/* Converting a register to a decimal unsigned */
/******************************************************************/
/* r0 contains value and r1 address area */
/* r0 return size of result (no zero final in area) */
/* area size => 11 bytes */
.equ LGZONECAL, 10
conversion10:
push {r1-r4,lr} @ save registers
mov r3,r1
mov r2,#LGZONECAL
1: @ start loop
bl divisionpar10U @unsigned r0 <- dividende. quotient ->r0 reste -> r1
add r1,#48 @ digit
strb r1,[r3,r2] @ store digit on area
cmp r0,#0 @ stop if quotient = 0
subne r2,#1 @ else previous position
bne 1b @ and loop
@ and move digit from left of area
mov r4,#0
2:
ldrb r1,[r3,r2]
strb r1,[r3,r4]
add r2,#1
add r4,#1
cmp r2,#LGZONECAL
ble 2b
@ and move spaces in end on area
mov r0,r4 @ result length
mov r1,#' ' @ space
3:
strb r1,[r3,r4] @ store space in area
add r4,#1 @ next position
cmp r4,#LGZONECAL
ble 3b @ loop if r4 <= area size
100:
pop {r1-r4,lr} @ restaur registres
bx lr @return
/***************************************************/
/* division par 10 unsigned */
/***************************************************/
/* r0 dividende */
/* r0 quotient */
/* r1 remainder */
divisionpar10U:
push {r2,r3,r4, lr}
mov r4,r0 @ save value
//mov r3,#0xCCCD @ r3 <- magic_number lower raspberry 3
//movt r3,#0xCCCC @ r3 <- magic_number higter raspberry 3
ldr r3,iMagicNumber @ r3 <- magic_number raspberry 1 2
umull r1, r2, r3, r0 @ r1<- Lower32Bits(r1*r0) r2<- Upper32Bits(r1*r0)
mov r0, r2, LSR #3 @ r2 <- r2 >> shift 3
add r2,r0,r0, lsl #2 @ r2 <- r0 * 5
sub r1,r4,r2, lsl #1 @ r1 <- r4 - (r2 * 2) = r4 - (r0 * 10)
pop {r2,r3,r4,lr}
bx lr @ leave function
iMagicNumber: .int 0xCCCCCCCD
/***************************************************/
/* calcul size string */
/***************************************************/
/* r0 string address */
/* r0 returns size string */
strLength:
push {r1,r2,lr}
mov r1,#0 @ init counter
1:
ldrb r2,[r0,r1] @ load byte of string index r1
cmp r2,#0 @ end string ?
addne r1,#1 @ no -> +1 counter
bne 1b @ and loop
100:
mov r0,r1
pop {r1,r2,lr}
bx lr
/***************************************************/
/* integer division unsigned */
/***************************************************/
division:
/* r0 contains dividend */
/* r1 contains divisor */
/* r2 returns quotient */
/* r3 returns remainder */
push {r4, lr}
mov r2, #0 @ init quotient
mov r3, #0 @ init remainder
mov r4, #32 @ init counter bits
b 2f
1: @ loop
movs r0, r0, LSL #1 @ r0 <- r0 << 1 updating cpsr (sets C if 31st bit of r0 was 1)
adc r3, r3, r3 @ r3 <- r3 + r3 + C. This is equivalent to r3 ? (r3 << 1) + C
cmp r3, r1 @ compute r3 - r1 and update cpsr
subhs r3, r3, r1 @ if r3 >= r1 (C=1) then r3 <- r3 - r1
adc r2, r2, r2 @ r2 <- r2 + r2 + C. This is equivalent to r2 <- (r2 << 1) + C
2:
subs r4, r4, #1 @ r4 <- r4 - 1
bpl 1b @ if r4 >= 0 (N=0) then loop
pop {r4, lr}
bx lr
</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">loop [
["MARTHA" "MARHTA"]
["DIXON" "DICKSONX"]
["JELLYFISH" "SMELLYFISH"]
] 'pair ->
print [pair "-> Jaro similarity:" round.to: 3 jaro first pair last pair]</syntaxhighlight>
{{out}}
<pre>[MARTHA MARHTA] -> Jaro similarity: 0.944
[DIXON DICKSONX] -> Jaro similarity: 0.767
[JELLYFISH SMELLYFISH] -> Jaro similarity: 0.896</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f JARO_DISTANCE.AWK
BEGIN {
main("DWAYNE","DUANE")
main("MARTHA","MARHTA")
main("DIXON","DICKSONX")
main("JELLYFISH","SMELLYFISH")
exit(0)
}
function main(str1,str2) {
printf("%9.7f '%s' '%s'\n",jaro(str1,str2),str1,str2)
}
function jaro(str1,str2, begin,end,i,j,k,leng1,leng2,match_distance,matches,str1_arr,str2_arr,transpositions) {
leng1 = length(str1)
leng2 = length(str2)
if (leng1 == 0 && leng2 == 0) { # both strings are empty
return(1)
}
if (leng1 == 0 || leng2 == 0) { # only one string is empty
return(0)
}
match_distance = int(max(leng1,leng2)/2-1)
for (i=1; i<=leng1; i++) { # find matches
begin = int(max(0,i-match_distance))
end = int(min(i+match_distance+1,leng2))
for (j=begin; j<=end; j++) {
if (str2_arr[j]) { continue }
if (substr(str1,i,1) != substr(str2,j,1)) { continue }
str1_arr[i] = 1
str2_arr[j] = 1
matches++
break
}
}
if (matches == 0) {
return(0)
}
k = 0
for (i=1; i<=leng1; i++) { # count transpositions
if (!str1_arr[i]) { continue }
while (!str2_arr[k]) {
k++
}
if (substr(str1,i,1) != substr(str2,k,1)) {
transpositions++
}
k++
}
transpositions /= 2
return((matches/leng1)+(matches/leng2)+((matches-transpositions)/matches))/3
}
function max(x,y) { return((x > y) ? x : y) }
function min(x,y) { return((x < y) ? x : y) }
</syntaxhighlight>
{{out}}
<pre>
0.8222222 'DWAYNE' 'DUANE'
0.9444444 'MARTHA' 'MARHTA'
0.7666667 'DIXON' 'DICKSONX'
0.8962963 'JELLYFISH' 'SMELLYFISH'
</pre>
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<syntaxhighlight lang="bbcbasic"> PRINT "Jaro similarity between the two strings:"
PROCDescribeJaro("MARTHA", "MARHTA")
PROCDescribeJaro("DIXON", "DICKSONX")
PROCDescribeJaro("JELLYFISH", "SMELLYFISH")
PROCDescribeJaro("DWAYNE", "DUANE")
PROCDescribeJaro("a", "b")
PROCDescribeJaro("", "")
END
DEF FNMax(a, b)=(a + b + ABS(a - b)) / 2
DEF FNMin(a, b)=(a + b - ABS(a - b)) / 2
DEF PROCDescribeJaro(word1$, word2$)
LOCAL d%, i%, j%, k%, l1%, l2%, m%, t%
PRINT " '" word1$ "' and '" word2$ "'" TAB(30) "= ";
IF word1$ == "" IF word2$ == "" PRINT;1 : ENDPROC
l1%=LENword1$
l2%=LENword2$
IF l1% < l2% SWAP l1%, l2% SWAP word1$, word2$
d%=l1% / 2 - 1
j%=1
FOR i%=1 TO l2%
IF MID$(word2$, i%, 1) == MID$(word1$, j%, 1) THEN
m%+=1
MID$(word1$, j%)=" "
ELSE
FOR k%=FNMax(1, i% - d%) TO FNMin(l1%, i% + d%)
IF MID$(word2$, i%, 1) == MID$(word1$, k%, 1) THEN
t%+=1
m%+=1
MID$(word1$, k%)=" "
IF k% > j% j%=k%
ENDIF
NEXT
ENDIF
j%+=1
NEXT
IF m% == 0 THEN
PRINT;0
ELSE
PRINT;(m% / l2% + m% / l1% + ((m% - (t% >> 1)) / m%)) / 3
ENDIF
ENDPROC</syntaxhighlight>
{{out}}
<pre>Jaro similarity between the two strings:
'MARTHA' and 'MARHTA' = 0.944444444
'DIXON' and 'DICKSONX' = 0.766666667
'JELLYFISH' and 'SMELLYFISH' = 0.896296296
'DWAYNE' and 'DUANE' = 0.822222222
'a' and 'b' = 0
'' and '' = 1</pre>
=={{header|C}}==
<
#include <string.h>
#include <ctype.h>
Line 142 ⟶ 886:
printf("%f\n", jaro("DIXON", "DICKSONX"));
printf("%f\n", jaro("JELLYFISH", "SMELLYFISH"));
}</
{{out}}
<pre>
Line 149 ⟶ 893:
0.896296
</pre>
=={{header|C#}}==
{{trans|Java}}
<syntaxhighlight lang="C#">
using System;
public class JaroDistance {
public static double Jaro(string s, string t) {
int s_len = s.Length;
int t_len = t.Length;
if (s_len == 0 && t_len == 0) return 1;
int match_distance = Math.Max(s_len, t_len) / 2 - 1;
bool[] s_matches = new bool[s_len];
bool[] t_matches = new bool[t_len];
int matches = 0;
int transpositions = 0;
for (int i = 0; i < s_len; i++) {
int start = Math.Max(0, i - match_distance);
int end = Math.Min(i + match_distance + 1, t_len);
for (int j = start; j < end; j++) {
if (t_matches[j]) continue;
if (s[i] != t[j]) continue;
s_matches[i] = true;
t_matches[j] = true;
matches++;
break;
}
}
if (matches == 0) return 0;
int k = 0;
for (int i = 0; i < s_len; i++) {
if (!s_matches[i]) continue;
while (!t_matches[k]) k++;
if (s[i] != t[k]) transpositions++;
k++;
}
return (((double)matches / s_len) +
((double)matches / t_len) +
(((double)matches - transpositions / 2.0) / matches)) / 3.0;
}
public static void Main(string[] args) {
Console.WriteLine(Jaro("MARTHA", "MARHTA"));
Console.WriteLine(Jaro("DIXON", "DICKSONX"));
Console.WriteLine(Jaro("JELLYFISH", "SMELLYFISH"));
}
}
</syntaxhighlight>
{{out}}
<pre>
0.944444444444445
0.766666666666667
0.896296296296296
</pre>
=={{header|C++}}==
{{trans|C}}
<syntaxhighlight lang="cpp">#include <algorithm>
#include <iostream>
#include <string>
double jaro(const std::string s1, const std::string s2) {
const uint l1 = s1.length(), l2 = s2.length();
if (l1 == 0)
return l2 == 0 ? 1.0 : 0.0;
const uint match_distance = std::max(l1, l2) / 2 - 1;
bool s1_matches[l1];
bool s2_matches[l2];
std::fill(s1_matches, s1_matches + l1, false);
std::fill(s2_matches, s2_matches + l2, false);
uint matches = 0;
for (uint i = 0; i < l1; i++)
{
const int end = std::min(i + match_distance + 1, l2);
for (int k = std::max(0u, i - match_distance); k < end; k++)
if (!s2_matches[k] && s1[i] == s2[k])
{
s1_matches[i] = true;
s2_matches[k] = true;
matches++;
break;
}
}
if (matches == 0)
return 0.0;
double t = 0.0;
uint k = 0;
for (uint i = 0; i < l1; i++)
if (s1_matches[i])
{
while (!s2_matches[k]) k++;
if (s1[i] != s2[k]) t += 0.5;
k++;
}
const double m = matches;
return (m / l1 + m / l2 + (m - t) / m) / 3.0;
}
int main() {
using namespace std;
cout << jaro("MARTHA", "MARHTA") << endl;
cout << jaro("DIXON", "DICKSONX") << endl;
cout << jaro("JELLYFISH", "SMELLYFISH") << endl;
return 0;
}</syntaxhighlight>
=={{header|Clojure}}==
<syntaxhighlight lang="clojure">
(ns test-project-intellij.core
(:gen-class))
(defn find-matches [s t]
" find match locations in the two strings "
" s_matches is set to true wherever there is a match in t and t_matches is set conversely "
(let [s_len (count s)
t_len (count t)
match_distance (int (- (/ (max s_len t_len) 2) 1))
matches 0
transpositions 0
fn-start (fn [i] (max 0 (- i match_distance))) ; function to compute starting position
fn-end (fn [i] (min (+ i match_distance 1) (- t_len 1))) ] ; function to compute end position
(loop [i 0
start (fn-start i)
end (fn-end i)
k start
s_matches (vec (repeat (count s) false))
t_matches (vec (repeat (count t) false))
matches 0]
(if (< i s_len)
(if (<= k end)
(if (get t_matches k)
; continue with next k
(recur i start end (inc k) s_matches t_matches matches)
(if (= (get s i) (get t k))
; match a position, so update matches, s_matches, t_matches to reflect match
(recur (inc i) (fn-start (inc i)) (fn-end (inc i)) (fn-start (inc i)) (assoc s_matches i true) (assoc t_matches k true) (inc matches))
; no match so try next k
(recur i start end (inc k) s_matches t_matches matches)))
; End of k iterations, so increment i and set k to start based upon i
(recur (inc i) (fn-start (inc i)) (fn-end (inc i)) (fn-start (inc i)) s_matches t_matches matches))
; End of i iterations
[matches s_matches t_matches]))))
(defn count-transpositions [s t s_matches t_matches]
" Utility function to count the number of transpositions "
(let [s_len (count s)]
(loop [i 0
k 0
transpositions 0]
(if (< i s_len)
; still elements in s (since i < s_len)
(if (not (get s_matches i nil))
; skip to next i since there are no matches in s
(recur (inc i) k transpositions)
; checking for match in t
(if (not (get t_matches k nil))
; keeping looping around as long as there are no matches in t
(recur i (inc k) transpositions)
(if (not= (get s i) (get t k))
; increment transposition count (if strings don't equal at match location)
(recur (inc i) (inc k) (inc transpositions))
; was a match, so advance i and k without increasing transpositions count
(recur (inc i) (inc k) transpositions))))
; Return count
transpositions))))
(defn jaro [s t]
" Main Jaro Distance routine"
(if (= s t)
1
(let [[matches s_matches t_matches] (find-matches s t)]
(if (= 0 matches)
0
(let [s_len (count s)
t_len (count t)
transpositions (count-transpositions s t s_matches t_matches)]
(float (/ (+ (/ matches s_len) (/ matches t_len) (/ (- matches (/ transpositions 2)) matches)) 3)))))))
(println (jaro "MARTHA" "MARHTA"))
(println (jaro "DIXON" "DICKSONX"))
(println (jaro "JELLYFISH" "SMELLYFISH"))
</syntaxhighlight>
{{out}}
<pre>
0.9444444
0.76666665
0.8962963
</pre>
=={{header|CLU}}==
{{trans|C}}
<syntaxhighlight lang="clu">max = proc [T: type] (a, b: T) returns (T)
where T has lt: proctype (T,T) returns (bool)
if a<b then return(b) else return(a) end
end max
min = proc [T: type] (a, b: T) returns (T)
where T has lt: proctype (T,T) returns (bool)
if a<b then return(a) else return(b) end
end min
jaro = proc (s1, s2: string) returns (real)
s1_len: int := string$size(s1)
s2_len: int := string$size(s2)
if s1_len = 0 & s2_len = 0 then return(1.0)
elseif s1_len = 0 | s2_len = 0 then return(0.0)
end
dist: int := max[int](s1_len, s2_len)/2 - 1
s1_match: array[bool] := array[bool]$fill(1,s1_len,false)
s2_match: array[bool] := array[bool]$fill(1,s2_len,false)
matches: real := 0.0
transpositions: real := 0.0
for i: int in int$from_to(1, s1_len) do
start: int := max[int](1, i-dist)
end_: int := min[int](i+dist, s2_len)
for k: int in int$from_to(start, end_) do
if s2_match[k] then continue end
if s1[i] ~= s2[k] then continue end
s1_match[i] := true
s2_match[k] := true
matches := matches + 1.0
break
end
end
if matches=0.0 then return(0.0) end
k: int := 1
for i: int in int$from_to(1, s1_len) do
if ~s1_match[i] then continue end
while ~s2_match[k] do k := k + 1 end
if s1[i] ~= s2[k] then
transpositions := transpositions + 1.0
end
k := k+1
end
transpositions := transpositions / 2.0
return( ((matches / real$i2r(s1_len)) +
(matches / real$i2r(s2_len)) +
((matches - transpositions) / matches)) / 3.0)
end jaro
start_up = proc ()
po: stream := stream$primary_output()
stream$putl(po, f_form(jaro("MARTHA", "MARHTA"), 1, 6))
stream$putl(po, f_form(jaro("DIXON", "DICKSONX"), 1, 6))
stream$putl(po, f_form(jaro("JELLYFISH", "SMELLYFISH"), 1, 6))
end start_up</syntaxhighlight>
{{out}}
<pre>0.944444
0.766667
0.896296</pre>
=={{header|COBOL}}==
{{trans|Java}}
<syntaxhighlight lang="cobol">
identification division.
program-id. JaroDistance.
environment division.
configuration section.
repository.
function length intrinsic
function trim intrinsic
function max intrinsic
function min intrinsic
.
data division.
working-storage section.
77 s pic x(255).
77 t pic x(255).
77 s-length pic 9(3).
77 t-length pic 9(3).
77 i pic 9(3).
77 j pic 9(3).
77 k pic 9(3).
77 start-pos pic 9(3).
77 end-pos pic 9(3).
77 match-distance pic 9(3).
77 matches pic 9(3).
77 transpositions pic 9(3).
77 distance pic 9v9(8).
01 jaro-table.
05 filler occurs 255.
10 filler pic 9(1).
88 s-matches value 1 when set to false is 0.
10 filler pic 9(1).
88 t-matches value 1 when set to false is 0.
procedure division.
main.
move "MARTHA" to s
move "MARHTA" to t
perform jaro-calc-and-show
move "DIXON" to s
move "DICKSONX" to t
perform jaro-calc-and-show
move "JELLYFISH" to s
move "SMELLYFISH" to t
perform jaro-calc-and-show
stop run
.
jaro-calc-and-show.
perform jaro-distance
display trim(s) " -> " trim(t) ", distance=" distance
.
jaro-distance.
move length(trim(s)) to s-length
move length(trim(t)) to t-length
if s-length = zeros and t-length = zeros
move 1 to distance
exit paragraph
end-if
compute match-distance = max(s-length, t-length) / 2 - 1
move low-values to jaro-table
move zeros to matches
move zeros to transpositions
perform varying i from 1 by 1 until i > s-length
move max(1, i - match-distance) to start-pos
move min(i + match-distance, t-length) to end-pos
perform varying j from start-pos by 1 until j > end-pos
if t-matches(j) or s(i:1) <> t(j:1)
exit perform cycle
end-if,
set s-matches(i), t-matches(j) to true
add 1 to matches
exit perform
end-perform
end-perform
if matches = zeros
move matches to distance
exit paragraph
end-if
move 1 to k
perform varying i from 1 by 1 until i > s-length
if not s-matches(i)
exit perform cycle
end-if
perform until t-matches(k)
add 1 to k
end-perform
if s(i:1) <> t(k:1)
add 1 to transpositions
end-if
add 1 to k
end-perform
compute distance = ((matches / s-length) + (matches / t-length) +
((matches - transpositions / 2) / matches)) / 3
.
</syntaxhighlight>
{{out}}
<pre>
MARTHA -> MARHTA, distance=0.94444444
DIXON -> DICKSONX, distance=0.76666666
JELLYFISH -> SMELLYFISH, distance=0.89629629
</pre>
=={{header|CoffeeScript}}==
{{trans|C++}}
<syntaxhighlight lang="coffeescript">jaro = (s1, s2) ->
l1 = s1.length
l2 = s2.length
if l1 == 0 then return if l2 == 0 then 1.0 else 0.0
match_distance = Math.max(l1, l2) / 2 - 1
s1_matches = []
s2_matches = []
m = 0
for i in [0...l1]
end = Math.min(i + match_distance + 1, l2)
for k in [Math.max(0, i - match_distance)...end]
if !s2_matches[k] and s1[i] == s2[k]
s1_matches[i] = true
s2_matches[k] = true
m++
break
if m == 0
0.0
else
t = 0.0
k = 0
for i in [0...l1]
if s1_matches[i]
until s2_matches[k] then k++
if s1[i] != s2[k++] then t += 0.5
(m / l1 + m / l2 + (m - t) / m) / 3.0
console.log jaro "MARTHA", "MARHTA"
console.log jaro "DIXON", "DICKSONX"
console.log jaro "JELLYFISH", "SMELLYFISH"</syntaxhighlight>
{{Out}}
<pre>0.9444444444444445
0.7666666666666666
0.8962962962962964</pre>
=={{header|Crystal}}==
{{trans|Ruby}}
<syntaxhighlight lang="ruby">def jaro(s, t)
return 1.0 if s == t
s_len = s.size
t_len = t.size
match_distance = ({s_len, t_len}.max // 2) - 1
s_matches = Array.new(s_len, false)
t_matches = Array.new(t_len, false)
matches = 0.0
s_len.times do |i|
j_start = {0, i - match_distance}.max
j_end = {i + match_distance, t_len - 1}.min
(j_start..j_end).each do |j|
t_matches[j] && next # -> next if t_matches[j]
s[i] == t[j] || next # -> next unless s[i] == t[j]
s_matches[i] = true
t_matches[j] = true
matches += 1.0
break
end
end
return 0.0 if matches == 0.0
k = 0
transpositions = 0.0
s_len.times do |i|
s_matches[i] || next # -> next unless s_matches[i]
while ! t_matches[k]; k += 1 end # -> k += 1 until t_matches[k]
s[i] == t[k] || (transpositions += 1.0) # -> (transpositions += 1.0) unless s[i] == t[k]
k += 1
end
((matches / s_len) + (matches / t_len) +
((matches - transpositions / 2.0) / matches)) / 3.0
end
%w( MARTHA MARHTA
DIXON DICKSONX
JELLYFISH SMELLYFISH
).each_slice(2) { |(s ,t)| puts "jaro(#{s}, #{t}) = #{"%.10f" % jaro(s, t)}" }
</syntaxhighlight>
{{out}}
<pre>
jaro(MARTHA, MARHTA) = 0.9444444444
jaro(DIXON, DICKSONX) = 0.7666666667
jaro(JELLYFISH, SMELLYFISH) = 0.8962962963
</pre>
=={{header|D}}==
{{trans|Kotlin}}
<syntaxhighlight lang="d">auto jaro(in string s1, in string s2) {
int s1_len = cast(int) s1.length;
int s2_len = cast(int) s2.length;
if (s1_len == 0 && s2_len == 0) return 1;
import std.algorithm.comparison: min, max;
auto match_distance = max(s1_len, s2_len) / 2 - 1;
auto s1_matches = new bool[s1_len];
auto s2_matches = new bool[s2_len];
int matches = 0;
for (auto i = 0; i < s1_len; i++) {
auto start = max(0, i - match_distance);
auto end = min(i + match_distance + 1, s2_len);
for (auto j = start; j < end; j++)
if (!s2_matches[j] && s1[i] == s2[j]) {
s1_matches[i] = true;
s2_matches[j] = true;
matches++;
break;
}
}
if (matches == 0) return 0;
auto t = 0.0;
auto k = 0;
for (auto i = 0; i < s1_len; i++)
if (s1_matches[i]) {
while (!s2_matches[k]) k++;
if (s1[i] != s2[k++]) t += 0.5;
}
double m = matches;
return (m / s1_len + m / s2_len + (m - t) / m) / 3.0;
}
void main() {
import std.stdio: writeln;
writeln(jaro( "MARTHA", "MARHTA"));
writeln(jaro( "DIXON", "DICKSONX"));
writeln(jaro("JELLYFISH", "SMELLYFISH"));
}</syntaxhighlight>
<pre>0.944444
0.766667
0.896296</pre>
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Jaro_distance#Pascal Pascal].
=={{header|Elixir}}==
{{trans|Ruby}}
{{works with|Elixir|1.3}}
<syntaxhighlight lang="elixir">defmodule Jaro do
def distance(s, t) when is_binary(s) and is_binary(t), do:
distance(to_charlist(s), to_charlist(t))
def distance(x, x), do: 1.0
def distance(s, t) do
s_len = length(s)
t_len = length(t)
{s_matches, t_matches, matches} = matching(s, t, s_len, t_len)
if matches == 0 do
0.0
else
{k, transpositions} = transposition(s, t, s_matches, t_matches)
((matches / s_len) +
(matches / t_len) +
((matches - transpositions/2) / matches)) / 3
end
end
defp matching(s, t, s_len, t_len) do
match_distance = div(max(s_len, t_len), 2) - 1
ac0 = {List.duplicate(false, s_len), List.duplicate(false, t_len), 0}
Enum.reduce(0..s_len-1, ac0, fn i,acc ->
j_start = max(0, i-match_distance)
j_end = min(i+match_distance, t_len-1)
Enum.reduce_while(j_start..j_end, acc, fn j,{sm,tm,m} ->
if Enum.at(tm, j) or Enum.at(s, i) != Enum.at(t, j) do
{:cont, {sm, tm, m}}
else
{:halt, { List.replace_at(sm, i, true),
List.replace_at(tm, j, true),
m + 1 }}
end
end)
end)
end
defp transposition(s, t, s_matches, t_matches) do
Enum.reduce(0..length(s)-1, {0,0}, fn i,{k,transpositions} ->
if Enum.at(s_matches, i) do
k = k + (Enum.drop(t_matches, k)
|> Enum.take_while(fn matche -> not matche end)
|> length)
if Enum.at(s, i) == Enum.at(t, k), do: {k+1, transpositions},
else: {k+1, transpositions+1}
else
{k, transpositions}
end
end)
end
end
~w( MARTHA MARHTA
DIXON DICKSONX
JELLYFISH SMELLYFISH )c
|> Enum.chunk(2)
|> Enum.each(fn [s,t] ->
:io.format "jaro(~s, ~s) = ~.10f~n", [inspect(s), inspect(t), Jaro.distance(s, t)]
end)</syntaxhighlight>
{{out}}
<pre>
jaro('MARTHA', 'MARHTA') = 0.9444444444
jaro('DIXON', 'DICKSONX') = 0.7666666667
jaro('JELLYFISH', 'SMELLYFISH') = 0.8962962963
</pre>
Elixir has a built-in function (<code>String.jaro_distance</code>).
=={{header|Emacs Lisp}}==
{{trans|Python}}
<syntaxhighlight lang="lisp">
(let ()
(defun jaro (s1 s2)
(let (mw mflags1 mflags2 fn-reset-mflags fn-reset-all-mflags fn-cnt-trans)
(setq mflags1 (make-vector (length s1) nil))
(setq mflags2 (make-vector (length s2) nil))
(setq mw (1- (/ (max (length s1) (length s2)) 2)))
(setq fn-reset-mflags
(lambda (idx)
(let ((start (max 0 (- idx mw)))
(end (min (1- (length s2)) (+ idx mw))))
(cl-loop for i from start to end do
(when (and (not (elt mflags1 idx))
(not (elt mflags2 i)))
(when (equal (elt s1 idx) (elt s2 i))
(aset mflags1 idx 't)
(aset mflags2 i 't) ) ) ) ) ) )
(setq fn-reset-all-mflags
(lambda ()
(dotimes (idx (length s1))
(funcall fn-reset-mflags idx) ) ) )
(setq fn-cnt-trans
(lambda ()
(let ((cur2 0) (transposition 0))
(dotimes (cur1 (length s1))
(when (aref mflags1 cur1)
(while (not (aref mflags2 cur2))
(setq cur2 (1+ cur2)) )
(when (not (equal (aref s1 cur1)
(aref s2 cur2)))
(setq transposition (1+ transposition)) )
(setq cur2 (1+ cur2))
)
)
transposition ) ) )
(funcall fn-reset-all-mflags)
(let ((m (seq-count (lambda (f) f) mflags1))
(tr (funcall fn-cnt-trans)))
;;(message "matches: %s, transposition: %s, |s1|: %d |s2|: %d" m tr (length s1) (length s2))
(if (= m 0)
0
(progn (/ (+ (/ (float m) (length s1)) (/ (float m) (length s2)) (/ (float (- m (/ (float tr) 2))) m) ) 3))
) ) ) )
(let ((params '(("MARTHA" "MARHTA")
("DIXON" "DICKSONX")
("JELLYFISH" "SMELLYFISH"))))
(dolist (p params)
(message "jaro(%s, %s) = %f"
(nth 0 p) (nth 1 p)
(jaro (nth 0 p) (nth 1 p)))
)
)
)
</syntaxhighlight>
{{out}}
<pre>
jaro(MARTHA, MARHTA) = 0.944444
jaro(DIXON, DICKSONX) = 0.766667
jaro(JELLYFISH, SMELLYFISH) = 0.896296
</pre>
=={{header|F_Sharp|F#}}==
<syntaxhighlight lang="fsharp">
// Calculate Jaro distance of 2 strings. Nigel Galloway: August 7th., 2020
let fG n g=Seq.map2(fun n g->if g=1 then Some n else None) n g |> Seq.choose id
let J (n:string) (g:string)=
let s1,s2=n.Length,g.Length
let w,m1,m2=(max s1 s2)/2-1,Array.zeroCreate<int>s1,Array.zeroCreate<int>s2
g|>Seq.iteri(fun i g->match [max(i-w) 0..min(i+w)(s1-1)]|>Seq.tryFind(fun i->n.[i]=g&&m1.[i]=0) with Some n->m1.[n]<-1;m2.[i]<-1 |_->())
let t=float(Seq.fold2(fun Σ n g->Σ + (if n<>g then 1 else 0)) 0 (fG n m1) (fG g m2))/2.0
let m=float(m2|>Array.sum) in if m=0.0 then m else ((m/float s1)+(m/float s2)+((m-t)/m))/3.0
printfn "MARTHA MARHTA->%f" (J "MARTHA" "MARHTA")
printfn "DIXON DICKSONX->%f" (J "DIXON" "DICKSONX")
printfn "JELLYFISH SMELLYFISH->%f" (J "JELLYFISH" "SMELLYFISH")
</syntaxhighlight>
{{out}}
<pre>
MARTHA MARHTA->0.944444
DIXON DICKSONX->0.766667
JELLYFISH SMELLYFISH->0.896296
</pre>
=={{header|Factor}}==
{{works with|Factor|0.99 development release 2019-03-17+}}
<syntaxhighlight lang="factor">USING: formatting fry generalizations kernel locals make math
math.order sequences sequences.extras ;
IN: rosetta-code.jaro-distance
: match? ( s1 s2 n -- ? )
[ pick nth swap indices nip ] [ 2nip ]
[ drop [ length ] bi@ max 2/ 1 - ] 3tri
'[ _ - abs _ <= ] any? ;
: matches ( s1 s2 -- seq )
over length <iota> [
[ [ nip swap nth ] [ match? ] 3bi [ , ] [ drop ] if ]
2with each
] "" make ;
: transpositions ( s1 s2 -- n )
2dup swap [ matches ] 2bi@ [ = not ] 2count 2/ ;
:: jaro ( s1 s2 -- x )
s1 s2 matches length :> m
s1 length :> |s1|
s2 length :> |s2|
s1 s2 transpositions :> t
m zero? [ 0 ] [ m |s1| / m |s2| / m t - m / + + 1/3 * ] if ;
: jaro-demo ( -- )
"DWAYNE" "DUANE"
"MARTHA" "MARHTA"
"DIXON" "DICKSONX"
"JELLYFISH" "SMELLYFISH" [
2dup jaro dup >float "%u %u jaro -> %u (~%.5f)\n" printf
] 2 4 mnapply ;
MAIN: jaro-demo</syntaxhighlight>
{{out}}
<pre>
"DWAYNE" "DUANE" jaro -> 37/45 (~0.82222)
"MARTHA" "MARHTA" jaro -> 17/18 (~0.94444)
"DIXON" "DICKSONX" jaro -> 23/30 (~0.76667)
"JELLYFISH" "SMELLYFISH" jaro -> 121/135 (~0.89630)
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">' version 09-10-2016
' compile with: fbc -s console
#Macro max(x, y)
IIf((x) > (y), (x), (y))
#EndMacro
#Macro min(x, y)
IIf((x) < (y), (x), (y))
#EndMacro
Function jaro(word1 As String, word2 As String) As Double
If Len(word1) > Len(word2) Then Swap word1, word2
Dim As Long i, j, j1, m, t
Dim As Long s1 = Len(word1)
Dim As Long s2 = Len(word2)
Dim As Long max_dist = s2 \ 2 -1 ' integer division
For i = 0 To s1 -1
If word1[i] = word2[j] Then
m = m +1
word2[j] = 32
Else
For j1 = max(0, i - max_dist) To min(s2 -1, i + max_dist)
If word1[i] = word2[j1] Then
t = t +1
m = m +1
word2[j1] = 32
If j1 > j Then j = j1
End If
Next
End If
j = j + 1
Next
If m = 0 Then Return 0
t = t \ 2
Return (m / s1 + m / s2 + ((m - t) / m)) / 3
End Function
' ------=< MAIN >=------
Print
Print " jaro (MARTHA, MARHTA) ="; jaro("MARTHA", "MARHTA")
Print " jaro (DIXON, DICKSONX) ="; jaro("DIXON", "DICKSONX")
Print " jaro (JELLYFISH, SMELLYFISH) ="; jaro("JELLYFISH", "SMELLYFISH")
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End</syntaxhighlight>
{{out}}
<pre> jaro (MARTHA, MARHTA) = 0.9444444444444444
jaro (DIXON, DICKSONX) = 0.7666666666666667
jaro (JELLYFISH, SMELLYFISH) = 0.8962962962962963</pre>
=={{header|Go}}==
<syntaxhighlight lang="go">package main
import "fmt"
func jaro(str1, str2 string) float64 {
if len(str1) == 0 && len(str2) == 0 {
return 1
}
if len(str1) == 0 || len(str2) == 0 {
return 0
}
match_distance := len(str1)
if len(str2) > match_distance {
match_distance = len(str2)
}
match_distance = match_distance/2 - 1
str1_matches := make([]bool, len(str1))
str2_matches := make([]bool, len(str2))
matches := 0.
transpositions := 0.
for i := range str1 {
start := i - match_distance
if start < 0 {
start = 0
}
end := i + match_distance + 1
if end > len(str2) {
end = len(str2)
}
for k := start; k < end; k++ {
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
}
k := 0
for i := range str1 {
if !str1_matches[i] {
continue
}
for !str2_matches[k] {
k++
}
if str1[i] != str2[k] {
transpositions++
}
k++
}
transpositions /= 2
return (matches/float64(len(str1)) +
matches/float64(len(str2)) +
(matches-transpositions)/matches) / 3
}
func main() {
fmt.Printf("%f\n", jaro("MARTHA", "MARHTA"))
fmt.Printf("%f\n", jaro("DIXON", "DICKSONX"))
fmt.Printf("%f\n", jaro("JELLYFISH", "SMELLYFISH"))
}</syntaxhighlight>
{{out}}
<pre>
0.944444
0.766667
0.896296
</pre>
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">import Data.List (elemIndex, intercalate, sortOn)
import Data.Maybe (mapMaybe)
import Text.Printf (printf)
---------------------- JARO DISTANCE ---------------------
jaro :: Ord a => [a] -> [a] -> Float
jaro x y
| 0 == m = 0
| otherwise =
(1 / 3)
* ( (m / s1) + (m / s2) + ((m - t) / m))
where
f = fromIntegral . length
[m, t] =
[f, fromIntegral . transpositions]
<*> [matches x y]
[s1, s2] = [f] <*> [x, y]
matches :: Eq a => [a] -> [a] -> [(Int, a)]
matches s1 s2 =
let [(l1, xs), (l2, ys)] =
sortOn
fst
((length >>= (,)) <$> [s1, s2])
r = quot l2 2 - 1
in mapMaybe
( \(c, n) ->
-- Initial chars out of range ?
let offset = max 0 (n - (r + 1))
in -- Any offset for this char within range.
elemIndex c (drop offset (take (n + r) ys))
>>= (\i -> Just (offset + i, c))
)
(zip xs [1 ..])
transpositions :: Ord a => [(Int, a)] -> Int
transpositions =
length
. filter (uncurry (>))
. (zip <*> tail)
--------------------------- TEST -------------------------
main :: IO ()
main =
mapM_ putStrLn $
fmap
( \(s1, s2) ->
intercalate
" -> "
[s1, s2, printf "%.3f\n" $ jaro s1 s2]
)
[ ("DWAYNE", "DUANE"),
("MARTHA", "MARHTA"),
("DIXON", "DICKSONX"),
("JELLYFISH", "SMELLYFISH")
]</syntaxhighlight>
{{Out}}
<pre>DWAYNE -> DUANE -> 0.822
MARTHA -> MARHTA -> 0.944
DIXON -> DICKSONX -> 0.767
JELLYFISH -> SMELLYFISH -> 0.896</pre>
=={{header|Haxe}}==
{{trans|Kotlin}}
{{works with|Neko|2.1.0}}
<syntaxhighlight lang="haxe">class Jaro {
private static function jaro(s1: String, s2: String): Float {
var s1_len = s1.length;
var s2_len = s2.length;
if (s1_len == 0 && s2_len == 0) return 1;
var match_distance = Std.int(Math.max(s1_len, s2_len)) / 2 - 1;
var matches = { s1: [for(n in 0...s1_len) false], s2: [for(n in 0...s2_len) false] };
var m = 0;
for (i in 0...s1_len) {
var start = Std.int(Math.max(0, i - match_distance));
var end = Std.int(Math.min(i + match_distance + 1, s2_len));
for (j in start...end)
if (!matches.s2[j] && s1.charAt(i) == s2.charAt(j)) {
matches.s1[i] = true;
matches.s2[j] = true;
m++;
break;
}
}
if (m == 0) return 0;
var k = 0;
var t = 0.;
for (i in 0...s1_len)
if (matches.s1[i]) {
while (!matches.s2[k]) k++;
if (s1.charAt(i) != s2.charAt(k++)) t += 0.5;
}
return (m / s1_len + m / s2_len + (m - t) / m) / 3.0;
}
public static function main() {
Sys.println(jaro( "MARTHA", "MARHTA"));
Sys.println(jaro( "DIXON", "DICKSONX"));
Sys.println(jaro("JELLYFISH", "SMELLYFISH"));
}
}</syntaxhighlight>
{{Out}}
<pre>0.944444444444445
0.766666666666667
0.896296296296296</pre>
=={{header|IS-BASIC}}==
<syntaxhighlight lang="is-basic">100 PROGRAM "Jaro.bas"
110 DO
120 READ IF MISSING EXIT DO:A$,B$
130 PRINT A$;", ";B$;":";JARO(A$,B$)
140 LOOP
150 DEF JARO(A$,B$)
160 LET J=1:LET M,T,JARO=0:LET S1=LEN(A$):LET S2=LEN(B$)
170 IF S1>S2 THEN
180 LET Z$=A$:LET A$=B$:LET B$=Z$
190 LET Z=S1:LET S1=S2:LET S2=Z
200 END IF
210 LET MAXDIST=INT(S2/2)
220 FOR I=1 TO S1
230 IF A$(I)=B$(J) THEN
240 LET M=M+1:CALL CHANGE(B$," ",J)
250 ELSE
260 FOR K=MAX(1,I-MAXDIST) TO MIN(S2,I+MAXDIST)
270 IF A$(I)=B$(K) THEN
280 LET T=T+1:LET M=M+1:CALL CHANGE(B$," ",K)
290 IF K>J THEN LET J=K
300 END IF
310 NEXT
320 END IF
330 IF J<S2 THEN LET J=J+1
340 NEXT
350 IF M<>0 THEN
360 LET T=INT(T/2)
370 LET JARO=(M/S1+M/S2+((M-T)/M))/3
380 END IF
390 END DEF
400 DEF CHANGE(REF S$,C$,POS)
410 LET S$=S$(:POS-1)&C$&S$(POS+1:)
420 END DEF
430 DATA MARTHA,MARHTA
440 DATA DIXON,DICKSONX
450 DATA JELLYFISH,SMELLYFISH
460 DATA DWAYNE,DUANE</syntaxhighlight>
=={{header|J}}==
Line 154 ⟶ 1,920:
Implementation:
<
d=. ((x >.&# y)%2)-1
e=. (x =/y) * d >: |x -/&(i.@#) y
Line 164 ⟶ 1,930:
s2=. #y
((m%s1)+(m%s2)+(m-t)%m)%3
)</
Task examples:
<
0.944444
'DIXON' jaro 'DICKSONX'
0.766667
'JELLYFISH' jaro 'SMELLYFISH'
0.896296</
=={{header|
<syntaxhighlight lang="java">public class JaroDistance {
public static double jaro(String s, String t) {
int s_len = s.length();
int t_len = t.length();
if (s_len == 0 && t_len == 0) return 1;
int match_distance = Integer.max(s_len, t_len) / 2 - 1;
boolean[] s_matches = new boolean[s_len];
boolean[] t_matches = new boolean[t_len];
int matches = 0;
int transpositions = 0;
for (int i = 0; i < s_len; i++) {
int start = Integer.max(0, i-match_distance);
int end = Integer.min(i+match_distance+1, t_len);
for (int j = start; j < end; j++) {
if (t_matches[j]) continue;
if (s.charAt(i) != t.charAt(j)) continue;
s_matches[i] = true;
t_matches[j] = true;
matches++;
break;
}
}
if (matches == 0) return 0;
int k = 0;
for (int i = 0; i < s_len; i++) {
if (!s_matches[i]) continue;
while (!t_matches[k]) k++;
if (s.charAt(i) != t.charAt(k)) transpositions++;
k++;
}
((double)matches / t_len) +
(((double)matches - transpositions/2.0) / matches)) / 3.0;
}
public static void main(String[] args) {
System.out.println(jaro( "MARTHA", "MARHTA"));
System.out.println(jaro( "DIXON", "DICKSONX"));
System.out.println(jaro("JELLYFISH", "SMELLYFISH"));
}
}</syntaxhighlight>
{{out}}
<pre>
0.9444444444444445
0.7666666666666666
0.8962962962962964
</pre>
=={{header|jq}}==
{{trans|Wren}}
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<syntaxhighlight lang="jq">def jaro($s1; $s2):
($s1|length) as $le1
| ($s2|length) as $le2
| if $le1 == 0 and $le2 == 0 then 1
elif $le1 == 0 or $le2 == 0 then 0
else ((((if $le2 > $le1 then $le2 else $le1 end) / 2) | floor) - 1) as $dist
| {matches: 0, matches2: [], matches2: [], transpos: 0 }
| reduce range(0; $le1) as $i (.;
(($i - $dist) | if . < 0 then 0 else . end) as $start
| (($i + $dist + 1) | if . > $le2 then $le2 else . end) as $stop
| .k = $start
| until(.k >= $stop;
if (.matches2[.k] or $s1[$i:$i+1] != $s2[.k:.k+1])|not
then .matches1[$i] = true
| .matches2[.k] = true
| .matches += 1
| .k = $stop
else .k += 1
end) )
| if .matches == 0 then 0
else .k = 0
| reduce range(0; $le1) as $i (.;
if .matches1[$i]
then until(.k >= $le2 or .matches2[.k]; .k += 1)
| if .k < $le2 and ($s1[$i:$i+1] != $s2[.k:.k+1]) then .transpos += 1 else . end
| .k += 1
else .
end )
| .transpos /= 2
| (.matches/$le1 + .matches/$le2 + ((.matches - .transpos)/.matches)) / 3
end
end ;
def task:
[["MARTHA","MARHTA"],
["DIXON", "DICKSONX"],
["JELLYFISH","SMELLYFISH"],
["ABC","DEF"]][]
| (jaro(.[0]; .[1]) * 1000 | floor / 1000) as $d
| "jaro(\(.[0]); \(.[1])) => \($d)";
task</syntaxhighlight>
{{out}}
<pre>
jaro(MARTHA; MARHTA) => 0.944
jaro(DIXON; DICKSONX) => 0.766
jaro(JELLYFISH; SMELLYFISH) => 0.896
jaro(ABC; DEF) => 0
</pre>
=={{header|Julia}}==
{{works with|Julia|1.5}}
<syntaxhighlight lang="julia">function jarodistance(s1, s2)
m = t = p = 0
matchstd = max(length(s1), length(s2)) / 2 - 1
for (i1, c1) in enumerate(s1)
for (i2, c2) in enumerate(s2)
(c1 == c2) && (abs(i2 - i1) ≤ matchstd) && (m += 1)
(c1 == c2) && (i2 == i1) && (p += 1)
end
end
t = (m - p) / 2
1 / 3 * (m / length(s1) + m / length(s2) + (m - t) / m)
end
@show jarodistance("MARTHA", "MARHTA")
@show jarodistance("DIXON", "DICKSONX")
@show jarodistance("JELLYFISH", "SMELLYFISH")
</syntaxhighlight>
{{out}}
<pre>
jarodistance("MARTHA", "MARHTA") = 0.9444444444444444
jarodistance("DIXON", "DICKSONX") = 0.6833333333333332
jarodistance("JELLYFISH", "SMELLYFISH") = 0.8870370370370371
</pre>
=={{header|Kotlin}}==
{{trans|Java}}
<syntaxhighlight lang="scala">object Jaro {
fun distance(s1: String, s2: String): Double {
val s1_len = s1.length
val s2_len = s2.length
if (s1_len == 0 && s2_len == 0) return 1.0
val match_distance = Math.max(s1_len, s2_len) / 2 - 1
val s1_matches = BooleanArray(s1_len)
val s2_matches = BooleanArray(s2_len)
var matches = 0
for (i in 0..s1_len - 1) {
val start = Math.max(0, i - match_distance)
val end = Math.min(i + match_distance + 1, s2_len)
(start..end - 1).find { j -> !s2_matches[j] && s1[i] == s2[j] } ?. let {
s1_matches[i] = true
s2_matches[it] = true
matches++
}
}
if (matches == 0) return 0.0
var t = 0.0
var k = 0
(0..s1_len - 1).filter { s1_matches[it] }.forEach { i ->
while (!s2_matches[k]) k++
if (s1[i] != s2[k]) t += 0.5
k++
}
val m = matches.toDouble()
return (m / s1_len + m / s2_len + (m - t) / m) / 3.0
}
}
fun main(args: Array<String>) {
println(Jaro.distance("MARTHA", "MARHTA"))
println(Jaro.distance("DIXON", "DICKSONX"))
println(Jaro.distance("JELLYFISH", "SMELLYFISH"))
}</syntaxhighlight>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[JaroDistance]
JaroDistance[s_String, t_String] := Module[{slen, tlen, maxdistance, smatches, tmatches, matches, transpositions, start, end, k, schar, tchar},
slen = StringLength[s];
tlen = StringLength[t];
schar = Characters[s];
tchar = Characters[t];
If[slen == tlen == 0,
1
,
maxdistance = Floor[Max[slen, tlen]/2] - 1;
smatches = ConstantArray[False, slen];
tmatches = ConstantArray[False, tlen];
matches = transpositions = 0;
Do[
start = Max[0, i - maxdistance];
end = Min[i + maxdistance + 1, tlen];
start = Max[1, i - maxdistance];
end = Min[i + maxdistance + 1, tlen];
Do[
If[! tmatches[[j]],
If[schar[[i]] == tchar[[j]],
smatches[[i]] = True;
tmatches[[j]] = True;
matches++;
Break[];
]
]
,
{j, start, end}
]
,
{i, slen}
];
If[matches == 0,
0
,
k = 1;
Do[
If[smatches[[i]],
While[! tmatches[[k]],
k++;
];
If[schar[[i]] != tchar[[k]],
transpositions++;
];
k++;
]
,
{i, slen}
];
N@(matches/slen + matches/tlen + (matches - transpositions/2)/matches)/3
]
]
]
JaroDistance["DWAYNE", "DUANE"]
JaroDistance["MARTHA", "MARHTA"]
JaroDistance["DIXON", "DICKSONX"]
JaroDistance["JELLYFISH", "SMELLYFISH"]</syntaxhighlight>
{{out}}
<pre>0.822222
0.944444
0.766667
0.896296</pre>
=={{header|Nim}}==
{{trans|Kotlin}}
<syntaxhighlight lang="nim">import lenientops
func jaro(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
echo jaro("MARTHA", "MARHTA")
echo jaro("DIXON", "DICKSONX")
echo jaro("JELLYFISH", "SMELLYFISH")</syntaxhighlight>
{{out}}
<pre>0.9444444444444445
0.7666666666666666
0.8962962962962964</pre>
=={{header|Objeck}}==
{{trans|Java}}
<syntaxhighlight lang="objeck">class JaroDistance {
function : Main(args : String[]) ~ Nil {
Jaro("MARTHA", "MARHTA")->PrintLine();
Jaro("DIXON", "DICKSONX")->PrintLine();
Jaro("JELLYFISH", "SMELLYFISH")->PrintLine();
}
function : Jaro(s : String, t : String) ~ Float {
s_len := s->Size();
t_len := t->Size();
if (s_len = 0 & t_len = 0) { return 1; };
match_distance := Int->Max(s_len, t_len) / 2 - 1;
s_matches := Bool->New[s_len];
t_matches := Bool->New[t_len];
matches := 0;
transpositions := 0;
for (i := 0; i < s_len; i++;) {
start := Int->Max(0, i-match_distance);
end := Int->Min(i+match_distance+1, t_len);
for (j := start; j < end; j++;) {
if (t_matches[j]) { continue; };
if (s->Get( i) <> t->Get( j)) { continue; };
s_matches[i] := true;
t_matches[j] := true;
matches++;
break;
};
};
if (matches = 0) { return 0; };
k := 0;
for (i := 0; i < s_len; i++;) {
if (<>s_matches[i]) { continue; };
while (<>t_matches[k]) { k++; };
if (s->Get( i) <> t->Get( k)) { transpositions++; };
k++;
};
return ((matches->As(Float) / s_len) +
(matches->As(Float) / t_len) +
((matches->As(Float) - transpositions/2.0) / matches)) / 3.0;
}
}</syntaxhighlight>
{{output}}
<pre>
0.944444
0.766667
0.896296
</pre>
=={{header|PARI/GP}}==
This version was translated from Java and Perl.
{{Works with|PARI/GP|2.7.4 and above}}
<syntaxhighlight lang="parigp">
\\Jaro distance between 2 strings s1 and s2.
\\ 4/12/16 aev
jaroDist(s1,s2)={
my(vt1=Vecsmall(s1),vt2=Vecsmall(s2),n1=#s1,n2=#s2,d,
md=max(n1,n2)\2-1,cs,ce,mc=0,tr=0,k=1,ds,
s1m=vector(n1,z,0),s2m=vector(n2,z,0));
if(!n1||!n2, return(0));
for(i=1,n1,
cs=max(1,i-md);
ce=min(i+md+1,n2);
for(j=cs,ce,
if(s2m[j],next);
if(vt1[i]!=vt2[j], next);
mc++; s1m[i]=1; s2m[j]=1; break;
);\\fend j
);\\fend i
if(!mc, return(0));
for(i=1,n1,
if(!s1m[i], next);
while(!s2m[k], k++);
if(vt1[i]!=vt2[k], tr++);
k++
);\\fend i
d=(mc/n1+mc/n2+(mc-tr/2)/mc)/3.0;
ds=Strprintf("%.5f",d);
print(" *** Jaro distance is: ",ds," for strings: ",s1,", ",s2);
return(d);
}
{ \\ Testing:
jaroDist("MARTHA","MARHTA");
jaroDist("DIXON","DICKSONX");
jaroDist("JELLYFISH","SMELLYFISH");
jaroDist("DWAYNE","DUANE");
}
</syntaxhighlight>
{{Output}}
<pre>
*** Jaro distance is: 0.94444 for strings: MARTHA, MARHTA
*** Jaro distance is: 0.76667 for strings: DIXON, DICKSONX
*** Jaro distance is: 0.89630 for strings: JELLYFISH, SMELLYFISH
*** Jaro distance is: 0.82222 for strings: DWAYNE, DUANE
</pre>
=={{header|Pascal}}==
<syntaxhighlight lang="pascal">
program Jaro_distance;
uses SysUtils, Math;
//converted from C source by /u/bleuge
function ssJaroWinkler(s1, s2: string): double;
var
l1, l2, match_distance, matches, i, k, trans: integer;
bs1, bs2: array[1..255] of boolean; //used to avoid getmem, max string length is 255
begin
l1 := length(s1);
l2 := length(s2);
fillchar(bs1, sizeof(bs1), 0); //set booleans to false
fillchar(bs2, sizeof(bs2), 0);
if l1 = 0 then
if l2 = 0 then
exit(1)
else
exit(0);
match_distance := (max(l1, l2) div 2) - 1;
matches := 0;
trans := 0;
for i := 1 to l1 do
begin
for k := max(1, i - match_distance) to min(i + match_distance, l2) do
begin
if bs2[k] then
continue;
if s1[i] <> s2[k] then
continue;
bs1[i] := true;
bs2[k] := true;
inc(matches);
break;
end;
end;
if matches = 0 then
exit(0);
k := 1;
for i := 1 to l1 do
begin
if (bs1[i] = false) then
continue;
while (bs2[k] = false) do
inc(k);
if s1[i] <> s2[k] then
inc(trans);
inc(k);
end;
trans := trans div 2;
result := ((matches / l1) + (matches / l2) + ((matches - trans) / matches)) / 3;
end;
begin
//test
writeln(formatfloat('0.######', ssJaroWinkler('DWAYNE', 'DUANE')));
writeln(formatfloat('0.######', ssJaroWinkler('MARTHA', 'MARHTA')));
writeln(formatfloat('0.######', ssJaroWinkler('DIXON', 'DICKSONX')));
writeln(formatfloat('0.######', ssJaroWinkler('JELLYFISH', 'SMELLYFISH')));
{$IFNDEF LINUX}readln;{$ENDIF}
end.</syntaxhighlight>
{{out}}
<pre>
0,822222
0,944444
0,766667
0,896296
</pre>
=={{header|Perl}}==
<syntaxhighlight lang="perl">use strict;
use warnings;
use List::Util qw(min max);
sub jaro {
my($s, $t) = @_;
my(@s_matches, @t_matches, $matches);
return 1 if $s eq $t;
my($s_len, @s) = (length $s, split //, $s);
my($t_len, @t) = (length $t, split //, $t);
my $match_distance = int (max($s_len, $t_len) / 2) - 1;
for my $i (0 .. $#s) {
my $start = max(0, $i - $match_distance);
my $end = min($i + $match_distance + 1, $t_len);
for my $j ($start .. $end - 1) {
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 my $i (0 .. $#s) {
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;
}
printf "%.3f\n", jaro(@$_[0], @$_[1]) for
['MARTHA', 'MARHTA'], ['DIXON', 'DICKSONX'], ['JELLYFISH', 'SMELLYFISH'],
['I repeat myself', 'I repeat myself'], ['', ''];</syntaxhighlight>
{{out}}
<pre>0.944
0.767
0.896
1.000
1.000</pre>
=={{header|Phix}}==
<!--<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;">constant</span> <span style="color: #000000;">testcouples</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #008000;">"CRATE"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"TRACE"</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"JONES"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"JOHNSON"</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"ABCVWXYZ"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"CABVWXYZ"</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"DWAYNE"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"DUANE"</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"MARTHA"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"MARHTA"</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"DIXON"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"DICKSONX"</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"JELLYFISH"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"SMELLYFISH"</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: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">testcouples</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">string</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">s1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">testcouples</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</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;">"%f <== jaro(\"%s\", \"%s\")\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">jaro</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s2</span><span style="color: #0000FF;">),</span><span style="color: #000000;">s1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s2</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
0.733333 <== jaro("CRATE", "TRACE")
0.790476 <== jaro("JONES", "JOHNSON")
0.958333 <== jaro("ABCVWXYZ", "CABVWXYZ")
0.822222 <== jaro("DWAYNE", "DUANE")
0.944444 <== jaro("MARTHA", "MARHTA")
0.766667 <== jaro("DIXON", "DICKSONX")
0.896296 <== jaro("JELLYFISH", "SMELLYFISH")
</pre>
=={{header|Python}}==
===Procedural===
{{Works with|Python|3}}
<syntaxhighlight lang="python">'''Jaro distance'''
from __future__ import division
def jaro(s, t):
'''Jaro distance between two strings.'''
s_len = len(s)
t_len = len(t)
Line 257 ⟶ 2,561:
for i in range(s_len):
start = max(0, i - match_distance)
end = min(i + match_distance + 1, t_len)
for j in range(start, end):
Line 285 ⟶ 2,589:
return ((matches / s_len) +
(matches / t_len) +
((matches - transpositions / 2) / matches)) / 3
def main():
'''Tests'''
for s, t in [('MARTHA', 'MARHTA'),
('DIXON', 'DICKSONX'),
('JELLYFISH', 'SMELLYFISH')]:
print("jaro(%r, %r) = %.10f" % (s, t, jaro(s, t)))
if __name__ == '__main__':
main()</syntaxhighlight>
{{out}}
<pre>jaro('MARTHA', 'MARHTA') = 0.9444444444
jaro('DIXON', 'DICKSONX') = 0.7666666667
jaro('JELLYFISH', 'SMELLYFISH') = 0.8962962963</pre>
===Composition of pure functions===
{{Trans|Haskell}}
{{Works with|Python|3}}
<syntaxhighlight lang="python">'''Jaro distance between two strings'''
from functools import reduce
import itertools
# --------------------- JARO FUNCTION ----------------------
# jaro :: String -> String -> Float
def jaro(x):
'''The Jaro distance between two strings.'''
def go(s1, s2):
m, t = ap(compose(Tuple, len))(
transpositionSum
)(matches(s1, s2))
return 0 if 0 == m else (
(1 / 3) * ((m / len(s1)) + (
m / len(s2)
) + ((m - t) / m))
)
return lambda y: go(x, y)
# -------------------------- TEST --------------------------
# main :: IO ()
def main():
'''Sample word pairs'''
print(
fTable('Jaro distances:\n')(str)(
showPrecision(3)
)(
uncurry(jaro)
)([
("DWAYNE", "DUANE"),
("MARTHA", "MARHTA"),
("DIXON", "DICKSONX"),
("JELLYFISH", "SMELLYFISH")
])
)
# ----------------- JARO HELPER FUNCTIONS ------------------
# transpositionSum :: [(Int, Char)] -> Int
def transpositionSum(xs):
'''A count of the transpositions in xs.'''
def f(a, xy):
x, y = xy
return 1 + a if fst(x) > fst(y) else a
return reduce(f, zip(xs, xs[1:]), 0)
# matches :: String -> String -> [(Int, Char)]
def matches(s1, s2):
'''A list of (Index, Char) correspondences
between the two strings s1 and s2.'''
[(_, xs), (l2, ys)] = sorted(map(
ap(compose(Tuple, len))(list), [s1, s2]
))
r = l2 // 2 - 1
# match :: (Int, (Char, Int)) -> (Int, Char)
def match(a, nc):
n, c = nc
offset = max(0, n - (1 + r))
def indexChar(x):
return a + [(offset + x, c)]
return maybe(a)(indexChar)(
elemIndex(c)(
drop(offset)(take(n + r)(ys))
)
)
return reduce(match, enumerate(xs), [])
# ------------------- GENERIC FUNCTIONS --------------------
# Just :: a -> Maybe a
def Just(x):
'''Constructor for an inhabited Maybe (option type) value.
Wrapper containing the result of a computation.
'''
return {'type': 'Maybe', 'Nothing': False, 'Just': x}
# Nothing :: Maybe a
def Nothing():
'''Constructor for an empty Maybe (option type) value.
Empty wrapper returned where a computation is not possible.
'''
return {'type': 'Maybe', 'Nothing': True}
# Tuple (,) :: a -> b -> (a, b)
def Tuple(x):
'''Constructor for a pair of values,
possibly of two different types.
'''
def go(y):
return (
x + (y,)
) if isinstance(x, tuple) else (x, y)
return go
# ap :: (a -> b -> c) -> (a -> b) -> a -> c
def ap(f):
'''Applicative instance for functions.
'''
def go(g):
def fxgx(x):
return f(x)(
g(x)
)
return fxgx
return go
# compose :: ((a -> a), ...) -> (a -> a)
def compose(*fs):
'''Composition, from right to left,
of a series of functions.
'''
def go(f, g):
def fg(x):
return f(g(x))
return fg
return reduce(go, fs, lambda x: x)
# drop :: Int -> [a] -> [a]
# drop :: Int -> String -> String
def drop(n):
'''The sublist of xs beginning at
(zero-based) index n.
'''
def go(xs):
if isinstance(xs, (list, tuple, str)):
return xs[n:]
else:
take(n)(xs)
return xs
return go
# elemIndex :: Eq a => a -> [a] -> Maybe Int
def elemIndex(x):
'''Just the index of the first element in xs
which is equal to x,
or Nothing if there is no such element.
'''
def go(xs):
try:
return Just(xs.index(x))
except ValueError:
return Nothing()
return go
# fst :: (a, b) -> a
def fst(tpl):
'''First member of a pair.'''
return tpl[0]
# maybe :: b -> (a -> b) -> Maybe a -> b
def maybe(v):
'''Either the default value v, if m is Nothing,
or the application of f to x,
where m is Just(x).
'''
return lambda f: lambda m: v if (
None is m or m.get('Nothing')
) else f(m.get('Just'))
# showPrecision Int -> Float -> String
def showPrecision(n):
'''A string showing a floating point number
at a given degree of precision.'''
return lambda x: str(round(x, n))
# fTable :: String -> (a -> String) ->
# (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
'''Heading -> x display function -> fx display function ->
f -> xs -> tabular string.
'''
def gox(xShow):
def gofx(fxShow):
def gof(f):
def goxs(xs):
ys = [xShow(x) for x in xs]
w = max(map(len, ys))
def arrowed(x, y):
return y.rjust(w, ' ') + (
' -> ' + fxShow(f(x))
)
return s + '\n' + '\n'.join(
map(arrowed, xs, ys)
)
return goxs
return gof
return gofx
return gox
# take :: Int -> [a] -> [a]
# take :: Int -> String -> String
def take(n):
'''The prefix of xs of length n,
or xs itself if n > length xs.
'''
islice = itertools.islice
def go(xs):
return (
xs[0:n]
if isinstance(xs, (list, tuple))
else list(islice(xs, n))
)
return go
# uncurry :: (a -> b -> c) -> ((a, b) -> c)
def uncurry(f):
'''A function over a tuple derived from a curried function.'''
return lambda xy: f(xy[0])(
xy[1]
)
# MAIN ---
if __name__ == '__main__':
main()</syntaxhighlight>
{{Out}}
<pre>Jaro distances:
('DWAYNE', 'DUANE') -> 0.822
('MARTHA', 'MARHTA') -> 0.944
('DIXON', 'DICKSONX') -> 0.767
('JELLYFISH', 'SMELLYFISH') -> 0.896</pre>
=={{header|Racket}}==
{{trans|C}}
(kinda)
Returns an exact value for the Jaro distance.
<syntaxhighlight lang="racket">#lang racket/base
;; {{trans|C}}
(require data/bit-vector)
(define (jaro-distance str1 str2)
(define str1-len (string-length str1))
(define str2-len (string-length str2))
(cond
[(and (zero? str1-len) (zero? str2-len)) 0]
[(or (zero? str1-len) (zero? str2-len)) 1]
[else
;; vectors of bools that signify if that char in the matching string has a match
(define str1-matches (make-bit-vector str1-len))
(define str2-matches (make-bit-vector str2-len))
(define matches
;; max distance between two chars to be considered matching
(let ((match-distance (sub1 (quotient (max str1-len str2-len) 2))))
(for/fold ((matches 0))
((i (in-range 0 str1-len))
(c1 (in-string str1)))
(define start (max 0 (- i match-distance)))
(define end (min (+ i match-distance 1) str2-len))
(for/fold ((matches matches))
((k (in-range start end))
(c2 (in-string str2 start))
#:unless (bit-vector-ref str2-matches k) ; if str2 already has a match continue
#:when (char=? c1 c2) ; if str1 and str2 are not
#:final #t)
;; otherwise assume there is a match
(bit-vector-set! str1-matches i #t)
(bit-vector-set! str2-matches k #t)
(add1 matches)))))
(cond
[(zero? matches) 0]
[else
(define-values (transpositions*2 k+)
(for/fold ((transpositions 0) (k 0))
((i (in-range 0 str1-len))
(c1 (in-string str1))
(b1 (in-bit-vector str1-matches))
;; if there are no matches in str1 continue
#:when b1)
(define k+ (for/first ((k+ (in-range k str2-len))
(b2 (in-bit-vector str2-matches k))
#:when b2)
k+))
(values
(+ transpositions (if (char=? c1 (string-ref str2 k+)) 0 1)) ; increment transpositions
(add1 k+)))) ;; while there is no match in str2 increment k
;; divide the number of transpositions by two as per the algorithm specs
;; this division is valid because the counted transpositions include both
;; instances of the transposed characters.
(define transpositions (quotient transpositions*2 2))
;; return the Jaro distance
(/ (+ (/ matches str1-len)
(/ matches str2-len)
(/ (- matches transpositions) matches))
3)])]))
(module+ test
(jaro-distance "MARTHA" "MARHTA"); 0.944444
(exact->inexact (jaro-distance "MARTHA" "MARHTA")); 0.944444
(jaro-distance "DIXON" "DICKSONX"); 0.766667
(exact->inexact (jaro-distance "DIXON" "DICKSONX")); 0.766667
(jaro-distance "JELLYFISH" "SMELLYFISH"); 0.896296
(exact->inexact (jaro-distance "JELLYFISH" "SMELLYFISH"))); 0.896296</syntaxhighlight>
{{out}}
The <code>exact->inexact</code> calls in the tests give an inexact, floating point version of the rational values.
<pre>17/18
0.9444444444444444
23/30
0.7666666666666667
121/135
0.8962962962962963</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{trans|Perl}}
<syntaxhighlight lang="raku" line>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', '' => '';
</syntaxhighlight>
{{out}}
<pre>0.944
0.767
0.896
1.000
1.000</pre>
=={{header|REXX}}==
<syntaxhighlight lang="rexx">/*REXX program computes the Jaro distance between two strings (or a list of strings).*/
@.= /*define a default for the @. array. */
parse arg @.1 /*obtain an optional character string. */
if @.1='' then do; @.1= 'MARTHA MARHTA' /*Nothing specified? Use the defaults.*/
@.2= 'DIXON DICKSONX'
@.3= 'JELLYFISH SMELLYFISH'
@.4= 'DWAYNE DUANE'
end /* [↑] embedded blanks are shown as is.*/
do j=1 while @.j\=='' /*process all the strings in the list. */
d= jaroD(@.j)
say 'Jaro distance is ' format(d, , 8) " for strings: " @.j
end /*j*/ /* └──── digits past the decimal point.*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
jaroD: procedure; arg s.1 s.2 .; L1= length(s.1); L2= length(s.2); m= 0
if L1==0 | L2==0 then return 0 /*check if any string is a null string.*/
f= max(L1, L2) % 2 - 1 /*calculate furthest distanced allowed.*/
r.= 0 /* [↓] see if the char is near enough.*/
do k=1 for L1; p= pos( substr(s.1, k, 1), s.2, max(1, k-f) )
r.k= p
if p\==0 & abs(p-k)<=f then m= m+1 /*if near enough, count it as a match. */
else r.k= 0 /* ··· otherwise, don't count it.*/
end /*k*/
t= 0
do o=1 for L1; om= o - 1; if r.o==0 | r.om==0 then iterate
if pos( substr(s.1, o, 1), s.2)==0 then iterate
if r.o<r.om then t= t + 1
end /*o*/ /* [↑] count number of transpositions.*/
if m==0 then return 0
return (m/L1 + m/L2 + (m-t)/m) / 3</syntaxhighlight>
{{out|output|text= when using the default inputs:}}
<pre>
Jaro distance is 0.94444444 for strings: MARTHA MARHTA
Jaro distance is 0.76666667 for strings: DIXON DICKSONX
Jaro distance is 0.89629630 for strings: JELLYFISH SMELLYFISH
Jaro distance is 0.82222222 for strings: DWAYNE DUANE
</pre>
=={{header|
<syntaxhighlight lang="ring">
# Project : Jaro distance
decimals(12)
see " jaro (MARTHA, MARHTA) = " + jaro("MARTHA", "MARHTA") + nl
see " jaro (DIXON, DICKSONX) = " + jaro("DIXON", "DICKSONX") + nl
see " jaro (JELLYFISH, SMELLYFISH) = " + jaro("JELLYFISH", "SMELLYFISH") + nl
func jaro(word1, word2)
if len(word1) > len(word2)
swap(word1, word2)
ok
j = 1
t = 0
m = 0
s1 = len(word1)
s2 = len(word2)
maxdist = (s2 / 2) -1
for i = 1 to s1
if word1[i] = word2[j] and j < max(len(word2), len(word2)) + 1
m = m +1
word2[j] = char(32)
else
for j1 = max(1, i - maxdist) to min(s2 -1, i + maxdist)
if word1[i] = word2[j1]
t = t +1
m = m +1
word2[j1] = char(32)
if j1 > j and j1 < max(len(word2), len(word2)) + 1
j = j1
ok
ok
next
ok
if j < max(len(word2), len(word2))
j = j + 1
ok
next
if m = 0
return 0
ok
t = floor(t / 2)
return (m / s1 + m / s2 + ((m - t) / m)) / 3
func swap(a, b)
temp = a
a = b
b = temp
return [a, b]
</syntaxhighlight>
Output:
<pre>
jaro (MARTHA, MARHTA) = 0.944444444444
jaro (DIXON, DICKSONX) = 0.766666666667
jaro (JELLYFISH, SMELLYFISH) = 0.896296296296
</pre>
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">def jaro(s, t)
return 1.0 if s == t
s_len = s.size
t_len = t.size
match_distance = ([s_len, t_len].max / 2) - 1
s_matches = []
t_matches = []
matches = 0.0
s_len.times do |i|
j_start = [0, i-match_distance].max
j_end = [i+match_distance, t_len-1].min
(j_start..j_end).each do |j|
t_matches[j] && next
Line 326 ⟶ 3,116:
end
end
return 0.0 if
k = 0
transpositions = 0.0
s_len.times do |i|
s_matches[i] || next
s[i] == t[k] || (transpositions += 1.0)
k += 1
end
((matches / s_len) +
end
DIXON
JELLYFISH
).each_slice(2) do |s,t|
puts "jaro(#{s.inspect}, #{t.inspect}) = #{'%.10f' % jaro(s, t)}"
end</
{{out}}
<pre>
Line 357 ⟶ 3,146:
jaro("JELLYFISH", "SMELLYFISH") = 0.8962962963
</pre>
=={{header|Rust}}==
{{trans|C++}}
<syntaxhighlight lang="rust">use std::cmp;
pub fn jaro(s1: &str, s2: &str) -> f64 {
let s1_len = s1.len();
let s2_len = s2.len();
if s1_len == 0 && s2_len == 0 { return 1.0; }
let match_distance = cmp::max(s1_len, s2_len) / 2 - 1;
let mut s1_matches = vec![false; s1_len];
let mut s2_matches = vec![false; s2_len];
let mut m: isize = 0;
for i in 0..s1_len {
let start = cmp::max(0, i as isize - match_distance as isize) as usize;
let end = cmp::min(i + match_distance + 1, s2_len);
for j in start..end {
if !s2_matches[j] && s1.as_bytes()[i] == s2.as_bytes()[j] {
s1_matches[i] = true;
s2_matches[j] = true;
m += 1;
break;
}
}
}
if m == 0 { return 0.0; }
let mut t = 0.0;
let mut k = 0;
for i in 0..s1_len {
if s1_matches[i] {
while !s2_matches[k] { k += 1; }
if s1.as_bytes()[i] != s2.as_bytes()[k] { t += 0.5; }
k += 1;
}
}
let m = m as f64;
(m / s1_len as f64 + m / s2_len as f64 + (m - t) / m) / 3.0
}
fn main() {
let pairs = [("MARTHA", "MARHTA"), ("DIXON", "DICKSONX"), ("JELLYFISH", "SMELLYFISH")];
for p in pairs.iter() { println!("{}/{} = {}", p.0, p.1, jaro(p.0, p.1)); }
}</syntaxhighlight>
{{Out}}
<pre>MARTHA/MARHTA = 0.9444444444444445
DIXON/DICKSONX = 0.7666666666666666
JELLYFISH/SMELLYFISH = 0.8962962962962964</pre>
=={{header|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="scala">object Jaro extends App {
def distance(s1: String, s2: String): Double = {
val s1_len = s1.length
val s2_len = s2.length
if (s1_len == 0 && s2_len == 0) return 1.0
val match_distance = Math.max(s1_len, s2_len) / 2 - 1
val s1_matches = Array.ofDim[Boolean](s1_len)
val s2_matches = Array.ofDim[Boolean](s2_len)
var matches = 0
for (i <- 0 until s1_len) {
val start = Math.max(0, i - match_distance)
val end = Math.min(i + match_distance + 1, s2_len)
start until end find { j => !s2_matches(j) && s1(i) == s2(j) } match {
case Some(j) =>
s1_matches(i) = true
s2_matches(j) = true
matches += 1
case None =>
}
}
if (matches == 0) return 0.0
var t = 0.0
var k = 0
0 until s1_len filter s1_matches foreach { i =>
while (!s2_matches(k)) k += 1
if (s1(i) != s2(k)) t += 0.5
k += 1
}
val m = matches.toDouble
(m / s1_len + m / s2_len + (m - t) / m) / 3.0
}
val strings = List(("MARTHA", "MARHTA"), ("DIXON", "DICKSONX"), ("JELLYFISH", "SMELLYFISH"))
strings.foreach { s => println(distance(s._1, s._2)) }
}</syntaxhighlight>
=={{header|Sidef}}==
<
return 1 if (s
var s_len = s.len
var t_len = t.len
var match_distance = (
var s_matches = []
Line 374 ⟶ 3,251:
var transpositions = 0
for i (^s_len
var start =
var end =
for k (start
t_matches[k] && next
s[i] == t[k] || next
Line 391 ⟶ 3,268:
var k = 0
for i (^s_len
s_matches[i] || next
while (!t_matches[k]) { ++k }
Line 409 ⟶ 3,286:
] {
say "jaro(#{pair.map{.join.dump}.join(', ')}) = #{'%.10f' % jaro(pair...)}"
}</
{{out}}
<pre>
Line 415 ⟶ 3,292:
jaro("DIXON", "DICKSONX") = 0.7666666667
jaro("JELLYFISH", "SMELLYFISH") = 0.8962962963
</pre>
=={{header|Stata}}==
Here we use the [https://ideas.repec.org/c/boc/bocode/s457850a.html jarowinkler] package from SSC. To install the package, type
<syntaxhighlight lang="stata">ssc install jarowinkler</syntaxhighlight>
Now the program for the task:
<syntaxhighlight lang="stata">clear
input str20 a str20 b
DWAYNE DUANE
MARTHA MARHTA
DIXON DICKSONX
JELLYFISH SMELLYFISH
end
jarowinkler a b, gen(jw) jaroonly(jaro)
format %8.3f jaro
format %-20s a b
list a b jaro</syntaxhighlight>
'''Output'''
<pre> +--------------------------------+
| a b jaro |
|--------------------------------|
1. | DWAYNE DUANE 0.822 |
2. | MARTHA MARHTA 0.944 |
3. | DIXON DICKSONX 0.767 |
4. | JELLYFISH SMELLYFISH 0.896 |
+--------------------------------+</pre>
=={{header|Swift}}==
<syntaxhighlight lang="swift"> 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"))
</syntaxhighlight>
{{out}}
<pre>
DWAYNE/DUANE: 0.822222222222222
MARTHA/MARHTA: 0.944444444444445
DIXON/DICKSONX: 0.766666666666667
JELLYFISH/SMELLYFISH: 0.896296296296296
</pre>
=={{header|Tcl}}==
<syntaxhighlight lang="tcl">proc jaro {s1 s2} {
set l1 [string length $s1]
set l2 [string length $s2]
set dmax [expr {max($l1, $l2)/2 - 1}] ;# window size to scan for matches
set m1 {} ;# match indices
set m2 {}
for {set i 0} {$i < $l1} {incr i} {
set jmin [expr {$i - $dmax}] ;# don't worry about going out-of-bounds
set jmax [expr {$i + $dmax}] ;# because [string index] will return {} safely
for {set j $jmin} {$j <= $jmax} {incr j} {
if {$j in $m2} continue ;# don't double-count matches
if {[string index $s1 $i] eq [string index $s2 $j]} {
lappend m1 $i
lappend m2 $j
break
}
}
}
set T 0 ;# number of transpositions
set oj -1
foreach j $m2 {
if {$j < $oj} {incr T}
set oj $j
}
set T [expr {$T / 2.0}]
set M [expr {1.0 * [llength $m1]}] ;# number of matches
expr { ( ($M / $l1) + ($M / $l2) + (($M - $T) / $M) ) / 3.0 }
}
foreach {s t} {
DWAYNE DUANE
MARTHA MARHTA
DIXON DICKSONX
JELLYFISH SMELLYFISH
} {
puts "[jaro $s $t]:\t$s / $t"
}</syntaxhighlight>
{{out}}
<pre>0.8222222222222223: DWAYNE / DUANE
0.9722222222222222: MARTHA / MARHTA
0.7666666666666666: DIXON / DICKSONX
0.8962962962962964: JELLYFISH / SMELLYFISH</pre>
=={{header|Turbo-Basic XL}}==
<syntaxhighlight lang="turbobasic">
10 DIM Word_1$(20), Word_2$(20), Z$(20)
11 CLS
20 Word_1$="MARTHA" : Word_2$="MARHTA" : ? Word_1$;" - ";Word_2$ : EXEC _JWD_ : ?
30 Word_1$="DIXON" : Word_2$="DICKSONX" : ? Word_1$;" - ";Word_2$ : EXEC _JWD_ : ?
40 Word_1$="JELLYFISH" : Word_2$="SMELLYFISH" : ? Word_1$;" - ";Word_2$ : EXEC _JWD_ : ?
11000 END
12000 REM JaroWinklerDistance INPUT(Word_1$, Word_2$) USE(Z$, I, J, K, L, M, N, S1, S2, Min, Max) RETURN(FLOAT Result)
12000 PROC _JWD_
12010 Result=0 : S1=LEN(Word_1$) : S2=LEN(Word_2$)
12020 IF S1>S2 THEN Z$=Word_1$ : Word_1$=Word_2$ : Word_2$=Z$ : M=S1 : S1=S2 : S2=M
12030 J=1: M=0 : N=0 : L=INT(S2/2) : Z$=Word_2$
12040 FOR I=1 TO S1
12050 IF Word_1$(I,I)=Word_2$(J,J) THEN M=M+1: Word_2$(J,J)=" ": GO# JMP_JWD
12060 Max=1 : IF Max<(I-L) THEN Max=I-L
12070 Min=S2 : IF Min>(I+L-1) THEN Min=I+L-1
12080 FOR K=Max TO Min
12090 IF Word_1$(I,I)=Word_2$(K,K) THEN N=N+1: M=M+1: Word_2$(K,K)=" ": IF K>J THEN J=K
12100 NEXT K
12110 #JMP_JWD : IF J<S2 THEN J=J+1
12120 NEXT I
12130 IF M=0
12140 Result=0 : REM jaro distance
12150 ELSE
12160 N=INT(N/2)
12170 Result=(M/S1+M/S2+((M-N)/M))/3. : REM jaro distance
12180 ENDIF
12190 ? "Jaro Distance=";Result
12200 Min=S1 : IF Min>S2 THEN Min=S2
12210 M=Min : IF M>3 THEN M=3
12220 M=M+1 : L=0 : Word_2$=Z$ : IF M>Min THEN M=Min
12230 FOR I=1 TO M
12240 IF Word_1$(I,I)=Word_2$(I,I)
12250 L=L+1
12260 ELSE
12270 EXIT
12280 ENDIF
12290 NEXT I
12300 Result=Result + (L*0.1*(1.0 - Result)) : REM Winkler
12310 ? "Jaro Winkler Distance=";Result
12320 ENDPROC
</syntaxhighlight>
{{out}}
<pre>MARTHA, MARHTA: 0.9444444433
DIXON, DICKSONX: 0.7666666666
JELLYFISH, SMELLYFISH: 0.8962962933</pre>
=={{header|VBA}}==
<syntaxhighlight lang="vb">
Option Explicit
Function JaroWinkler(text1 As String, text2 As String, Optional p As Double = 0.1) As Double
Dim dummyChar, match1, match2 As String
Dim i, f, t, j, m, l, s1, s2, limit As Integer
i = 1
Do
dummyChar = Chr(i)
i = i + 1
Loop Until InStr(1, text1 & text2, dummyChar, vbTextCompare) = 0
s1 = Len(text1)
s2 = Len(text2)
limit = WorksheetFunction.Max(0, Int(WorksheetFunction.Max(s1, s2) / 2) - 1)
match1 = String(s1, dummyChar)
match2 = String(s2, dummyChar)
For l = 1 To WorksheetFunction.Min(4, s1, s2)
If Mid(text1, l, 1) <> Mid(text2, l, 1) Then Exit For
Next l
l = l - 1
For i = 1 To s1
f = WorksheetFunction.Min(WorksheetFunction.Max(i - limit, 1), s2)
t = WorksheetFunction.Min(WorksheetFunction.Max(i + limit, 1), s2)
j = InStr(1, Mid(text2, f, t - f + 1), Mid(text1, i, 1), vbTextCompare)
If j > 0 Then
m = m + 1
text2 = Mid(text2, 1, f + j - 2) & dummyChar & Mid(text2, f + j)
match1 = Mid(match1, 1, i - 1) & Mid(text1, i, 1) & Mid(match1, i + 1)
match2 = Mid(match2, 1, f + j - 2) & Mid(text1, i, 1) & Mid(match2, f + j)
End If
Next i
match1 = Replace(match1, dummyChar, "", 1, -1, vbTextCompare)
match2 = Replace(match2, dummyChar, "", 1, -1, vbTextCompare)
t = 0
For i = 1 To m
If Mid(match1, i, 1) <> Mid(match2, i, 1) Then t = t + 1
Next i
JaroWinkler = (m / s1 + m / s2 + (m - t / 2) / m) / 3
JaroWinkler = JaroWinkler + (1 - JaroWinkler) * l * WorksheetFunction.Min(0.25, p)
End Function
</syntaxhighlight>
=={{header|V (Vlang)}}==
{{trans|Python}}
<syntaxhighlight lang="v (vlang)">import math
fn jaro(str1 string, str2 string) f64 {
s1_len := str1.len
s2_len := str2.len
if s1_len == 0 && s2_len == 0 {
return 1
}
if s1_len == 0 || s2_len == 0 {
return 0
}
match_distance := math.max<int>(s1_len,s2_len)/2 - 1
mut str1_matches := []bool{len: s1_len}
mut str2_matches := []bool{len: s2_len}
mut matches := 0
mut transpositions := 0.0
for i in 0..s1_len {
start := math.max<int>(0,i - match_distance)
end := math.min<int>(i + match_distance, s2_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..s1_len {
if !str1_matches[i] {
continue
}
for !str2_matches[k] {
k++
}
if str1[i] != str2[k] {
transpositions++
}
k++
}
transpositions /= 2
return (matches/f64(s1_len) +
matches/f64(s2_len) +
(matches-transpositions)/matches) / 3
}
fn main() {
println(jaro("MARTHA", "MARHTA"))
println(jaro("DIXON", "DICKSONX"))
println(jaro("JELLYFISH", "SMELLYFISH"))
}</syntaxhighlight>
{{out}}
<pre>0.9444444444444445
0.7666666666666666
0.8962962962962964
</pre>
=={{header|Wren}}==
{{trans|Go}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./fmt" for Fmt
var jaro = Fn.new { |s1, s2|
var le1 = s1.count
var le2 = s2.count
if (le1 == 0 && le2 == 0) return 1
if (le1 == 0 || le2 == 0) return 0
var dist = (le2 > le1) ? le2 : le1
dist = (dist/2).floor - 1
var matches1 = List.filled(le1, false)
var matches2 = List.filled(le2, false)
var matches = 0
var transpos = 0
for (i in 0...s1.count) {
var start = i - dist
if (start < 0) start = 0
var end = i + dist + 1
if (end > le2) end = le2
var k = start
while (k < end) {
if (!(matches2[k] || s1[i] != s2[k])) {
matches1[i] = true
matches2[k] = true
matches = matches + 1
break
}
k = k + 1
}
}
if (matches == 0) return 0
var k = 0
for (i in 0...s1.count) {
if (matches1[i]) {
while(!matches2[k]) k = k + 1
if (s1[i] != s2[k]) transpos = transpos + 1
k = k + 1
}
}
transpos = transpos / 2
return (matches/le1 + matches/le2 + (matches - transpos)/matches) / 3
}
System.print(Fmt.f(0, jaro.call("MARTHA", "MARHTA")))
System.print(Fmt.f(0, jaro.call("DIXON", "DICKSONX")))
System.print(Fmt.f(0, jaro.call("JELLYFISH", "SMELLYFISH")))</syntaxhighlight>
{{out}}
<pre>
0.944444
0.766667
0.896296
</pre>
=={{header|zkl}}==
<
fcn _jaro(str1,str2, matchDistance){
cs:=Sink(String);
Line 438 ⟶ 3,715:
( matches/s1Len + matches/s2Len +
((matches - transpositions)/matches) ) / 3.0
}</
<
T("MARTHA","MARHTA"), T("DIXON","DICKSONX"), T("JELLYFISH","SMELLYFISH"))){
println(0'|jaro("%s","%s") = %.10f|.fmt(s,t,jaro(s,t)));
}</
{{out}}
<pre>
Line 449 ⟶ 3,726:
jaro("JELLYFISH","SMELLYFISH") = 0.8962962963
</pre>
=={{header|ZX Spectrum Basic}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="zxbasic">10 LET a$="MARTHA": LET b$="MARHTA": PRINT a$;", ";b$;": ";: GO SUB 1000: PRINT jaro
20 LET a$="DIXON": LET b$="DICKSONX": PRINT a$;", ";b$;": ";: GO SUB 1000: PRINT jaro
30 LET a$="JELLYFISH": LET b$="SMELLYFISH": PRINT a$;", ";b$;": ";: GO SUB 1000: PRINT jaro
900 STOP
1000 REM Jaro subroutine
1010 LET s1=LEN a$: LET s2=LEN b$: LET j=1: LET m=0: LET t=0
1030 IF s1>s2 THEN LET z$=a$: LET a$=b$: LET b$=z$: LET z=s1: LET s1=s2: LET s2=z
1035 LET maxdist=INT (s2/2)
1040 FOR i=1 TO s1
1050 IF a$(i)=b$(j) THEN LET m=m+1: LET b$(j)=" ": GO TO 2000
1080 FOR k=FN x(1,i-maxdist) TO FN n(s2,i+maxdist)
1090 IF a$(i)=b$(k) THEN LET t=t+1: LET m=m+1: LET b$(k)=" ": IF k>j THEN LET j=k
1100 NEXT k
2000 IF j<s2 THEN LET j=j+1:
2010 NEXT i
2020 IF m=0 THEN LET jaro=0: RETURN
2030 LET t=INT (t/2)
2040 LET jaro=(m/s1+m/s2+((m-t)/m))/3
2050 RETURN
5000 REM Functions
5010 DEF FN x(a,b)=(a AND a>b)+(b AND a<b)+(a AND a=b): REM max function
5020 DEF FN n(a,b)=(a AND a<b)+(b AND a>b)+(a AND a=b): REM min function</syntaxhighlight>
{{out}}
<pre>MARTHA, MARHTA: 0.94444444
DIXON, DICKSONX: 0.76666667
JELLYFISH, SMELLYFISH: 0.8962963</pre>
| |||