Une recherche qui pardonne les fautes de frappe : comment fonctionne vraiment la tolérance aux erreurs

Le problème, énoncé précisément

Un client qui cherche « hummingbrid » veut presque certainement dire « hummingbird ». Une zone de recherche qui ne renvoie aucun résultat pour cette requête n'est pas stricte pour une bonne raison : elle échoue sur la seule chose pour laquelle elle existe, trouver ce que la personne voulait dire, et pas seulement ce qu'elle a tapé. La tolérance aux fautes de frappe est le nom général des mécanismes qui comblent cet écart. On dirait une seule fonction. En réalité, ce sont au moins deux mécanismes différents, avec des coûts différents et des façons différentes d'échouer, et c'est en les confondant que la plupart des implémentations naïves se trompent.

La brique de base : la distance d'édition

Presque tous les mécanismes de tolérance aux fautes de frappe, quel que soit le moteur, reposent sur la même idée de fond : la distance d'édition entre deux chaînes, le plus souvent la distance de Levenshtein, qui compte le nombre minimum d'insertions, de suppressions ou de substitutions d'un seul caractère nécessaires pour transformer une chaîne en l'autre. « Chemize » est à une substitution de « chemise ». « Chmeise » au lieu de « chemise », avec deux lettres voisines inversées, est à une transposition : deux éditions selon la définition classique de Levenshtein, une seule dans la variante de Damerau-Levenshtein, qui compte l'inversion comme une seule édition. Le chiffre, à lui seul, ne décide rien ; ce qui compte, c'est ce que le système en fait.

Le détail à régler dès le départ : une distance d'une ou deux éditions est généreuse pour un mot long et dangereuse pour un mot court. Deux éditions sur un mot de dix lettres le changent à peine. Deux éditions sur un mot de trois lettres peuvent le transformer en un mot complètement différent : « mer » et « mur » sont à une édition l'un de l'autre, mais « mer » et « ver » aussi, tout comme « mer » et « mes ». Un système de tolérance aux fautes qui applique le même seuil de distance quelle que soit la longueur du mot finira par « corriger » joyeusement des mots courts et distincts les uns en les autres. La correction honnête est un seuil proportionné à la longueur : aucune correction sur les mots très courts, une édition autorisée à partir de quelques lettres, deux éditions seulement quand le mot est assez long pour rester reconnaissable après deux modifications.

Deux mécanismes différents, souvent confondus en une seule fonction

« Tolérance aux fautes de frappe » désigne généralement l'une de deux choses réellement différentes, et celle que propose un système change ce qu'il peut faire et ne pas faire.

1. La correspondance fuzzy au moment de la requête

Elasticsearch, OpenSearch et les moteurs similaires peuvent exécuter une requête fuzzy (ou utiliser le paramètre fuzziness d'une requête match) qui compare le terme recherché aux termes indexés en utilisant la distance d'édition au moment de la requête, sans avoir besoin de savoir à l'avance quelles fautes existent. Cela fonctionne parce que le moteur possède déjà un index inversé de tous les termes présents dans le catalogue ; une requête fuzzy revient, en gros, à « trouver les termes indexés à N éditions au plus de celui-ci, et classer les résultats selon leur proximité ». Elle ne demande aucune étape de maintenance séparée et se dégrade en douceur : une requête légèrement fausse classe quand même en tête les termes indexés les plus proches. Son vrai coût apparaît sur un champ à forte cardinalité ou un très grand vocabulaire, où calculer la distance d'édition sur un grand ensemble de termes candidats est plus lourd qu'une recherche de terme exact ; c'est pourquoi la correspondance fuzzy est généralement appliquée de façon sélective (le champ principal de texte libre, pas chaque champ mot-clé) plutôt que partout par défaut.

2. La correction par dictionnaire, appliquée seulement quand il le faut

Un système sans moteur de recherche capable de scorer nativement les correspondances fuzzy, par exemple une simple recherche basée sur SQL, doit construire le mécanisme lui-même : un dictionnaire de termes valides, construit à partir des noms de produits et de marques du catalogue, auquel on compare un terme de recherche qui n'a rien donné pour trouver le vrai mot le plus proche. Le dictionnaire est couramment indexé par trigrammes de caractères (des fragments de trois lettres) plutôt que comparé lettre par lettre à chaque mot, à la fois parce qu'un index de trigrammes réduit la liste des candidats aux mots plausiblement proches avant de calculer la distance d'édition exacte sur un ensemble bien plus petit, et parce qu'il ne demande aucun moteur externe.

Le détail qui rend cette approche économique en pratique, au lieu d'en faire un piège de performance, c'est le moment où la recherche dans le dictionnaire s'exécute. Si chaque recherche payait le coût d'une consultation du dictionnaire, la tolérance aux fautes ralentirait toutes les requêtes, y compris celles tapées correctement qui trouvaient déjà des résultats. La consultation n'a de raison de s'exécuter qu'une fois que la recherche exacte est revenue vide : une requête correcte n'y touche jamais, et seul le cas à zéro résultat paie le surcoût. Mesurées sur un vrai catalogue, une requête bien orthographiée et une requête mal orthographiée qui déclenche la consultation du dictionnaire ont pris le même temps, faible, dans les deux cas (toutes deux entre 0,16 et 0,19 seconde sur cette installation précise) : le chemin du dictionnaire n'ajoute un coût qu'aux recherches qui, sinon, n'auraient rien renvoyé du tout.

Le dictionnaire demande aussi un entretien dont une requête fuzzy n'a pas besoin : il doit apprendre les nouveaux mots à mesure que le catalogue grandit et oublier les mots des produits qui n'existent plus, sinon il se périme lentement et commence à suggérer des corrections vers des produits abandonnés. Un dictionnaire reconstruit selon un calendrier (par exemple chaque semaine, plus un complément à la demande la première fois qu'une recherche à zéro résultat a besoin d'un mot qu'il n'a pas encore) reste aligné sur le catalogue sans être reconstruit à chaque requête.

Où la version facile se casse

• Un seuil de distance d'édition fixe pour des mots de toutes les longueurs, comme vu plus haut : une correction généreuse sur les mots courts transforme des mots distincts les uns en les autres.
• Corriger une requête qui a déjà des résultats. Si une recherche qui a déjà trouvé des produits est aussi « corrigée » vers un autre terme plus populaire, le client peut être éloigné de ce qu'il a réellement tapé et envoyé vers ce que le moteur juge proche et populaire. La correction a sa place après une vraie recherche à zéro résultat, pas comme une réécriture permanente de chaque requête en arrière-plan.
• Une correction qui se déclenche discrètement quand elle ne devrait pas. Sur une page de recherche à facettes, une sélection de filtres peut légitimement donner zéro résultat (un client a choisi une combinaison de taille et de couleur que personne n'a en stock). Ce n'est pas un problème d'orthographe, et une couche de tolérance aux fautes incapable de faire la différence essaiera de « corriger » un terme parfaitement orthographié parce que ce sont les filtres, et non le mot, qui ont vidé la page.
• Compter sur la correspondance fuzzy pour garantir aussi des facettes justes. Faire en sorte qu'une requête mal orthographiée trouve quand même des produits est un problème différent de celui de compter correctement combien de produits correspondent à chaque valeur de filtre. Un moteur tolérant aux fautes qui trouve des résultats pour « hummingbrid » calculera sans hésiter les comptages de facettes pour cette même correspondance fuzzy ; si un élément en aval (une liste d'autocomplétion de « recherches populaires », par exemple) suppose que « au moins un produit trouvé » signifie « c'était un vrai terme, correctement orthographié », il republiera volontiers les fautes de frappe de la boutique auprès de chaque visiteur. C'est justement parce que le moteur tolérant fait bien son travail que cette erreur-là devient facile à commettre ailleurs dans le même système.
• Le silence au lieu de la transparence. Une recherche qui remplace discrètement le terme tapé par un autre, sans indiquer qu'une substitution a eu lieu, laisse le client se demander pourquoi les résultats ne correspondent pas tout à fait à ce qu'il a cherché. Une ligne visible et honnête, « Aucun résultat pour X. Voici les résultats pour Y », coûte une phrase et évite complètement cette confusion.

Une courte check-list

• Adaptez la distance d'édition autorisée à la longueur du mot ; n'appliquez pas le même seuil à un mot de trois lettres et à un mot de douze.
• Ne corrigez qu'après une vraie recherche à zéro résultat, jamais par une réécriture silencieuse d'une requête qui avait déjà trouvé quelque chose.
• Distinguez « le mot était mal orthographié » de « les filtres ont vidé la page » : les deux demandent un traitement différent, et les confondre produit une tentative de correction là où elle n'avait pas lieu d'être.
• Si vous maintenez votre propre dictionnaire au lieu de vous appuyer sur le scoring fuzzy intégré d'un moteur, tenez-le à jour : reconstruisez-le selon un calendrier et laissez-le apprendre du catalogue à mesure qu'il change, sinon il commencera à suggérer des mots qui n'existent plus.
• Dites au client quand une substitution a eu lieu. Ne laissez pas une correspondance fuzzy « réussie » masquer le fait que ce qu'il a tapé et ce qu'il a obtenu ne sont pas le même mot.

En bref

La tolérance aux fautes de frappe n'est pas un interrupteur marche/arrêt : c'est un choix entre deux mécanismes différents, la correspondance fuzzy native du moteur au moment de la requête, ou un dictionnaire entretenu et consulté seulement lors d'une vraie recherche à zéro résultat, chacun avec son propre coût et sa propre façon de se tromper en silence. Les deux erreurs à surveiller sont de corriger des mots qui n'étaient pas du tout mal orthographiés, et de compter sur une correspondance fuzzy pour répondre à des questions pour lesquelles elle n'a pas été conçue, comme un comptage exact de facettes. Nous gérons cela dans cll_essearch, notre module de recherche et de navigation à facettes pour PrestaShop, à la fois avec la correspondance fuzzy native d'Elasticsearch et avec notre propre dictionnaire à trigrammes pour les boutiques qui utilisent le moteur natif de la base de données, si vous voulez voir cette distinction appliquée à une vraie boutique en ligne.

Recherche Elasticsearch et Navigation à FacettesRecherche ultra-rapide, tolérante aux fautes de frappe, avec navigation à facettes moderne en panneau modal, a…99,99 €Voir le produit