algoritmi, documenti, strategie di completamento automatico, ecc

Question

Mi chiedo se qualcuno ha buone risorse da leggere o programmare per sperimentare "completamento automatico"

Vorrei sapere qual è la teoria alla base del completamento automatico, da dove iniziare quali sono gli errori comuni ecc.

Ho trovato affascinante il modo in cui prodotti come Enso, Launchy, Google Chrome e persino tcsh eseguono il loro completamento automatico, ho iniziato da solo per curiosità un po 'di codice di esempio e sono arrivato alla conclusione che questo deve essere un campo ampiamente esplorato prima.

Gradirei se qualcuno condividesse qualche buona risorsa tecnica su come implementarlo.

Grazie in anticipo.

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/ - nel mondo .Net
• Un brutto brevetto sull'approccio al completamento automatico (forse vale ancora la pena leggere per la teoria ) http://www.patentstorm.us/patents/5845300/description.html
• http://ask.metafilter.com/91068/Fuzzy-text- algoritmo di completamento per una discussione di alto livello sulle strategie da adottare.

Answer 2

Dai un'occhiata a questo blog sull'implementazione del completamento automatico utilizzando GWT:

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

Ma ti consiglio di iniziare con qualcosa di molto semplice da solo per capire come viene eseguita l'implementazione. Comincerei con un Trie, forse anche memorizzato completamente sul client, quindi passerei all'ottimizzazione con le query del server se ritieni che siano necessarie.

Answer 3

Il completamento automatico viene in genere implementato utilizzando una delle seguenti opzioni:

• Alberi . Indicizzando il testo ricercabile in una struttura ad albero (albero dei prefissi, albero dei suffissi, dawg, ecc.) È possibile eseguire ricerche molto veloci a spese della memoria. L'attraversamento dell'albero può essere adattato per una corrispondenza approssimativa.
• Partizionamento dei pattern . Suddividendo il testo in token (ngram) è possibile eseguire ricerche per occorrenze di pattern utilizzando un semplice schema di hashing.
• Filtri . Trova una serie di potenziali corrispondenze e quindi applica un algoritmo sequenziale per controllare ciascun candidato.

Un paio di articoli sull'argomento:

• Bo & # 345; ivoj Melichar. Corrispondenza approssimativa delle stringhe di Automi finiti;
• Gonzalo Navarro. Una visita guidata alla corrispondenza approssimativa delle stringhe;
• Leonid Boytsov. Metodi di indicizzazione per la ricerca approssimativa nel dizionario: analisi comparativa;
• Marios Hadjieleftheriou e Divesh Srivastava. Elaborazione approssimativa delle stringhe;
• Surajit Chaudhuri e Raghav Kaushik. Estensione del completamento automatico per tollerare errori;

Dai un'occhiata a completamente , una libreria di completamento automatico Java.