Quali sono alcune alternative a un array di bit?

Question

Ho un'applicazione di recupero delle informazioni che crea array di bit dell'ordine di decine di milioni di bit.Il numero di bit "impostati" nell'array varia ampiamente, da tutti azzerati a tutti impostati.Attualmente sto utilizzando un semplice array di bit (java.util.BitSet), quindi ciascuno dei miei array di bit occupa diversi megabyte.

Il mio piano è quello di esaminare la cardinalità del primo N bit, quindi decidere quale struttura dati utilizzare per il resto.Chiaramente alcune strutture dati sono migliori per array di bit molto sparsi e altre quando sono impostati circa la metà dei bit (quando la maggior parte dei bit è impostata, posso usare la negazione per trattarli come un insieme sparso di zeri).

• Quali strutture potrebbero essere buone a ciascun estremo?
• Ce ne sono nel mezzo?

Ecco alcuni vincoli o suggerimenti:

1. I bit vengono impostati una sola volta e in ordine di indice.
2. Ho bisogno di una precisione del 100%, quindi qualcosa come un filtro Bloom non è abbastanza buono.
3. Dopo aver creato il set, devo essere in grado di scorrere in modo efficiente i bit "set".
4. I bit sono distribuiti in modo casuale, quindi è probabile che gli algoritmi di codifica della lunghezza di esecuzione non siano molto migliori di un semplice elenco di indici di bit.
5. Sto cercando di ottimizzare l'utilizzo della memoria, ma la velocità è ancora valida Alcuni peso.

Qualcosa con un'implementazione Java open source è utile, ma non strettamente necessario.Mi interessano di più i fondamentali.

Answer 1

A meno che i dati non siano veramente casuali E ha una distribuzione simmetrica 1/0, questo diventa semplicemente un problema di compressione dei dati senza perdita ed è molto analogo alla compressione CCITT Gruppo 3 utilizzata per il bianco e nero (ovvero:Binario) Immagini FAX.CCITT Gruppo 3 utilizza uno schema di codifica Huffman.Nel caso del FAX viene utilizzato un set fisso di codici Huffman, ma per un dato set di dati è possibile generare un set specifico di codici per ciascun set di dati per migliorare il rapporto di compressione ottenuto.Finché devi accedere ai bit solo in sequenza, come hai lasciato intendere, questo sarà un approccio abbastanza efficiente.L'accesso casuale creerebbe alcune sfide aggiuntive, ma probabilmente potresti generare un indice dell'albero di ricerca binario su vari punti di offset nell'array che ti consentirebbe di avvicinarti alla posizione desiderata e quindi entrare da lì.

Nota:Lo schema di Huffman funziona ancora bene anche se i dati sono casuali, purché la distribuzione 1/0 non sia perfettamente uniforme.Cioè, minore è la distribuzione, migliore è il rapporto di compressione.

Infine, se i bit sono veramente casuali con una distribuzione uniforme, allora beh, secondo Sig.Claude Shannon, non sarai in grado di comprimerlo in modo significativo utilizzando alcuno schema.

Answer 2

Prenderei fortemente in considerazione l'utilizzo della codifica range al posto della codifica Huffman.In generale, la codifica a intervalli può sfruttare l'asimmetria in modo più efficace rispetto alla codifica di Huffman, ma ciò è particolarmente vero quando la dimensione dell'alfabeto è così piccola.In effetti, quando l '"alfabeto nativo" è semplicemente 0 e 1, l'unico modo in cui Huffman può ottenere una compressione è combinando quei simboli, che è esattamente ciò che farà la codifica dell'intervallo, in modo più efficace.

Answer 3

Forse è troppo tardi per te, ma esiste una libreria molto veloce ed efficiente in termini di memoria per array di bit sparsi (senza perdita di dati) e altri tipi di dati basati sui tentativi.Guarda a Judy si schiera

Answer 4

Grazie per le risposteQuesto è ciò che proverò per scegliere dinamicamente il metodo giusto:

Raccoglierò tutti i primi N risultati in un array di bit convenzionale e scegli uno dei tre metodi, in base alla simmetria di questo esempio.

• Se il campione è altamente asimmetrico, memorizzerò semplicemente gli indici ai bit impostati (o forse alla distanza dal bit successivo) in un elenco.
• Se il campione è altamente simmetrico, continuerò a usare un array di bit convenzionale.
• Se il campione è moderatamente simmetrico, userò un metodo di compressione senza perdita come Huffman Coding suggerito da Inscitekjeff.

I confini tra le regioni asimmetriche, moderate e simmetriche dipenderanno dal tempo richiesto dai vari algoritmi bilanciati rispetto allo spazio di cui hanno bisogno, dove il valore relativo del tempo rispetto allo spazio sarebbe un parametro regolabile.Lo spazio necessario per la codifica di Huffman è una funzione della simmetria e ne definirò il profilo con i test.Inoltre, testerò tutti e tre i metodi per determinare i requisiti di tempo della mia implementazione.

È possibile (e in realtà lo spero) che il metodo di compressione centrale sia sempre migliore dell'elenco o dell'array di bit o di entrambi.Forse posso incoraggiare questo scegliendo una serie di codici di Huffman adattati per una simmetria superiore o inferiore.Quindi posso semplificare il sistema e utilizzare solo due metodi.

Answer 5

Un altro pensiero di compressione:

Se l'array di bit non è molto lungo, potresti provare ad applicare il file Trasformata di Burrows-Wheeler prima di utilizzare qualsiasi codifica di ripetizione, come Huffman.Un'implementazione ingenua richiederebbe memoria O (n ^ 2) durante la (de) compressione e tempo O (n ^ 2 log n) per la decompressione - ci sono quasi certamente anche delle scorciatoie da avere.Ma se c'è qualche struttura sequenziale nei tuoi dati, questo dovrebbe davvero aiutare la codifica di Huffman.

Potresti anche applicare questa idea a un blocco alla volta per mantenere più pratico l'utilizzo del tempo/della memoria.L'uso di un blocco alla volta potrebbe consentirti di mantenere sempre compressa la maggior parte della struttura dei dati se stai leggendo/scrivendo in sequenza.

Answer 6

La compressione senza perdite diretta è la strada da percorrere.Per renderlo ricercabile dovrai comprimere blocchi relativamente piccoli e creare un indice in un array di blocchi.Questo indice può contenere l'offset del bit iniziale in ciascun blocco.

Answer 7

Prova combinatoria rapida che non puoi davvero risparmiare molto spazio:

Supponiamo di avere un sottoinsieme arbitrario di n/2 bit impostato su 1 su n bit totali.Hai (n scegli n/2) possibilità.Utilizzando La formula di Stirling, questo è all'incirca 2^n / sqrt(n) * sqrt(2/pi).Se ogni possibilità è ugualmente probabile, allora non c'è modo di dare alle scelte più probabili rappresentazioni più brevi.Quindi abbiamo bisogno di log_2 (n scegli n/2) bit, che equivale a circa n - (1/2)log(n) bit.

Non è un ottimo risparmio di memoria.Ad esempio, se lavori con n=2^20 (1 mega), puoi salvare solo circa 10 bit.Non ne vale la pena.

Detto questo, sembra anche molto improbabile che i dati veramente utili siano veramente casuali.Nel caso in cui ci sia più struttura nei tuoi dati, probabilmente c'è una risposta più ottimistica.