Vediamo Google, Firefox alcune pagine AJAX mostrano un elenco di elementi probabili mentre i tipi di caratteri dell'utente.Qual è il miglior algoritmo di completamento automatico/suggerimento, datastructure [C++/C]
Qualcuno può fornire un buon algoritmo, struttura dati per l'implementazione del completamento automatico?
A trie è una struttura dati che può essere utilizzata per trovare rapidamente le parole che corrispondono a un prefisso.
Edit: Ecco un esempio che mostra come usare uno per implementare autocomplete http://rmandvikar.blogspot.com/2008/10/trie-examples.html
Ecco un confronto tra 3 diversi auto-complete implementations (anche se è in Java non C++).
* In-Memory Trie
* In-Memory Relational Database
* Java Set
Quando si cercano le chiavi, il trie è leggermente più veloce dell'implementazione Set. Sia il trie che il set sono un po 'più veloci della soluzione di database relazionale.
Il costo di impostazione del Set è inferiore alla soluzione Trie o DB. Dovresti decidere se stai costruendo nuovi "set di parole" frequentemente o se la velocità di ricerca è la priorità più alta.
Questi risultati sono in Java, il tuo chilometraggio può variare con una soluzione C++.
Per una soluzione semplice: si genera un 'candidato' con una modifica minima (Levenshtein) distanza (1 o 2), allora si prova l'esistenza del candidato con un contenitore di hash (impostare sarà sufficiente per un semplice soltion , quindi utilizzare unordered_set da tr1 o boost).
Esempio: Hai scritto carr e vuoi auto. arr è generato da 1 cancellazione. Arr è nel tuo stato non ordinato? No. crr è generato da 1 cancellazione. Crr è nel tuo stato non ordinato? No. la macchina è generata da 1 cancellazione. La macchina è nel tuo stato non ordinato? Sì, hai vinto.
Naturalmente c'è l'inserimento, cancellazione, ecc ... trasposizione
È vedere che il vostro algoritmo per la generazione di candidati è davvero dove stai sprecando tempo, soprattutto se si dispone di un molto poco unordered_set.
Per i set di dati di grandi dimensioni, un buon candidato per il back-end sarebbe alberi di ricerca ternari. Combinano il meglio di due mondi: il sovraccarico di spazio ridotto degli alberi di ricerca binari e l'efficienza temporale basata sui caratteri dei tentativi di ricerca digitale.
veda in Dr. Dobbs Journal: http://www.ddj.com/windows/184410528
L'obiettivo è il recupero veloce di un gruppo di risultati finito come l'utente digita in consente in primo luogo considerare che per la ricerca "informatica" è possibile iniziare a digitare da "computer". o "scienza" ma non "omputer". Quindi, data una frase, genera le sottofasi che iniziano con una parola. Ora per ciascuna frase, inseriscile nel TST (albero di ricerca ternario). Ogni nodo nel TST rappresenterà un prefisso di una frase che è stata digitata finora. Memorizzeremo i migliori 10 (diciamo) risultati per quel prefisso in quel nodo. Se ci sono molti più candidati rispetto al numero finito di risultati (10 qui) per un nodo, ci dovrebbe essere una funzione di classificazione per risolvere la competizione tra due risultati.
L'albero può essere costruito una volta ogni poche ore, a seconda del dinamismo dei dati.Se i dati sono in tempo reale, suppongo che qualche altro algoritmo fornirà un bilanciamento migliore. In questo caso, il requisito assoluto è il recupero rapido dei risultati per ogni battitura digitata che fa molto bene.
Ulteriori complicazioni sorgono se viene suggerita la correzione ortografica. In tal caso, dovranno essere considerati anche gli algoritmi di modifica della distanza.
Per piccoli set di dati come un elenco di paesi, una semplice implementazione di Trie lo farà. Se si intende implementare un elenco a discesa di tale completamento automatico in un'applicazione Web, il widget di completamento automatico di YUI3 eseguirà tutto per te dopo aver fornito i dati in un elenco. Se si utilizza YUI3 come solo frontend per un completamento automatico supportato da dati di grandi dimensioni, creare i servizi Web basati su TST in C++ e quindi utilizzare l'origine dati del nodo script del widget di completamento automatico per recuperare i dati dal servizio Web anziché da un elenco semplice.
Se volete suggerire i completamenti più popolari, un "Suggerisci albero" può essere una buona scelta: Suggest Tree
Segment trees può essere utilizzato per l'attuazione efficiente auto complete
in qualche modo correlato è la descrizione di Google Peter Norvig di come eseguire la correzione ortografica: http://norvig.com/spell-correct.html –
Un Trie standard richiede molta memoria, per set più grandi si desidera utilizzare un Trie compatto che riduce notevolmente l'ingombro della memoria. Ulteriori ottimizzazioni comprendono l'inizializzazione pigra dei valori del nodo e le giuste strutture dati per i bambini/set di valori. Qualche tempo fa ho creato una [libreria di autocompletamento] (https://github.com/fmmfonseca/completamente) in grado di gestire set di dati molto grandi (10.000.000+) e risponde in modo efficiente a ricerche esatte e approssimative. –