Algorithme pour l'autocomplétion ?

Question

Je fais référence à l'algorithme qui est utilisé pour donner des suggestions de requête lorsqu'un utilisateur tape un terme de recherche dans Google.

Je suis principalement intéressé par la façon dont l'algorithme de Google est capable de montrer : 1. Les résultats les plus importants (les requêtes les plus probables plutôt que tout ce qui correspond) 2. Les sous-chaînes correspondantes 3. Correspondances floues

Je sais que vous pourriez utiliser Trie ou Trie généralisé pour trouver des correspondances, mais cela ne répondrait pas aux exigences ci-dessus...

Questions similaires posées précédemment aquí

Answer 1

Pour des algorithmes de correspondance de chaînes de caractères flous/partiels (heh) géniaux, consultez Damn Cool Algorithms :

• http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees
• http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata

Ils ne remplacent pas les essais, mais empêchent plutôt les recherches par force brute dans les essais, ce qui est tout de même une grande victoire. Ensuite, vous voulez probablement trouver un moyen de limiter la taille de la trie :

• tenez une liste des mots les plus récents/les plus utilisés dans le monde ;
• pour chaque utilisateur, conserver une trie des mots récents ou des N premiers mots pour cet utilisateur.

Enfin, vous voulez éviter les consultations lorsque c'est possible...

• mise en cache des résultats de la recherche : si l'utilisateur clique sur les résultats de la recherche, vous pouvez les servir très rapidement, puis récupérer de manière asynchrone la recherche complète, partielle ou floue.
• précalculer les résultats de la recherche : si l'utilisateur a tapé "appl", il est probable qu'il continue avec "apple", "apply".
• Prélivrer les données : par exemple, une application web peut envoyer un ensemble de résultats plus petit au navigateur, suffisamment petit pour rendre viable la recherche par force brute en JS.

Answer 2

Je voudrais juste dire... Une bonne solution à ce problème va incorporer plus qu'un arbre de recherche ternaire. Des Ngrams et des Shingles (phrases) sont nécessaires. Les erreurs de frontières entre les mots doivent également être détectées. "hell o" devrait être "hello" ... et "whitesocks" devrait être "white socks" - ce sont des étapes de prétraitement. Si vous ne pré-traitez pas les données correctement, vous n'obtiendrez pas de résultats de recherche valables. Les arbres de recherche ternaires sont un élément utile pour déterminer ce qu'est un mot, et aussi pour mettre en œuvre la supposition de mots apparentés lorsqu'un mot tapé n'est pas un mot valide dans l'index.

L'algorithme de Google suggère et corrige les phrases. L'algorithme de Google a également une certaine notion du contexte... si le premier mot que vous recherchez est lié à la météo et que vous les combinez "weatherforcst" vs "monsoonfrcst" vs "deskfrcst" - je suppose que, dans les coulisses, les classements sont modifiés dans la suggestion en fonction du premier mot rencontré - la prévision et la météo sont des mots liés, donc la prévision obtient un rang élevé dans la suggestion "Did-You-Mean".

mots-partiels (ngrams), phrases-termes (shingles), mots-proximité (word-clustering-index), arbre de recherche ternaire (word lookup).

Answer 3

L'algorithme exact de Google est inconnu, mais il est dit de travailler par analyse statistique des données des utilisateurs. Une approche qui ne convient pas à la plupart des cas. Plus souvent, la complétion automatique est mise en œuvre en utilisant l'une des méthodes suivantes :

• Arbres . En indexant le texte à rechercher dans une structure arborescente (arbre préfixe, arbre suffixe, dawg, etc.) on peut exécuter des recherches très rapides au détriment du stockage en mémoire. La traversée de l'arbre peut être adaptée pour la correspondance approximative.
• Partitionnement des motifs . En partitionnant le texte en tokens (ngrammes), il est possible d'exécuter des recherches d'occurrences de motifs en utilisant un simple schéma de hachage.
• Filtrage . Trouvez un ensemble de correspondances potentielles, puis appliquez un algorithme séquentiel pour vérifier chaque candidat.

Jetez un coup d'œil à complètement une bibliothèque de complétion automatique en Java.

Answer 4

Jetez un coup d'œil à L'algorithme de la barre Awesome de Firefox

Google suggest est utile, car il prend en compte les millions de requêtes populaires + vos requêtes antérieures liées.

Il n'a cependant pas un bon algorithme de complétion / interface utilisateur :

1. Ne fait pas de sous-chaînes
2. Cela semble être un algorithme relativement simple de préfixation des limites des mots.
   Par exemple : Essayez tomcat tut --> suggère correctement "tomcat tutorial". Essayez maintenant tomcat rial --> aucune suggestion )- :
3. Ne supporte pas le "vous voulez dire ?" - comme dans les résultats de recherche de Google.

Answer 5

Il existe des outils comme soundex y distance de levenshtein qui peut être utilisé pour trouver des correspondances floues qui se situent dans une certaine fourchette.

Soundex trouve les mots qui se ressemblent et la distance levenshtein trouve les mots qui se trouvent à une certaine distance d'édition d'un autre mot.