Lorsque vous faîtes une recherche sur un moteur de recherche, il vous est sans doute déjà arrivé de faire une faute de frappe, ou d’inverser deux lettres. Malgré cette faute, vous avez quand même des résultats pertinents qui sortent. Comment est-ce possible ? Nous allons voir deux algorithmes qui permettent de laisser à vos utilisateurs le droit à l’erreur lorsqu’ils font une recherche. Ou de pouvoir comparer deux chaînes de caractères et voir leur proximité.
En SQL, lorsque vous faites des requêtes en base en utilisant une chaîne de caractères comme critères de recherche, vous aurez plusieurs possibilités de recherche :
- avec la chaîne exacte (= ‘laChaine’)
- commençant par la chaîne (LIKE ‘laChaine%’)
- finissant par la chaîne (LIKE ‘%laChaine’)
- contenant la chaîne (LIKE ‘%laChaine%)
En revanche, si vous faites une faute de frappe ou une inversion de caractères (ex ‘laChaien’), vous ne trouverez aucun enregistrement qui correspond. Alors que dans les faits votre recherche est assez proche. Il existe des algorithmes permettant de faire des comparaisons de chaîne, et vous donner un niveau de similarité entre deux chaînes.
Vous pouvez également utiliser ces méthodes si vous faîtes des reprises de données, ou si vous cherchez à intégrer des données qui ont été saisies à la main.
Jaro Winkler
Avec la distance de Jaro Winkler, vous allez pouvoir « mesurer » la similarité de deux chaînes de caractères. Le résultat obtenu sera entre 0 et 1, 1 étant une égalité parfaite entre les deux chaînes.
Si vous voulez voir exactement comment elle fonctionne sous le capot, vous pouvez aller voir la fiche Wikipedia.
Si vous souhaitez l’utiliser dans vos développements, vous pourrez trouver les codes sources sur le net. Par exemple le code source en C, ou si vous utilisez les fonctions et procédures MySQL le code source en fonction MySQL.
Attention quand même, ces fonctions de comparaisons de caractères sont assez consommatrices en ressources, et peuvent prendre du temps à s’exécuter. Notamment si vous souhaitez comparer une entrée utilisateur à des milliers ou millions d’entrées en base d’une chaîne de caractères.
Voici ce que donne quelques exécutions de la fonction en MySQL avec différentes chaînes :
Levenshtein
La distance de Levenshtein indique le nombre de manipulations (ajout, suppression, remplacement) qu’il faut faire pour arriver d’une chaîne à une autre. Donc 0 est une égalité parfaite, et plus le chiffre augmente, plus les chaînes sont différentes.
Si vous souhaitez en savoir plus, vous pouvez aller voir la fiche Wikipedia.
Pour l’implémenter, vous pourrez trouver le code sur le web, par exemple le code source en fonction MySQL. Même remarque que pour Jaro Winkler, ce sont des fonctions consommatrices.
Voici ce que donne quelques exécutions de la fonction en MySQL avec différentes chaînes :
