C++ È necessario confrontare una stringa con 200.000 parole

Nel mio programma in C++ ...C++ È necessario confrontare una stringa con 200.000 parole

Tipi di utente nella stringa di programma "foo".

Ho bisogno di confrontare questa stringa alle mie stringhe, in file txt scrivere: questa stringa è un nome! (o aggettivo ...)

Ho pochi file TXT: un file con nomi, file 2-nd con aggettivi ... ma in ogni file è di circa 200.000 parole.

Come posso effettivamente confrontare questa stringa "pippo" con le stringhe nei miei file?

Cosa devo usare?

fonte

2010-02-28 Kate83

È questo compito? Si prega di taggare come tale se lo è. –

No, non è compito a casa, è una domanda. – Kate83

Che ne dici di un vero database? Le "specifiche" che hai fornito sembrano essere piuttosto incomplete, nel migliore dei casi ... – none

Metti le tue parole nei contenitori std::set<std::string> e fai una ricerca su di loro. Questo dà O (log n) tempo per un accesso, che è probabilmente sufficiente per quello che stai facendo.

È inoltre possibile utilizzare std::map<std::string, std::string> dove la chiave è la parola e il valore è la classe (ad esempio "nome").

fonte

2010-02-28 19:14:28 Tronic

Come pensi, leggere circa 200.000 x 2 parole in contenitori sarà veloce? – Kate83

@Kate: sì. 200k non è niente. –

std :: map e std :: set sono altamente ottimizzati per la ricerca per chiave (possono utilizzare, ad esempio, un albero di ricerca rosso-nero internamente), quando si utilizza c.find (chiave). Saranno necessari solo pochi confronti per trovare il nodo corretto. – Tronic

Hai solo bisogno di confermare se corrisponde a qualcosa?

In tal caso, utilizzare un Trie.

fonte

2010-02-28 19:14:36 Soraz

Devo dire all'utente che la sua parola è un sostantivo, un aggettivo ... o un programma non so quale sia quella parola. – Kate83

Quindi utilizzare due tentativi, uno per i nomi e uno per gli aggettivi. – MSalters

Utilizzare la struttura dati TRIE per questo. Dovresti aver bisogno di un po 'di memoria per costruire la struttura dei dati. Ma il tuo obiettivo sarà più efficiente.

fonte

2010-02-28 19:15:17 bragboy

Grazie, proverò questo 1-st :) – Kate83

OMG TRIE è geniale. Purtroppo, questo è qualcosa che ho potuto reinventare se premuto abbastanza forte per questo. –

L'ho reinventato nel 1996 in C. Il diff di velocità mi ha tolto i calzini (il PC era un 486). Molto bello È stato scritto per la prima volta alla fine degli anni '60, credo. Non sapevo che fosse una vera struttura fino a quando non sono diventato monopolizzato qualche anno fa. Se si tratta di compiti a casa, impressioneresti davvero l'insegnante più delle funzioni integrate. Se funziona, i tuoi colleghi ti prenderanno in giro per perdere tempo a reinventare la ruota! – FastAl

Si consiglia di utilizzare sqlite per i file invece.

È possibile creare un CRC di ciascuno dei valori chiave e memorizzare la chiave e i valori (int) in una tabella. Creare un indice per il campo chiave.

Quando si desidera eseguire una ricerca, è possibile prendere il CRC della parola e effettuare una ricerca nella tabella.

fonte

2010-02-28 19:19:45

La creazione CRC per ogni parola 1-1? In caso contrario, le chiavi potrebbero scontrarsi? – bragboy

@Bragaadees Con solo 200.000 chiavi avresti maggiori probabilità di vincere alla lotteria. Potresti anche usare crc-8 se lo volessi. Puoi selezionare tutto e fare il confronto delle stringhe se 2 corrisponde, ma 2 probabilmente non corrisponderebbero mai. –

Cattiva idea. Con CRC-32, le collisioni di compleanno sono probabilmente di 2^16 = 65536 chiavi. Con 200.000 chiavi, una collisione è quasi garantita. Sì, la possibilità di qualsiasi coppia si scontra è solo 1 su 4 miliardi, ma ci sono 40.000.000.000 coppie di chiavi. – MSalters

A Radix tree un utilizzo di memoria migliore per le stringhe rispetto a un trie "normale" se si hanno molte stringhe con radici/prefissi comuni (che è probabilmente il caso di un dizionario cioè parole con molte forme - anche se questo sarebbe probabilmente dipende dalla lingua).

fonte

2010-03-01 04:44:04

È possibile memorizzare il file esterno indicizzato come btree o come hash concatenato, in quanto fornisce tempi di ricerca molto rapidi e ricerche minime per individuare i dati.

fonte

2010-03-01 14:11:49 anijhaw

C++ È necessario confrontare una stringa con 200.000 parole

risposta

Problemi correlati