Différence entre Jaro-Winkler et Levenshtein distance?

J’ai un cas d’utilisation où je dois faire une correspondance floue entre des millions d’enregistrements provenant de plusieurs fichiers. J’ai identifié deux algorithmes pour cela: Jaro-Winkler et Levenshtein modifient la distance.

Lorsque j’ai commencé à explorer les deux, je n’ai pas pu comprendre la différence exacte entre les deux. Il semble que Levenshtein donne le nombre de modifications entre deux chaînes, et Jaro-Winkler donne un score correspondant entre 0,0 et 1,0. Je n’ai pas compris l’algorithme. Comme je dois utiliser l’un ou l’autre algorithme, j’ai besoin de connaître les différences exactes en ce qui concerne les performances de l’algorithme.

Levenshtein compte le nombre de modifications (insertions, suppressions ou substitutions) nécessaires pour convertir une chaîne en une autre. Damerau-Levenshtein est une version modifiée qui considère également les transpositions comme des éditions individuelles. Bien que la sortie soit le nombre entier de modifications, cela peut être normalisé pour donner une valeur de similarité par la formule

1 - (edit distance / length of the larger of the two ssortingngs) 

L’algorithme Jaro est une mesure des caractères communs, ne dépassant pas la moitié de la longueur de la chaîne la plus longue, compte tenu des transpositions. Winkler a modifié cet algorithme pour soutenir l’idée que les différences au début de la chaîne sont plus importantes que les différences à la fin de la chaîne. Jaro et Jaro-Winkler conviennent pour comparer des chaînes plus petites comme des mots et des noms.

Décider lequel utiliser n’est pas seulement une question de performance. Il est important de choisir une méthode adaptée à la nature des chaînes que vous comparez. En général, les deux algorithmes que vous avez mentionnés peuvent être coûteux, car chaque chaîne doit être comparée à toutes les autres chaînes, et avec des millions de chaînes dans votre dataset, le nombre de comparaisons est énorme. C’est beaucoup plus coûteux que de calculer un codage phonétique pour chaque chaîne, puis de regrouper simplement des chaînes partageant des codages identiques.

Il existe une mine d’informations détaillées sur ces algorithmes et d’autres algorithmes de correspondance de chaînes floues sur Internet. Celui-ci vous donnera un début:

Une comparaison de l’appariement des noms personnels: techniques et questions pratiques

Selon cet article, la vitesse des quatre algorithmes Jaro et Levenshtein que j’ai mentionnés va du plus rapide au plus lent:

  • Jaro
  • Jaro-Winkler
  • Levenshtein
  • Damerau-Levenshtein

avec le plus lent prenant 2 à 3 fois plus longtemps que le plus rapide. Bien sûr, ces temps dépendent des longueurs des chaînes et des implémentations, et il existe des moyens d’optimiser ces algorithmes qui n’ont peut-être pas été utilisés.