Duplicata possible :
Comment fonctionne l'algorithme Google "Did you mean ? Algorithme fonctionne-t-il ?
Supposons que vous ayez déjà un système de recherche sur votre site web. Comment pouvez-vous implémenter le "Did you mean : <spell_checked_word> "comme Google le fait dans certains requêtes de recherche ?
En fait, ce que fait Google est très peu trivial et, à première vue, contre-intuitif. Il ne procède pas à une vérification dans un dictionnaire, mais utilise des statistiques pour identifier les requêtes "similaires" qui ont donné plus de résultats que votre requête. L'algorithme exact n'est évidemment pas connu.
Il y a différents sous-problèmes à résoudre ici, comme une base fondamentale pour toutes les statistiques liées au traitement du langage naturel, il y a un livre indispensable : Fondation du traitement statistique du langage naturel .
Concrètement, pour résoudre le problème de la similarité entre les mots et les requêtes, j'ai obtenu de bons résultats avec l'utilisation de Modifier la distance Il s'agit d'une mesure mathématique de la similarité des chaînes de caractères qui fonctionne étonnamment bien. J'avais l'habitude d'utiliser Levenshtein mais les autres peuvent être intéressantes.
Le Soundex - d'après mon expérience - est merdique.
En fait, le stockage et la recherche efficaces d'un grand dictionnaire de mots mal orthographiés, ainsi que l'extraction en moins d'une seconde, ne sont pas non plus chose aisée. Votre meilleure chance est d'utiliser les moteurs d'indexation et d'extraction de texte intégral existants (c'est-à-dire pas celui de votre base de données), dont les suivants Lucene est actuellement l'un des meilleurs et, par coïncidence, il a été porté sur de nombreuses plateformes.
Norvig, de Google, a expliqué comment cela fonctionne ; il a même donné une implémentation Python d'une vingtaine de lignes :
http://googlesystem.blogspot.com/2007/04/simplified-version-of-googles-spell.html
http://www.norvig.com/spell-correct.html
Le Dr Norvig aborde également la question du "vouliez-vous dire" dans cet excellent exposé . Le Dr Norvig est chef de la recherche chez Google - lorsqu'on lui demande comment est implémenté le "did you mean", sa réponse est la suivante autoritaire .
Il s'agit donc d'une vérification orthographique, vraisemblablement avec un dictionnaire dynamique construit à partir d'autres recherches ou même de phrases Internet réelles et autres. Mais c'est toujours vérification de l'orthographe .
SOUNDEX et autres suppositions n'ont pas droit de cité, les gens !
J'ai été agréablement surpris que quelqu'un ait demandé comment créer un système de suggestion orthographique de pointe pour les moteurs de recherche. Je travaille sur ce sujet depuis plus d'un an pour une société de moteurs de recherche et je peux indiquer des informations du domaine public sur le sujet.
Comme nous l'avons mentionné dans un précédent article, Google (ainsi que Microsoft et Yahoo !) n'utilise pas de dictionnaire prédéfini et n'emploie pas non plus des hordes de linguistes qui réfléchissent aux éventuelles fautes d'orthographe des requêtes. Cela serait impossible en raison de l'ampleur du problème, mais aussi parce qu'il n'est pas certain que les gens puissent identifier correctement quand et si une requête est mal orthographiée.
Il existe au contraire un principe simple et plutôt efficace qui est également valable pour toutes les langues européennes. Récupérez toutes les requêtes uniques de vos journaux de recherche, calculez la distance d'édition entre toutes les paires de requêtes, en supposant que la requête de référence est celle qui a le nombre le plus élevé.
Cet algorithme simple fonctionne parfaitement pour de nombreux types de requêtes. Si vous voulez passer au niveau supérieur, je vous suggère de lire l'article de Microsoft Research à ce sujet. Vous pouvez le trouver aquí
Le document contient une excellente introduction, mais vous devrez ensuite vous familiariser avec des concepts tels que le modèle de Markov caché.
Vérifiez ce article sur wikipedia à propos de la distance de Levenshtein. Assurez-vous de bien regarder les améliorations possibles.
Je vous suggère de regarder SOUNDEX pour trouver des mots similaires dans votre base de données.
Vous pouvez également accéder à votre propre dictionnaire google en utilisant la fonction Demande de suggestions orthographiques dans l'API Google .
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
