bisogno di memoria modo efficiente per archiviare tonnellate di stringhe (era: implementazione HAT-Trie in java)

Question

sto lavorando con un ampio set (5-20 milioni di euro) di chiavi String (durata media 10 caratteri) che ho bisogno di memorizzare in un a struttura di dati di memoria che supporta la seguente operazione in tempo costante o quasi in tempo costante:

// Returns true if the input is present in the container, false otherwise 
public boolean contains(String input) 

hashmap di Java sta dimostrando di essere più che soddisfacente per quanto riguarda il throughput è interessato, ma sta prendendo un sacco di memoria. Sto cercando una soluzione che sia efficiente in termini di memoria e supporti ancora un throughput che sia accettabile (paragonabile o quasi all'altezza dell'hashing).

Non mi importa dei tempi di inserimento/cancellazione. Nella mia applicazione, eseguirò solo gli inserimenti (solo al momento dell'avvio) e successivamente eseguirò una query sulla struttura dei dati solo utilizzando il metodo contains per la durata dell'applicazione.

Ho letto che la struttura dati HAT-Trie è la più vicina alle mie esigenze. Mi chiedo se esiste una libreria che ha un'implementazione.

Altri suggerimenti con indicazioni per implementazioni benvenute.

Grazie.

Answer 1

Il trie sembra un'ottima idea per i vostri limiti.

A "pensare fuori dagli schemi" alternativo:

se lo può permettere una certa probabilità di rispondere "presente" per una stringa che è assente

EDIT: se lo può permettere falsi positivi, utilizzare un Bloom filter come suggerito da WizardOfOdds nei commenti.

Per k = 1, un filtro Bloom è come una tabella hash senza le chiavi: ogni "bucket" è semplicemente un valore booleano che indica se almeno un input con lo stesso hash era presente. Se i falsi positivi dell'1% sono accettabili, la tabella hash può essere piccola come circa 100 * 20 milioni di bit o circa 200 MiB. Per 1 su 1000 falsi positivi, 2GiB.

L'utilizzo di diverse funzioni di hash anziché di uno può migliorare il tasso di falsi positivi per la stessa quantità di bit.

Answer 2

Per l'efficienza dello spazio, ricerca O (log (n)) e codice semplice, provare la ricerca binaria su una matrice di caratteri. 20 milioni di chiavi di lunghezza media 10 rendono 200 milioni di caratteri: 400 MB se hai bisogno di 2 byte/carattere; 200 MB se riesci a farla franca 1. In cima a questo devi in ​​qualche modo rappresentare i confini tra i tasti dell'array. Se puoi prenotare un carattere separatore, questo è un modo; altrimenti potresti usare un array parallelo di offset int.

La variante più semplice utilizza una serie di stringhe, a un costo di spazio elevato dall'overhead per oggetto. Dovrebbe ancora battere un hashtable nell'efficienza dello spazio, anche se non altrettanto.

Answer 3

Google visualizza un post sul blog HAT tries in Java. Ma non vedo come questo risolverà il problema direttamente: la struttura è un trie superficiale rispetto ai prefissi dei tasti, con le foglie che sono hashtables che contengono i suffissi di tutte le chiavi con il prefisso specificato. Quindi, in totale, hai un sacco di hashtables che memorizzano tutte le chiavi che sono nel tuo attuale hashtable (magari salvando alcuni byte per chiave in generale a causa dei prefissi comuni). Ad ogni modo, hai bisogno di un hash più efficiente in termini di spazio rispetto a quello predefinito di Java, o il sovraccarico per oggetto ti colpirà altrettanto male.Quindi, perché non iniziare con una classe hashtable specializzata solo per le chiavi stringa, se segui questa strada e ti preoccupi della parte trie solo se sembra ancora utile?

Answer 4

Simile a un trie è un albero di ricerca ternario, ma un albero di ricerca ternario ha il vantaggio di utilizzare meno memoria. È possibile leggere sugli alberi di ricerca ternaria here, here e here. Anche uno dei principali articoli sull'argomento di Jon Bentley e Robert Sedgewick è here. Parla anche di ordinare le stringhe rapidamente, quindi non lasciatevi scoraggiare da quello.