Distance de Jaro-Winkler

La distance de Jaro entre les chaînes ${\displaystyle s_{1}}$ et ${\displaystyle s_{2}}$ est définie par :

${\displaystyle d_{j}={\frac {1}{3}}\left({\frac {m}{|s_{1}|}}+{\frac {m}{|s_{2}|}}+{\frac {m-t}{m}}\right)}$

où:

• ${\displaystyle |s_{i}|}$ est la longueur de la chaîne de caractères ${\displaystyle s_{i}}$ ;
• ${\displaystyle m}$ est le nombre de caractères correspondants (voir ci-dessous);
• ${\displaystyle t}$ est le nombre de transpositions (voir ci-dessous).

Deux caractères identiques de ${\displaystyle s_{1}}$ et de ${\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 :

${\displaystyle \left\lfloor {\frac {\max(|s_{1}|,|s_{2}|)}{2}}\right\rfloor -1}$.

Le nombre de transpositions est obtenu en comparant le i-ème caractère correspondant de ${\displaystyle s_{1}}$ avec le i-ème caractère correspondant de ${\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 ${\displaystyle p}$ qui favorise les chaînes commençant par un préfixe de longueur ${\displaystyle \ell }$ (avec ${\displaystyle \ell \leq 4}$). En considérant deux chaînes ${\displaystyle s_{1}}$ et ${\displaystyle s_{2}}$, leur distance de Jaro-Winkler ${\displaystyle d_{w}}$ est :

${\displaystyle d_{w}=d_{j}+(\ell p(1-d_{j}))}$

où :

• ${\displaystyle d_{j}}$ est la distance de Jaro entre ${\displaystyle s_{1}}$ et ${\displaystyle s_{2}}$
• ${\displaystyle \ell }$ est la longueur du préfixe commun (maximum 4 caractères)
• ${\displaystyle p}$ est un coefficient qui permet de favoriser les chaînes avec un préfixe commun. Winkler propose pour valeur ${\displaystyle p=0.1}$

Soit deux chaînes ${\displaystyle s_{1}}$ MARTHA et ${\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 :

• ${\displaystyle m=6}$ (nombre de 1 dans la table)
• ${\displaystyle |s_{1}|=6}$
• ${\displaystyle |s_{2}|=6}$
• Les caractères correspondants sont {M,A,R,T,H,A} pour ${\displaystyle s_{1}}$ et {M,A,R,H,T,A} pour ${\displaystyle s_{2}}$. 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ù ${\displaystyle t={\frac {2}{2}}=1}$

La distance de Jaro est :

${\displaystyle d_{j}={\frac {1}{3}}\left({\frac {6}{6}}+{\frac {6}{6}}+{\frac {6-1}{6}}\right)=0{,}944}$

La distance de Jaro-Winkler avec ${\displaystyle p=0{,}1}$ avec un préfixe de longueur ${\displaystyle \ell =3}$ devient

${\displaystyle d_{w}=0{,}944+(3\times 0{,}1(1-0{,}944))=0{,}961}$

Avec les chaînes ${\displaystyle s_{1}}$ DWAYNE et ${\displaystyle s_{2}}$ DUANE on trouve :

• ${\displaystyle m=4}$
• ${\displaystyle |s_{1}|=6}$
• ${\displaystyle |s_{2}|=5}$
• ${\displaystyle t=0}$

La distance de Jaro est :

${\displaystyle d_{j}={\frac {1}{3}}\left({\frac {4}{6}}+{\frac {4}{5}}+{\frac {4-0}{4}}\right)=0{,}822}$

Celle de Jaro-Winkler avec ${\displaystyle \ell =1}$ :

${\displaystyle d_{w}=0{,}822+(1\times 0{,}1(1-0{,}822))=0{,}84}$

Avec les chaînes ${\displaystyle s_{1}}$ DIXON et ${\displaystyle s_{2}}$ DICKSONX, on obtient :

On calcule l'éloignement maximum pour le critère de correspondance

${\displaystyle \left\lfloor {\frac {\max(|s_{1}|,|s_{2}|)}{2}}\right\rfloor -1=\lfloor {\frac {8}{2}}\rfloor -1=3}$.

• ${\displaystyle m=4}$ (les deux X ne correspondent pas, car ils sont éloignés de plus de 3 caractères)
• ${\displaystyle |s_{1}|=5}$
• ${\displaystyle |s_{2}|=8}$
• ${\displaystyle t=0}$

La distance de Jaro :

${\displaystyle d_{j}={\frac {1}{3}}\left({\frac {4}{5}}+{\frac {4}{8}}+{\frac {4-0}{4}}\right)=0.767}$

La distance de Jaro-Winkler avec ${\displaystyle \ell =2}$ :

${\displaystyle d_{w}=0{,}767+(2\times 0{,}1(1-0{,}767))=0{,}813}$

• (en) Jaro, M. A., « Advances in record linking methodology as applied to the 1985 census of Tampa Florida », Journal of the American Statistical Society, vol. 84, n^o 406,‎ 1989, p. 414-420
• (en) Jaro, M. A., « Probabilistic linkage of large public health data file », Statistics in Medicine, vol. 14,‎ 1995, p. 491-498 (lire en ligne)
• (en) Winkler, W. E., « The state of record linkage and current research problems », Statistics of Income Division, Internal Revenue Service Publication R99/04,‎ 1999 (lire en ligne)
• (en) Winkler, W. E., « Overview of Record Linkage and Current Research Directions », Research Report Series, RRS,‎ 2006 (lire en ligne)

• (en) Implémentation Opensource en Java et .NET
• (en) Implémentation originale en C
• Implémentation en Delphi
• Implémentation simple en C

• Portail de l'informatique théorique