Sono un principiante in C++. Qualcuno può dirmi una migliore struttura dati in C++ per memorizzare tutte le parole in un dizionario e scoprire se una parola è presente nel dizionario. So che i tavoli hash sono i migliori ma non so quale struttura dati li utilizza?Miglior struttura dati in C++ per trovare una stringa in un dizionario
Grazie mille in anticipo.
La libreria standard dell'implementazione C++ può avere unordered_set o hash_set. Sono essenzialmente la stessa cosa; il primo fa parte del prossimo standard C++ 0x ed è supportato da alcuni degli ultimi compilatori, quest'ultimo è del SGI STL originale ed è incluso in molte implementazioni di librerie standard.
È una parte hash_set o unordered_set della libreria standard? – brett
@brett: 'hash_set': Ufficialmente? No. Ma molte implementazioni di libreria standard (incluso Visual C++ e libstdC++) lo includono. 'unordered_set': Non ancora. Farà parte della libreria standard quando C++ 0x è approvato nel 2011. Alcune implementazioni di libreria standard (ad es. La libreria Visual C++ 2010) lo includono. –
Posso usarlo nel mio compilatore linux? G ++? Se no qual è la migliore struttura dati? – brett
hash_map, se presente nella libreria del compilatore del C++ (ad es. GNU C++ o Microsoft Visual C++). Se stai utilizzando qualche altro compilatore meno diffuso, sospetto che tu possa trovare comunque un'implementazione decente di terze parti di hash_map.
Il prossimo standard C++ chiama invece la stessa struttura dati std::unordered_map.
Se non si desidera associare alcuna informazione con le parole del dizionario, basta registrare se una parola è presente o meno, è possibile utilizzare le variazioni _set (anziché _map) della struttura dati sopra riportata i nomi dei tipi.
Ovviamente, sono tutti modelli (come tutti i contenitori nella libreria standard C++), quindi è necessario istanziarli in modo appropriato con la tipica sintassi del modello.
Ma penso che andrà meglio con un set di parole, non con una mappa che è un contenitore chiave-valore associativo. Come ha detto James, qualsiasi implementazione di set dovrebbe essere sufficiente. –
@ Hernán, come ho detto, se ha solo bisogno delle informazioni di presenza/assenza, 'hash_set' o' unordered_set' sarà sufficiente - se ha mai bisogno di registrare qualsiasi informazione ausiliaria, allora le varianti di '..._ map' saranno essere migliore (e altrettanto efficiente). –
Se l'unico requisito è decidere se una parola è contenuta in un dizionario che non cambia mai, senza bisogno di alcun altro tipo di informazione sulla parola, (ad esempio, un correttore ortografico), allora Bloom filter è un efficiente struttura dati per questa attività.
Se ci sono altri dati da associare a ogni parola che deve essere cercata, std::map è un buon punto di partenza generale.
Se è necessario il completamento automatico (quando è stata immessa una parola parziale), è possibile utilizzare Prefix tree (trie).
Un filtro di fioritura è una struttura di dati probabilistica; non può darti una risposta Sì/No definitiva. I falsi positivi sono possibili, ma i falsi negativi non lo sono. Il trie è comunque una buona idea. –
Gli hash sono piuttosto buoni, ma la struttura migliore è un trie. Puoi ottenere un trie da <ext/pb_ds/assoc_container.hpp> in GCC. Vedi the online reference.
#include <ext/pb_ds/assoc_container.hpp>
#include <string>
#include <iostream>
int main() {
pb_ds::trie< std::string, int > dict;
dict.insert(std::make_pair("hello", 3));
std::cerr << (dict.find("hello") != dict.end()) << std::endl;
std::cerr << (dict.find("goodbye") != dict.end()) << std::endl;
}
Solo map funzionalità -come, non un puro set, è fornito. Nell'esempio sopra ho aggiunto un dummy int come dati da mappare a ... non dovrebbe fare molto male.
Ciò che fa male è che questo non funzionerà al di fuori di GCC.
D'altra parte, un non -standard tabella di hash (non std:: o ext:: nulla) consentirebbe di trovare solo corrispondenze approssimative, vale a dire da ricercare tra checksum di parole al posto delle parole stesse. Questa sarebbe la soluzione più veloce e più compatta. Dizionari basati su Bloom filters possono contenere molte migliaia di parole in pochi kilobyte.
Come mai non funziona al di fuori di GCC? Non c'è modo di importare queste librerie in Visual Studio (compilatore CL)? –
@YechielLabunskiy Il file è semplicemente incluso in GCC. Potrebbe funzionare in MSVC se non dipende da eventuali estensioni GCC o inciampare in errori MSVC. Vale sicuramente la pena di provarlo. Dovresti trattarlo come una libreria di terze parti separata e monitorarlo per gli aggiornamenti. – Potatoswatter
Se si è disposti a rollare la propria soluzione e il dizionario è stato risolto, un perfect hash è un buon modo per andare. Garantisce un tempo di ricerca costante.
Ho avuto questo esatto problema (generando dizionari fissi) un anno o due fa e sono rimasto deluso nel constatare che l'hashing perfetto richiede praticamente una struttura di dati a due livelli e quindi più letture di memoria per ricerca. Finisce per essere più lento di un semplice vecchio hash table con concatenamento. –
FWIW, ecco il codice che ho finito per scrivere la tabella: http://hg.mozilla.org/tracemonkey/file/e555673c8119/js/src/xpconnect/src/qsgen.py#l1488 e per sondarlo: http : //hg.mozilla.org/tracemonkey/file/e555673c8119/js/src/xpconnect/src/xpcquickstubs.cpp#l70 In pratica genera alcune catene di 3 voci lunghe (poche ricerche devono comunque superare qualsiasi catena) . –
Preferirei usare un Trie. Un Trie sarà una buona struttura dati per creare un dizionario efficiente in memoria con ricerche veloci e sì, completamento automatico.
Pensatelo come una tabella hash, che fornisce una rapida ricerca di coppie chiave-valore (o solo la ricerca di chiavi), ma a differenza di una tabella hash consente di scorrere le chiavi in ordine.
Si prega di fare riferimento a Trie - Wiki per ulteriori informazioni/riferimento.
Ci sono C++ DS forniti dalla libreria standard come mappe, set ecc. Quindi qual è il DS migliore per cercare una stringa. Leggerò tutte le stringhe e la ricerca. – brett