Distance de Jaro-Winkler

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.

Distance de Jaro

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

${\displaystyle d_{j}=\left\{{\begin{array}{l l}0&{\text{si }}m=0\\{\frac {1}{3}}\left({\frac {m}{|s_{1}|}}+{\frac {m}{|s_{2}|}}+{\frac {m-t}{m}}\right)&{\text{sinon}}\end{array}}\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.

Distance de Jaro-Winkler

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}$

Exemples

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 :

	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

• ${\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 :

	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

${\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}$

Cas particuliers

Avec les chaînes ${\displaystyle s_{1}}$ 75000 et ${\displaystyle s_{2}}$ 75020 on doit trouver :

${\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 ${\displaystyle m=4}$ au lieu de ${\displaystyle m=5}$.

Notes et références

• (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)

Liens externes

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

v · m Algorithmique du texte
Recherche de sous-chaîne	Algorithme de Knuth-Morris-Pratt Algorithme de Boyer-Moore Algorithme de Boyer-Moore-Horspool Algorithme de Raita Algorithme de Baeza-Yates-Gonnet Algorithme Z Algorithme de Rabin-Karp Algorithme d'Aho-Corasick
Alignement de chaînes	Algorithme de Needleman-Wunsch Algorithme de Smith-Waterman Transformée de Burrows-Wheeler
Mesure de similarité	Distance de Jaro-Winkler Distance de Levenshtein Distance de Hamming
Arbre des suffixes	Algorithmes de Weiner et de McCreight Algorithme d'Ukkonen Tableau des suffixes Tableau de Lyndon
Comparaisons	Plus longue sous-séquence commune Plus longue sous-chaîne commune Plus courte super-séquence commune

• Portail de l'informatique théorique