La distance de Jaro-Winkler mesure la similarité entre deux chaînes de caractères. Il s'agit d'une variante proposée en 1999 par William E. Winkler, découlant de la distance de Jaro (1989, Matthew A. Jaro) qui est principalement utilisée dans la détection de doublons.
Plus la distance de Jaro-Winkler entre deux chaînes est élevée, plus elles sont similaires. Cette mesure est particulièrement adaptée au traitement de chaînes courtes comme des noms ou des mots de passe. Le résultat est normalisé de façon à avoir une mesure entre 0 et 1, le zéro représentant l'absence de similarité.
Distance de Jaro
La distance de Jaro entre chaînes s1 et s2 est définie par :
dj=31(∣s1∣m+∣s2∣m+mm−t)
où:
m est le nombre de caractères correspondants (voir ci-dessous);
t est le nombre de transpositions (voir ci-dessous).
Deux caractères identiques de s1 et de s2 sont considérés comme correspondants si leur éloignement (i.e. la différence entre leurs positions dans leurs chaînes respectives) ne dépasse pas :
⌊2max(∣s1∣,∣s2∣)⌋−1.
Le nombre de transpositions est obtenu en comparant le i-ème caractère correspondant de s1 avec le i-ème caractère correspondant de s2. Le nombre de fois où ces caractères sont différents, divisé par deux, donne le nombre de transpositions.
Distance de Jaro-Winkler
La méthode introduite par Winkler utilise un coefficient de préfixep qui favorise les chaînes commençant par un préfixe de longueurℓ (avec ℓ≤4). En considérant deux chaînes s1 et s2, leur distance de Jaro-Winkler dw est :
dw=dj+(ℓp(1−dj))
où :
dj est la distance de Jaro entre s1 et s2
ℓ est la longueur du préfixe commun (maximum 4 caractères)
p est un coefficient qui permet de favoriser les chaînes avec un préfixe commun. Winkler propose pour valeur p = 0.1
Exemples
Soit deux chaînes s1MARTHA et s2MARHTA. La table de correspondance est :
M
A
R
T
H
A
M
1
0
0
0
0
0
A
0
1
0
0
0
0
R
0
0
1
0
0
0
H
0
0
0
0
1
0
T
0
0
0
1
0
0
A
0
0
0
0
0
1
m = 6 (nombre de 1 dans la table)
| s1 | = 6
| s2 | = 6
Les caractères correspondants sont {M,A,R,T,H,A} pour s1 et {M,A,R,H,T,A} pour s2. En considérant ces ensembles ordonnés, on a donc 2 couples (T/H et H/T) de caractères correspondants différents, soit deux demi-transpositions. D'où t=22=1
La distance de Jaro est :
dj=31(66+66+66−1)=0.944
La distance de Jaro-Winkler avec p = 0.1 avec un préfixe de longueurℓ=3 devient
dw=0.944+(3∗0.1(1−0.944))=0.961
Avec les chaînes s1DWAYNE et s2DUANE on trouve :
m = 4
| s1 | = 6
| s2 | = 5
t = 0
La distance de Jaro est :
dj=31(64+54+44−0)=0.822
Celle de Jaro-Winkler avec ℓ=1 :
dw=0.822+(1∗0.1(1−0.822))=0.84
Avec les chaînes s1DIXON et s2DICKSONX, on obtient :
D
I
X
O
N
D
1
0
0
0
0
I
0
1
0
0
0
C
0
0
0
0
0
K
0
0
0
0
0
S
0
0
0
0
0
O
0
0
0
1
0
N
0
0
0
0
1
X
0
0
0
0
0
On calcule l'éloignement maximum pour le critère de correspondance
⌊2max(∣s1∣,∣s2∣)⌋−1=⌊28⌋−1=3.
m = 4 (les deux X ne correspondent pas, car ils sont éloignés de plus de 3 caractères)