Fuzzy Search

La recherche approximative (fuzzy search) est une technique de recherche tolérante aux variantes orthographiques, qui fait correspondre des résultats approchés sur la base de la distance d'édition, des n-grammes ou d'algorithmes phonétiques.

Objectif

Renvoyer des résultats pertinents même lorsque la saisie de l'utilisateur contient des fautes de frappe ou des variantes, améliorant l'expérience de recherche.

Mécanisme

Méthodes courantes : correspondance par seuil de distance de Levenshtein, index inversés de n-grammes, accélération par BK-tree, correspondance phonétique Soundex/Metaphone et algorithme Bitap. Des implémentations sont fournies par fuse.js, la requête fuzzy d'Elasticsearch, entre autres.

Cas d’usage

Correction orthographique dans les moteurs de recherche
Autocomplétion en ligne de commande
Requêtes floues en base de données
Recherche de code (tolérante aux fautes)

Exemples

entrée

recieve → receive

Output

Matches receive (distance 2)

Spelling correction

Erreurs courantes

Overly loose thresholds cause too many false matches: Adjust thresholds dynamically based on word length

Termes associés

Levenshtein Distance

La distance de Levenshtein est le nombre minimal d'insertions, de suppressions et de substitutions d'un seul caractère nécessaires pour rendre deux chaînes identiques.

Soundex est un algorithme phonétique qui encode les noms anglais selon leur prononciation en une lettre plus trois chiffres, attribuant le même code aux noms à consonance proche ; il sert à la recherche approximative de noms de personnes.

Un N-gramme est une séquence de N unités consécutives (caractères ou mots) extraites d'un texte, utilisée dans les modèles de langage, la similarité et l'analyse de texte.

La distance d'édition est le nombre minimal d'opérations d'édition d'un seul caractère (insertion, suppression, substitution) nécessaires pour transformer une chaîne en une autre ; la distance de Levenshtein en est la forme la plus courante.

References