Se ci sono poche stringhe univoche sufficienti per adattarsi alla memoria, usa solo Dictionary<string, uint> dove la chiave è la stringa e il valore il suo conteggio.
Se le stringhe univoche non si adattano alla memoria, è possibile utilizzare un filtro bloom come la struttura dati in cui si memorizza un contatore per ciascun hash anziché un bit per ogni hash. Compilalo in un primo passaggio sui dati. Quindi ogni stringa con un numero sufficiente di occorrenze avrà il contatore per tutti gli hash associati oltre la soglia (100 nel tuo caso). Nel secondo passaggio, usa l'approccio del dizionario di conteggio, ma solo su stringhe che non vengono eliminate dal filtro di fioritura.
.. so maybe 7 bytes on average for the word and 4 bytes to store the count, that's at least 11 bytes per word but maybe i am forgetting things so let's double = 20 bytes. 20 byes * 3 billion records = 60 billion bytes or 56 GB
Se sei preoccupato per l'archiviazione, allora in linea di principio un Trie (o trie) è un buon modo per memorizzare il set corrente di stringhe e ampli; conta. Il fatto che sia effettivamente utile dipende dal fatto che ci sia abbastanza ridondanza di prefissi nelle stringhe per superare quella extra di pulizia.
Indipendentemente dal contenitore utilizzato per il set di lavoro corrente, tieni presente che sono necessari solo 16 bit ( uint16_t ) per rappresentare i conteggi fino a 100k, che è tutto ciò che serve. Quando una stringa raggiunge un conteggio di 100k, aggiungi ad un filtro di fioritura di stringhe che già sappiamo ignorare . Nota che hai ancora bisogno di una copia della stringa da qualche parte poiché i filtri di fioritura producono corrispondenze false positive.
L'elaborazione della stringa diventa qualcosa come
if (probably_ignored(s) && // quick bloom filter check
definitely_ignored(s)) // slow check to exact string
{
return;
}
uint16_t *count = get_or_add(s); // lookup or insert in working set
if (99999 == *count) {
ignore(s); // remove from working set, add to bloom filter etc.
}
++ *count;
Vale anche la pena notare che il tuo contenitore può essere più piccolo se il set di caratteri è ridotto. Ad esempio, se non hai bisogno di maiuscole / minuscole o di caratteri non stampabili o di cifre, tutto ciò che puoi eliminare può ridurre i requisiti di archiviazione.
La variante di conteggio BloomFilter proposta da @CodesInChaos dovrebbe funzionare bene, è necessario scegliere da vicino l'algoritmo di hash, è probabile che ci siano collisioni che potrebbero distorcere i risultati. È possibile utilizzare 2-3 diversi hash per creare una singola chiave su cui contare.
Un approccio più semplice e brutale in cui è possibile utilizzare un database, un semplice embeded dovrebbe fare il trucco (SQlite, berkely db ecc.). Archiviare le stringhe e un contatore, quindi interrogare per ottenere quelli in cui sei stato interrotto, quindi eliminare tutto il database nel caso in cui non sia necessario. La RAM è costosa, ma è necessario disporre di spazio su disco. Tuttavia, sarà un po 'più lento in fase di esecuzione rispetto a un approccio interamente in memoria. Detto questo, devi comunque leggere le stringhe dal disco quindi tutto sommato non dovrebbe aggiungere un sovraccarico, specialmente se le stringhe si ripetono spesso, il database alla fine dovrebbe essere molto più piccolo del set di dati originale . Nel peggiore dei casi sarà lo spazio per tutte le stringhe + un int + piccolo overhead del database.
Infine, le tue stime (56 GB) sono nel peggiore dei casi, che sarà effettivamente il caso se tutte le tue stringhe sono diverse. ma qualcosa mi dice che i dati effettivi memorizzati saranno molto meno, darei la soluzione di mappa semplice morta prima. Memorizzare la stringa come chiave e contatore e scorrere. La cosa peggiore che succederà è che la tua app riempirà la ram e andrà in crash. Se funziona, ottieni la tua risposta con una dozzina di loc. Almeno avresti un'idea di come appaiono i dati.
---- Modifica Idea Flash, potresti finalmente concatenare le stringhe con un separatore e utilizzare l'algoritmo di ricerca delle stringhe sul tutto. Abbastanza frequente approccio nella ricerca di modelli genetici in cui il set di dati può diventare grande come si descrive Controlla la ricerca Z-Box link oppure il classico link del classico Boyer-Moore entrambi i quali ho provato in passato con un certo successo per problemi simili.
Approccio 1: A causa delle dimensioni del set di dati, tenterei di rompere il set se possibile.
Supponiamo che tu abbia attualmente un singolo file original.txt Il mio primo pensiero sarebbe una sorta di benna in nuovi file per prima lettera / carattere nella stringa. Se i file in questo set di risultati sono ancora troppo grandi per essere conservati in memoria, eseguirò l'iterazione su ciascun file nello stesso modo utilizzando il secondo carattere. Ripeti questo approccio finché i tuoi file non saranno gestibili. Se le stringhe sono distribuite regolarmente e solo alfabeticamente, dopo il terzo passaggio scendi a 170687 stringhe per file.
Questo approccio potrebbe anche usare una HashMap nidificata complessa e credo che Java sarebbe in grado di memorizzare nella cache le parti più profonde e impedire di avere l'intero set in memoria in una volta. (Potrei essere tragicamente sbagliato da quella parte però)
Metodo 2: utilizza un database
metti tutti i dati in un'unica tabella indicizzata sulla stringa in questione e poi puoi usare
Select count(*),your_string from your_table group by your_string;
E potresti liberarti delle stringhe meno comuni con qualcosa di simile
delete from your_table
where your_string in (
Select count(*),your_string from your_table
group by your_string
having (count(*) < 100 or count(*) > 100000;
Approccio 3: Hashmap < Stringa, frequenza > impedisce la ripetizione dei dati in memoria
Leggi altre domande sui tag data-structures strings