Distance de Jaro-Winkler

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

La distance de Jaro entre chaînes s_1 et s_2 est définie par :

d_j = \frac{1}{3}\left(\frac{m}{|s_1|} + \frac{m}{|s_2|} + \frac{m-t}{m}\right)

où:

  • |s_i| est la longueur de la chaîne de caractères s_i ;
  • 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 s_1 et de 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 :

\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 s_1 avec le i-ème caractère correspondant de 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[modifier | modifier le code]

La méthode introduite par Winkler utilise un coefficient de préfixe p qui favorise les chaînes commençant par un préfixe de longueur \ell (avec \ell \le 4). En considérant deux chaînes s_1 et s_2, leur distance de Jaro-Winkler d_w est :

d_w = d_j + (\ell p (1 - d_j))

où :

  • d_j est la distance de Jaro entre s_1 et s_2
  • \ell 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[modifier | modifier le code]

Soit deux chaînes s_1 MARTHA et 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
  • m = 6 (nombre de 1 dans la table)
  • |s_1| = 6
  • |s_2| = 6
  • Les caractères correspondants sont {M,A,R,T,H,A} pour s_1 et {M,A,R,H,T,A} pour 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ù t = \frac{2}{2} = 1

La distance de Jaro est :

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 p = 0.1 avec un préfixe de longueur \ell=3 devient

d_w = 0.944 + (3 * 0.1 (1 - 0.944)) = 0.961~

Avec les chaînes s_1 DWAYNE et s_2 DUANE on trouve :

  • m = 4
  • |s_1| = 6
  • |s_2| = 5
  • t = 0

La distance de Jaro est :

d_j = \frac{1}{3}\left(\frac{4}{6} + \frac{4}{5} + \frac{4-0}{4}\right) = 0.822

Celle de Jaro-Winkler avec \ell = 1 :

d_w = 0.822 + (1 * 0.1 (1 - 0.822)) = 0.84~

Avec les chaînes s_1 DIXON et 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

\left\lfloor\frac{\max(|s_1|,|s_2|)}{2}\right\rfloor-1 = \lfloor\frac{8}{2}\rfloor-1=3.
  • m = 4 (les deux X ne correspondent pas, car ils sont éloignés de plus de 3 caractères)
  • |s_1| = 5
  • |s_2| = 8
  • t = 0

La distance de Jaro :

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 \ell = 2 :

d_w = 0.767 + (2 * 0.1 (1 - 0.767)) = 0.813~

Notes et références[modifier | modifier le code]

  • (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, no 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[modifier | modifier le code]