Récupération tolérante et par caractères génériques

La récupération tolérante permet à un système de recherche de faire correspondre des requêtes malgré les variations orthographiques, les caractères génériques et les différences phonétiques, afin que les utilisateurs trouvent toujours des documents pertinents même lorsque la requête et le texte ne correspondent pas exactement.

Definition

La récupération tolérante comprend des techniques au niveau du dictionnaire qui font correspondre les termes de requête aux termes indexés malgré des entrées incomplètes, mal orthographiées ou phonétiquement variables, y compris l'expansion des caractères génériques, la correction orthographique basée sur la distance d'édition et l'encodage phonétique.

Scope

Ce sujet aborde les techniques qui assouplissent la correspondance exacte des termes au niveau du dictionnaire : le traitement des requêtes par caractères génériques à l'aide d'index permuterm et de k-grammes, la correction orthographique par distance d'édition et contexte, et la correspondance phonétique telle que Soundex. Il examine comment le dictionnaire de termes est augmenté pour prendre en charge ces recherches approximatives et comment les termes candidats sont générés et classés, distinctement de la correspondance sémantique, qui traite du sens plutôt que de la forme de surface.

Core questions

• Comment les requêtes par caractères génériques, telles que les motifs de préfixe, de suffixe et d'infixe, sont-elles évaluées par rapport au dictionnaire ?
• Comment les index permuterm et de k-grammes prennent-ils en charge les recherches par caractères génériques ?
• Comment le terme le plus proche correctement orthographié est-il trouvé pour un terme de requête mal orthographié ?
• Comment la distance d'édition (Levenshtein) quantifie-t-elle la différence entre deux chaînes de caractères ?
• Comment la correspondance phonétique telle que Soundex regroupe-t-elle les termes qui se ressemblent phonétiquement ?

Key concepts

• requête par caractère générique
• index permuterm
• index de k-grammes
• distance d'édition (Levenshtein)
• correction orthographique
• correspondance phonétique (Soundex)
• correspondance approximative de chaînes de caractères
• génération de termes candidats

Key theories

Indexation par caractères génériques avec les index permuterm et de k-grammes

Faire pivoter les termes de manière à ce qu'un caractère générique tombe toujours à la fin (permuterm) ou indexer les termes par leurs k-grammes de caractères permet au système de convertir un motif de caractère générique en recherches de dictionnaire ordinaires qui récupèrent des termes candidats.

Correction orthographique par distance d'édition

Le nombre minimum d'insertions, de suppressions et de substitutions d'un seul caractère nécessaires pour transformer une chaîne en une autre (distance d'édition) fournit une mesure fondée pour proposer des alternatives correctement orthographiées à un terme de requête, souvent combinée avec la fréquence des termes et le contexte.

Clinical relevance

La récupération tolérante alimente les fonctionnalités de recherche quotidiennes : les suggestions orthographiques de type 'voulez-vous dire', l'autocomplétion et la recherche par préfixe, ainsi que la correspondance tolérante des noms et des termes de produits. Elle améliore considérablement le rappel et l'expérience utilisateur lorsque les requêtes contiennent des fautes de frappe ou lorsque les utilisateurs ne connaissent pas l'orthographe exacte.

History

La correspondance approximative et la correction orthographique ont une longue histoire en informatique, avec Soundex datant de l'indexation des registres du début du XXe siècle. L'enquête de Kukich de 1992 a consolidé les techniques de correction orthographique automatique, et l'enquête de Navarro de 2001 a systématisé la correspondance approximative de chaînes de caractères. Ces méthodes sont devenues des composants standards des dictionnaires de recherche à mesure que la recherche sur le web rendait essentielle la gestion tolérante des requêtes.

Key figures

• Karen Kukich
• Gonzalo Navarro

Seminal works

• manning2008
• kukich1992
• navarro2001

Frequently asked questions

Comment un moteur de recherche gère-t-il un caractère générique comme 'comput*' ?

Il utilise une structure de dictionnaire auxiliaire, telle qu'un index permuterm ou de k-grammes, pour trouver tous les termes correspondant au motif (computer, computing, computation, etc.), puis évalue la requête originale comme si ces termes avaient été listés explicitement.

Qu'est-ce que la distance d'édition et pourquoi est-elle utilisée pour la correction orthographique ?

La distance d'édition compte le nombre minimum d'insertions, de suppressions et de substitutions d'un seul caractère nécessaires pour transformer un mot en un autre. Une petite distance d'édition entre un terme de requête mal orthographié et un terme du dictionnaire suggère que le terme du dictionnaire est une correction probable et intentionnelle.