Salut et bienvenue dans ce nouvel épisode du podcast de Code Garage, je m'appelle Nicolas
Brandon Bernard et aujourd'hui on va parler de l'algorithme de Levenstein.
Donc comparer deux chaînes de caractère c'est un des premiers exercices qu'on apprend
à réaliser quand on étudie la programmation.
Donc ça, évidemment, c'est un truc très facile à réaliser quand on compare deux
chaînes de caractère qu'on a écrites dans un programme, mais quand une de ces chaînes
a été écrite par un humain, la tâche devient beaucoup plus compliquée.
Alors, normalement, le premier réflexe c'est d'effectuer deux opérations avant d'utiliser
l'opérateur de comparaison classique.
C'est par exemple passer les deux chaînes en minuscule pour éviter tout problème de
casse et enlever tous les accents.
Alors ça, c'est un bon début, mais en cas de faute d'orthographe ou simplement
de faute de frappe, votre simple algorithme de comparaison, il sera plus suffisant.
Donc comment faire comprendre à votre code que par exemple, titaniques avec un C et
titaniques avec un K sont à peu près équivalents entre eux ?
Eh bien, on va apprendre à faire ça grâce à l'algorithme qui est appelé distance
de Levenstein.
Donc le fonctionnement de cet algorithme, il est simple à comprendre et il peut être
très puissant s'il est bien utilisé.
L'algorithme consiste à comparer la distance entre deux chaînes en fonction d'un nombre
de transformation basique minimum à effectuer pour rendre les deux chaînes de caractère
similaire entre elles.
Alors qu'est-ce que ça veut dire ?
Ces transformations sont au nombre de trois.
Donc ça peut être l'ajout d'un caractère, la suppression d'un caractère ou le remplacement
d'un caractère.
Imaginons, reprenons notre exemple avec titanique.
Eh bien, par exemple, pour rendre les chaînes titaniques avec un C et titaniques avec
un K similaire, eh bien il faut remplacer un caractère.
On remplace le K par le C.
Ou le C par le K, selon dans le sens où on le prend.
Et donc, remplacement d'un caractère, c'est une transformation.
Chaque transformation, donc que ce soit l'ajout d'un caractère, la suppression ou le remplacement,
ça a une valeur de 1 pour le calcul de la distance.
Donc en fait, il suffit d'additionner le nombre de transformations qu'on a effectuées
sur la chaîne pour avoir cette distance.
En l'occurrence, la distance de l'Ewenstein entre titanique avec un K et titanique avec
un C, eh bien c'est de 1.
Si on avait écrit par exemple, titanique avec un K et un deuxième T au milieu, eh bien
ça aurait été de 2 puisqu'on a reçu une transformation qui est donc le remplacement
du K en C et la suppression d'un caractère, le T entre O.
Ça aurait été donc la distance de 2.
Donc comme vous aurez pu le remarquer, si on utilise seulement la distance de l'Ewenstein
sans prendre le soin de transformer les chaînes de caractère préalables, eh bien l'algorithme,
il prendra la K en compte, les accents en compte, etc.
Donc l'idéal, c'est de commencer par ces deux transformations au préalable avant
de calculer cette distance.
Mais il faut aussi réfléchir à la distance idéale pour laquelle on souhaite accepter
une réponse ou non.
Parce qu'en effet, plus la distance acceptée est grande, plus votre code, pardon, sera
permissif évidemment, et il risque de laisser passer ce qu'on appelle des faux positifs.
Et à l'inverse, une distance acceptée qui est trop petite, ça risque d'écarter des
mots pourtant très proches.
Donc voilà comme j'ai dit tout à l'heure, par exemple en français, juste un oubli avec
un S ou un S en trop, eh bien c'est déjà égal à une distance de 1.
Donc ça veut dire que c'est une faute qui est très commune, ou une faute de frappe qui
est très commune.
Et donc si on se limite à ça, en fait on ne peut pas, on n'a pas le droit à l'erreur
pour d'autres choses.
Alors il n'existe pas réellement de distance idéale.
Tout dépend de la langue dans laquelle est appliqué l'algorithme, mais aussi éventuellement
la taille du mot d'origine.
Parce que oui, une distance de 1 sur un mot de 3 lettres ou sur un mot de 10 lettres,
ça a pas réellement le même impact dans une mise en situation réelle.
Après, c'est à vous de faire vos tests et de trouver pour chaque cas d'utilisation
la bonne manière d'utiliser cet algorithme.
Alors il y a quelques inconvénients quand même.
Outre le fait qu'il n'existe pas de distance idéale, le point de vigilance, il se situe
surtout sur le type de données que vous souhaitez vérifier.
Par exemple, dans le cadre d'un quiz, on imagine que les réponses 100s et chien avec
un s sont autant valides l'une que l'autre.
Mais les réponses 1968 et 1969 n'ont pas du tout la même signification.
Alors que si on prend juste les chaînes de caractère, ces propositions, elles ont la
même distance de l'Evenstein qui est égale à 1.
Donc il ne faut pas appliquer cette distance sans prendre en compte le format des données
qu'on attend en entrée.
Il faut bien réfléchir à la pertinence de cette méthode pour votre cas d'usage précis.
Alors cet algorithme, il est assez facile, on va dire, à implémenter, mais il y a des
implémentations qui sont plus efficaces que d'autres et d'autres qui ont été optimisés.
Donc ce que vous pouvez faire, c'est qu'il y a déjà plein de librairies de bibliothèques
qui implémentent cette distance de l'Evenstein.
Donc je vous mets par exemple un lien d'une implementation qui est très rapide à exécuter
en JavaScript qui est disponible sur NPM.
Je vous le mets dans les liens directement de l'épisode.
Et puis sinon, si vous êtes intéressé par le pseudo-code qui y a derrière cet algorithme,
eh bien je vous mets la page Wikipedia directement où il y a le pseudo-code.
J'espère que cet épisode vous a été utile, que vous aurez appris quelque chose.
Et moi je vous donne rendez-vous à la semaine prochaine pour un prochain épisode ou alors
directement sur code-garage.fr.
Code-garage, qu'est-ce que c'est ? C'est un site de formation, de cours où vous pouvez
accéder à tous les cours en illimité pour 19€ 419 par mois.
Vous avez des cours sur Git, sur SQL, sur comment devenir freelance ou comment trouver
un job en tant que développeur junior, etc.
Tous les cours, vous y avez accès en illimité simplement pour un abonnement fixe.
C'est un petit peu le Netflix des cours pour les devs.
Voilà, à la semaine prochaine !