algorithmes de saisie semi-automatique, des papiers, des stratégies, etc

Question

Je me demande si quelqu'un a de bonnes ressources pour lire ou code pour expérimenter pour « autcomplete »

Je voudrais savoir quelle est la théorie derrière autocomplétion, où commencer ce sont J'ai trouvé fascinant la façon dont les produits comme Enso, Launchy, Google Chrome et même tcsh effectuent leur auto complète, je me suis lancé juste pour la curiosité de l'échantillon de code et je suis arrivé à la conclusion que cela doit être un domaine largement exploré auparavant.

Je serais reconnaissant si quelqu'un partage une bonne ressource technique sur la façon de mettre en œuvre cela.

Merci d'avance.

Answer 1

• http://humanized.com/weblog/2007/03/30/what_makes_a_good_autocomplete/ -
• http://social.msdn.microsoft.com/Forums/en-US/vblanguage/thread/2ccb37b9-c7e1-4113-86ac-ad3d33b4b4b1/ - dans le monde .Net
• Un méchant brevet sur l'approche autocomplétion (encore peut-être la peine de lire pour la théorie ) http://www.patentstorm.us/patents/5845300/description.html
• http://ask.metafilter.com/91068/Fuzzy-text-completion-algorithm pour un haut discussion de niveau sur les stratégies à adopter.

Answer 2

Vérifiez ce blog sur la mise en œuvre à l'aide autocomplete GWT:

http://jroller.com/glongman/entry/gwt_autocompleter

Mais je vous recommande d'abord commencer par quelque chose de très simple sur votre propre à comprendre comment la mise en œuvre se fait. Je commencerai par un Trie, peut-être même stocké complètement sur le client, puis je passerai à l'optimisation avec les requêtes du serveur si vous pensez qu'elles sont nécessaires.

Answer 3

Autocomplete est généralement mis en œuvre en utilisant une des opérations suivantes:

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

Quelques articles sur le sujet:

• Bořivoj Melichar. Approximation de chaîne approximative par des automates finis;
• Gonzalo Navarro. Une visite guidée pour rapprocher les cordes;
• Leonid Boytsov. Méthodes d'indexation pour la recherche d'un dictionnaire approximatif: analyse comparative;
• Marios Hadjieleftheriou et Divesh Srivastava.Traitement de chaîne approximatif;
• Surajit Chaudhuri et Raghav Kaushik. Extension de l'auto-complétion pour tolérer les erreurs

Jetez un oeil à completely, une bibliothèque Java autocomplete.