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.
Le résultat est normalisé de façon à avoir une mesure entre 0 et 1, donc 0 représente l'absence de similarité et 1, l'égalité des chaines comparées.
Cette mesure est particulièrement adaptée au traitement de chaînes courtes comme des noms ou des mots de passe.
La distance de Jaro entre les chaînes s 1 {\displaystyle s_{1}} et s 2 {\displaystyle s_{2}} est définie par :
où:
Deux caractères identiques de s 1 {\displaystyle s_{1}} et de s 2 {\displaystyle s_{2}} 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 :
Le nombre de transpositions est obtenu en comparant le i-ème caractère correspondant de s 1 {\displaystyle s_{1}} avec le i-ème caractère correspondant de s 2 {\displaystyle s_{2}} . Le nombre de fois où ces caractères sont différents, divisé par deux, donne le nombre de transpositions.
La méthode introduite par Winkler utilise un coefficient de préfixe p {\displaystyle p} qui favorise les chaînes commençant par un préfixe de longueur ℓ {\displaystyle \ell } (avec ℓ ≤ 4 {\displaystyle \ell \leq 4} ). En considérant deux chaînes s 1 {\displaystyle s_{1}} et s 2 {\displaystyle s_{2}} , leur distance de Jaro-Winkler d w {\displaystyle d_{w}} est :
où :
Soit deux chaînes s 1 {\displaystyle s_{1}} MARTHA et s 2 {\displaystyle s_{2}} MARHTA. Nous allons dresser leur table de correspondance. Ici, l'éloignement maximal vaut 6 / 2 - 1 = 2. Dans les cases jaunes de la table ci-dessous, on inscrira donc 1 lorsque les caractères sont identiques (il y a correspondance) et 0 sinon :
La distance de Jaro est :
La distance de Jaro-Winkler avec p = 0 , 1 {\displaystyle p=0{,}1} avec un préfixe de longueur ℓ = 3 {\displaystyle \ell =3} devient
Avec les chaînes s 1 {\displaystyle s_{1}} DWAYNE et s 2 {\displaystyle s_{2}} DUANE on trouve :
Celle de Jaro-Winkler avec ℓ = 1 {\displaystyle \ell =1} :
Avec les chaînes s 1 {\displaystyle s_{1}} DIXON et s 2 {\displaystyle s_{2}} DICKSONX, on obtient :
On calcule l'éloignement maximum pour le critère de correspondance
La distance de Jaro :
La distance de Jaro-Winkler avec ℓ = 2 {\displaystyle \ell =2}
Avec les chaînes s 1 {\displaystyle s_{1}} 75000 et s 2 {\displaystyle s_{2}} 75020 on doit trouver :
d w = 0.907 {\displaystyle d_{w}=0.907}
Les correspondances entre les deux chaînes de caractères ne sont pas les mêmes ("75000" pour la première et "7500" pour la seconde). Par conséquent, il faut prendre m = 4 {\displaystyle m=4} au lieu de m = 5 {\displaystyle m=5} .