La recherche fuzzy avec distance de Levenshtein

Vous tapez « jetton » dans un moteur de recherche. Vous vouliez écrire « jeton ». Résultat : zéro trouvailles. Frustrant, non ?

C'est exactement le problème que résout la recherche fuzzy — une méthode qui accepte que vous ne soyez pas parfait, et qui trouve quand même ce que vous cherchez.

Qu'est-ce qu'une recherche fuzzy ?

Le mot vient de l'anglais fuzzy : flou, approximatif. Une recherche fuzzy ne cherche pas l'exactitude stricte. Elle cherche la proximité.

Au lieu de dire « ce mot est différent, donc je ne le montre pas », elle dit « ce mot est presque le même, donc je le montre quand même ».

🎯 En clair : la recherche fuzzy tolère les fautes de frappe, les inversions de lettres, les omissions et les substitutions.

La distance de Levenshtein : le compteur d'erreurs

L'algorithme le plus connu pour mesurer cette proximité s'appelle la distance de Levenshtein. Inventé en 1965 par le mathématicien russe Vladimir Levenshtein, il répond à une question simple :

« Combien d'opérations faut-il pour transformer un mot en un autre ? »

Les opérations autorisées sont trois :

• Insertion : ajouter une lettre — jeton → jetton (ajout d'un t)
• Suppression : retirer une lettre — token → tokn (retrait du e)
• Substitution : remplacer une lettre — rag → rack (remplacement du g par ck)

Exemples concrets

Le seuil adaptatif : pas trop, pas trop peu

Si on accepte une distance de 5 sur un mot de 3 lettres, n'importe quel mot matchera. Si on exige une distance de 0, seuls les mots exacts passeront.

La solution : un seuil adaptatif selon la longueur du mot :

• Mot de 3 lettres ou moins → seuil de 0 (exactitude seule)
• Mot de 4 à 5 lettres → seuil de 1 (une erreur tolérée)
• Mot de 6 à 8 lettres → seuil de 2 (deux erreurs tolérées)
• Mot de plus de 8 lettres → seuil de 3 (trois erreurs tolérées)

Ce seuil proportionnel évite les faux positifs tout en restant permissif là où c'est pertinent.

Les alias : le filet de sécurité

La distance de Levenshtein ne suffit pas toujours. Prenons « RAG » : c'est un acronyme de 3 lettres. Avec un seuil de 0, même « Rag » avec une majuscule ne matcherait pas si on est strict.

C'est pourquoi on ajoute des alias : des formes alternatives stockées avec chaque terme. Pour « RAG », les alias peuvent être :

• rag (minuscule)
• retrieval augmented generation (forme longue anglaise)
• génération augmentée (forme longue française)

Quand vous cherchez « rack », l'algorithme teste :

1. Est-ce que « rack » est inclus exactement dans le titre ? Non.
2. Quelle est la distance de Levenshtein entre « rack » et « RAG » ? 2. Le seuil pour 3 lettres est 0 ou 1 selon la rigueur.
3. Quelle est la distance entre « rack » et les alias ? « rack » vs « rag » = 2. Possible match.

En pratique, avec un seuil légèrement plus permissif pour les petits mots (seuil 1 pour 3-4 lettres), « rack » trouve bien « RAG ».

Comment ça marche concrètement ?

Voici le cœur de l'algorithme, simplifié :

function levenshtein(motA, motB) {
  // On construit une matrice
  // Chaque case [i][j] = distance entre
  // les i premières lettres de motA
  // et les j premières lettres de motB

  for (chaque lettre de motA) {
    for (chaque lettre de motB) {
      si les lettres sont identiques :
        cout = 0
      sinon :
        cout = 1

      distance = minimum(
        case_du_haut + 1,      // suppression
        case_de_gauche + 1,    // insertion
        case_diagonale + cout  // substitution
      )
    }
  }

  return valeur_en_bas_à_droite
}

La complexité est de O(n × m) où n et m sont les longueurs des deux mots. Pour des mots de moins de 20 lettres, c'est instantané.

L'application au glossaire d'Aide IA

Le glossaire d'explodev.fr contient 1 293 termes couvrant l'intelligence artificielle et l'informatique. Sans recherche fuzzy, une faute de frappe = zéro résultat.

Avec la recherche fuzzy mise en place :

• 11 620 alias générés automatiquement (acronymes, fautes de frappe, variantes)
• Seuil adaptatif selon la longueur du mot
• Recherche sur sous-chaînes glissantes

Résultat : même si vous tapez « jetton », « rack » ou « toke », le bon terme apparaît.

Pour aller plus loin

La distance de Levenshtein n'est pas la seule approche. Voici d'autres techniques de recherche approximative :

• Soundex / Metaphone : recherche phonétique (base sur la prononciation)
• N-grams : découpe les mots en sous-séquences de n lettres
• TF-IDF : pondère l'importance des mots dans un corpus
• Embeddings sémantiques : recherche par sens, pas par lettres

Mais pour un glossaire de 1 300 termes en JavaScript client-side, la distance de Levenshtein reste le meilleur compromis : rapide, compréhensible, et suffisamment puissante.

💡 L'essentiel : la recherche fuzzy, c'est l'intelligence artificielle appliquée à l'interface. Elle anticipe que vous n'êtes pas parfait — et vous aide quand même.