Comment comparer deux chaînes de caractères contenant des fautes ?

Comparer deux strings est l'un des premiers exercices que l'on apprend à réaliser lorsque l'on étudie la programmation, mais lorsque l'une de ces chaînes a été écrite par un humain, la tâche devient beaucoup plus compliqué.

Normalement votre premier réflexe est d'effectuer deux opérations avant d'utiliser l'opérateur de comparaison classique :

• Passer les deux chaînes en minuscule pour éviter tout problème de casse
• Enlever tous les accents

Et c'est un bon début, mais en cas de faute d'orthographe ou de simple faute de frappe, votre simple algorithme de comparaison ne sera plus suffisant.

Alors comment faire comprendre à votre code que "Titanic" et "Titanik" sont bien équivalents entre eux? Nous allons apprendre à faire cela grâce à un algorithme assez simple appelé "distance de Levenshtein".

La distance de Levenshtein

Le fonctionnement de cet algorithme est simple à comprendre mais peut être très puissant si il est bien utilisé.

Le principe

L'algorithme consiste à comparer la distance entre deux chaines en fonction du nombre de transformations basiques minimum à effectuer pour rendre les String similaires entre elles.

Ces transformations sont au nombre de trois, lesquelles sont :

• L'ajout d'un caractère
• La suppression d'un caractère
• Le remplacement d'un caractère

Par exemple, pour rendre les chaînes "developpeur" et "developers" similaire il faudra appliquer les transformations suivantes au premier mot :

• suppression du caractère "p" à la position 6
• suppression du caractère "u" à la position 9
• ajout du caractère "s" à la fin de la chaîne

Chaque transformation ayant la même valeur (1) pour le calcul de la distance, il suffit d'additionner le nombre de transformations effectuées. En l’occurrence, la distance de Levenshtein entre "developpeur" et "developers" est de 3.

Utilisation

Comme vous aurez pu le remarquer si l'on utilise seulement la distance de Levenshtein sans prendre le soin de transformer les chaînes de caractères au préalable, l'algorithme prendra la casse ainsi que les accents en compte.

L'idéal est donc de commencer par ces deux transformations au préalable avant de calculer la distance entre les deux chaines, mais il faut aussi réfléchir à la distance idéale pour laquelle on souhaite accepter une réponse ou non.

En effet, plus la distance acceptée est grande, plus votre code sera permissif et risque de laisser passer des faux-positifs, et à l'inverse une distance acceptée trop courte risque d'écarter des mots pourtant très proches.

Par exemple un simple oubli de "s" est déjà égal à une distance de 1

Il n'existe pas réellement de distance idéal, tout dépend de la langue sur laquelle elle est appliquée ainsi que de la taille du mot d'origine. Car oui une distance de 1 sur un mot de 3 lettres ou sur un mot de 10 lettres n'a pas réellement le même impact dans une mise en situation réelle.

C'est à vous de faire vos tests et de trouver la bonne manière d'utiliser cet algorithme.

Inconvénients

Outre le fait qu'il n'existe pas de distance idéale, le point de vigilance 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 "chien" ou "chiens" 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 toutes ces propositions ont la même distance de Levenshtein égale à 1.

Il ne faut donc pas appliquer cette distance sans prendre en compte le format des données que l'on attend en entrée et bien réfléchir à la pertinence de cette méthode pour votre cas d'usage.

Implémentation en Javascript

Même si le principe de cet algorithme est très simple à comprendre, l'implémentation peut avoir un vrai rôle à jouer dans les performances de ce dernier.

Je vous mets donc le lien vers l'implémentation la plus efficiente en Javascript que vous pourrez inclure dans vos projets.

Si vous développez dans un autre langage, ne vous inquiétez pas, vous trouverez forcément une implémentation déjà existante et si vous êtes intéressé par le pseudo-code, vous en trouverez une version accessible à tous sur Wikipédia :

https://fr.wikipedia.org/wiki/Distance_de_Levenshtein#Algorithme