algorithmes d'auto-complétion, papiers, stratégies, etc.

Question

Je me demande si quelqu'un a de bonnes ressources à lire ou du code à expérimenter pour " autcomplete "

Je voudrais savoir quelle est la théorie derrière l'auto-complétion, par où commencer, quelles sont les erreurs courantes, etc.

J'ai trouvé fascinante la manière dont des produits tels qu'Enso, Launchy, Google Chrome et même tcsh effectuent leur auto-complétion. J'ai commencé par moi-même juste par curiosité avec un exemple de code et j'en suis arrivée à la conclusion que ce devait être un domaine largement exploré auparavant.

J'apprécierais que quelqu'un partage une bonne ressource technique sur la manière 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 d'auto-complétion (il est peut-être encore intéressant de lire pour la théorie ) http://www.patentstorm.us/patents/5845300/description.html
• http://ask.metafilter.com/91068/Fuzzy-text- algorithme d'achèvement pour une discussion de haut niveau sur les stratégies à adopter.

Answer 2

Découvrez ce blog sur la mise en œuvre de la saisie semi-automatique à l'aide de GWT:

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

Mais je vous recommanderais d’abord de commencer par quelque chose de très simple pour comprendre comment l’implémentation est effectuée. Je commencerais par un Trie, peut-être même complètement stocké sur le client, avant de passer à l'optimisation avec les requêtes du serveur si vous pensez qu'elles sont nécessaires.

Answer 3

La saisie semi-automatique est généralement implémentée à l'aide de l'un des éléments suivants:

• Arbres . En indexant le texte interrogeable dans une arborescence (arborescence de préfixes, arborescence de suffixes, dawg, etc.), il est possible d’exécuter des recherches très rapides aux dépens de la mémoire. La traversée de l’arbre peut être adaptée pour une correspondance approximative.
• Partition de modèle . En partitionnant le texte en jetons (ngrams), il est possible d’exécuter des recherches sur les occurrences de modèles à l’aide d’un schéma de hachage simple.
• Filtrage . Recherchez un ensemble de correspondances potentielles, puis appliquez un algorithme séquentiel pour vérifier chaque candidat.

Quelques articles sur le sujet:

• Borivoj Melichar. Correspondance approximative de chaînes par automates finis;
• Gonzalo Navarro. Visite guidée pour rechercher approximativement les correspondances de chaînes;
• Leonid Boytsov. Méthodes d'indexation pour la recherche approximative de dictionnaires: analyse comparative;
• Marios Hadjieleftheriou et Divesh Srivastava. Traitement approximatif de la chaîne;
• Surajit Chaudhuri et Raghav Kaushik. Extension de l'auto-complétion pour tolérer les erreurs;

Jetez un coup d'oeil à la complètement , une bibliothèque Java à complétion automatique.