Compressione per un flusso unico di dati

Question

Ho un gran numero di array interi. Ognuno contiene alcune migliaia di numeri interi e ogni numero intero è generalmente uguale a quello precedente o è diverso solo per un singolo bit o due. Vorrei ridurre ogni array il più piccolo possibile per ridurre l'IO del mio disco.

Zlib lo riduce a circa il 25% delle dimensioni originali. È carino, ma non credo che il suo algoritmo sia particolarmente adatto al problema. Qualcuno conosce una libreria di compressione o un semplice algoritmo che potrebbe funzionare meglio per questo tipo di informazioni?

Aggiornamento: zlib dopo averlo convertito in un array di xor delta lo riduce a circa il 20% delle dimensioni originali.

Answer 1

Se la maggior parte degli interi è davvero la stessa della precedente e la differenza tra simboli può di solito essere espressa come un singolo capovolgimento di bit, questo sembra un lavoro per XOR.

Prendi uno stream di input come:

1101
1101
1110
1110
0110

e output:

1101
0000
0010
0000
1000

un po 'di pseudo codice

compressed[0] = uncompressed[0]
loop
  compressed[i] = uncompressed[i-1] ^ uncompressed[i]

Ora abbiamo ridotto la maggior parte dell'output a 0, anche quando viene modificato un bit alto. La compressione RLE in qualsiasi altro strumento che usi avrà una giornata campale con questo. Funzionerà ancora meglio su numeri interi a 32 bit e può ancora codificare un numero intero radicalmente diverso spuntando nel flusso. Ti sei risparmiato il fastidio di occuparti di impacchettare te stesso, poiché tutto rimane una quantità di dimensioni int.

Quando vuoi decomprimere:

uncompressed[0] = compressed[0]
loop
  uncompressed[i] = uncompressed[i-1] ^ compressed[i]

Questo ha anche il vantaggio di essere un semplice algoritmo che verrà eseguito molto, molto velocemente, dato che è solo XOR.

Answer 2

Hai considerato Codifica run-length ?

Oppure prova questo: invece di memorizzare i numeri stessi, memorizzi le differenze tra i numeri. 1 1 2 2 2 3 5 diventa 1 0 1 0 0 1 2. Ora la maggior parte dei numeri che devi codificare sono molto piccoli. Per memorizzare un numero intero piccolo, utilizza un numero intero a 8 bit anziché quello a 32 bit che codificherai sulla maggior parte delle piattaforme. Questo è un fattore 4 proprio lì. Se devi essere preparato per spazi più grandi di quello, designa il bit alto dell'intero a 8 bit per dire "questo numero richiede anche i successivi 8 bit".

Puoi combinarlo con la codifica run-length per rapporti di compressione ancora migliori, a seconda dei tuoi dati.

Nessuna di queste opzioni è particolarmente difficile da implementare e funzionano tutte molto velocemente e con pochissima memoria (al contrario, diciamo, bzip).

Answer 3

Desideri preelaborare i tuoi dati, trasformandoli in modo reversibile in una forma più adatta al tuo metodo di compressione dei dati back-end, per prima cosa. I dettagli dipenderanno sia dal metodo di compressione back-end, sia (più criticamente) dalle proprietà che ti aspetti dai dati che stai comprimendo.

Nel tuo caso, zlib è un metodo di compressione basato sul byte, ma i tuoi dati arrivano in numeri interi (32-bit?). Non è necessario reimplementare te stesso zlib, ma è necessario leggere come funziona, in modo da poter capire come presentarlo con dati facilmente comprimibili o se è appropriato per i tuoi scopi.

Zlib implementa una forma di codifica Lempel-Ziv. JPG e molti altri usano la codifica Huffman per il loro backend. La codifica run-length è popolare per molti usi ad hoc. Ecc., Ecc ...

Answer 4

Forse la risposta è pre-filtrare le matrici in modo analogo a Filtro utilizzato per creare piccole immagini PNG . Ecco alcune idee sulla cima della mia testa. Non ho provato questi approcci, ma se hai voglia di giocare, potrebbero essere interessanti.

1. Suddividi i tuoi in ciascuno in 4 byte, quindi i ₀ , i ₁ , i ₂ , ..., i _n diventa b _0,0 , b _0,1 , b _0,2 , b _0,3 , b _1,0 , b _1,1 , b _1,2 , b _{1, 3} , ..., b _{n, 0} , b _{n, 1} , b _{n, 2} , b _{n, 3} . Quindi scrivi tutti i _{i, 0} s, seguiti dai b _{i, 1} s, b _{i, 2} s, e b < sub> i, 3 ?? s. Se la maggior parte delle volte i tuoi numeri differiscono solo di un paio di bit, dovresti ottenere delle lunghe sequenze di byte ripetuti, che dovrebbero comprimersi davvero bene usando qualcosa come la codifica di lunghezza di esecuzione o zlib. Questo è il mio preferito dei metodi che presento.

2. Se i numeri interi in ciascun array sono strettamente correlati a quello precedente, potresti forse memorizzare il numero intero originale, seguito da differenze rispetto alla voce precedente - questo dovrebbe fornire un insieme più piccolo di valori da cui attingere, che in genere risulta in una forma più compressa.

3. Se i vari bit differiscono, è possibile che si verifichino differenze sostanziali, ma se è più probabile che si abbiano differenze numeriche elevate che corrispondono (di solito) a uno o due bit diversi, si potrebbe stare meglio con uno schema in cui si crea un array ahebyte: utilizzare i primi 4 byte per codificare il primo intero, quindi per ogni voce successiva, utilizzare 0 o più byte per indicare quali bit devono essere capovolti, memorizzando 0, 1, 2, ..., o 31 nel byte, con una sentinella (diciamo 32) per indicare quando hai finito. Ciò potrebbe comportare il numero non elaborato di byte necessari per rappresentare in media un numero intero vicino a 2, che la maggior parte dei byte proviene da un set limitato (0 - 32). Esegui quel flusso attraverso zlib e forse rimarrai piacevolmente sorpreso.

Answer 5

Hai provato bzip2 per questo? http://bzip.org/

Per me ha sempre funzionato meglio di zlib.

Answer 6

Poiché la tua preoccupazione è ridurre l'IO del disco, ti consigliamo di comprimere ogni array intero in modo indipendente, senza fare riferimento ad altri array interi.

Una tecnica comune per il tuo scenario è quella di memorizzare le differenze, poiché un piccolo numero di differenze può essere codificato con parole chiave brevi. Sembra che tu debba inventare il tuo schema di codifica per le differenze, dal momento che sono differenze multi-bit, forse usando un byte a 8 bit qualcosa come questo come punto di partenza:

• 1 bit per indicare che segue un nuovo intero completo o che questo byte codifica una differenza dall'ultimo intero,
• 1 bit per indicare che ci sono più byte seguenti, registrando più differenze a singolo bit per lo stesso numero intero.
• 6 bit per registrare il numero di bit per passare dal numero intero precedente.

Se ci sono più di 4 bit diversi, quindi memorizzare l'intero.

Questo schema potrebbe non essere appropriato se hai anche molti codici completamente diversi, poiché ora impiegheranno 5 byte ciascuno invece di 4.

Answer 7

"Zlib lo riduce di un fattore di circa 4x." significa che un file di 100K ora occupa negativo 300K; è abbastanza impressionante da qualsiasi definizione :-). Suppongo che intendi che lo riduce del 75%, ovvero a 1/4 della sua dimensione originale.

Una possibilità per una compressione ottimizzata è la seguente (presuppone un numero intero a 32 bit e al massimo 3 bit che cambiano da elemento a elemento).

• Emette il primo numero intero (32 bit).
• Emette il numero di cambi di bit (n = 0-3, 2 bit).
• Output n bit specificatori (0-31, 5 bit ciascuno).

Il caso peggiore per questa compressione è una variazione di 3 bit in ogni numero intero (2 + 5 + 5 + 5 bit) che tenderà a 17/32 delle dimensioni originali (compressione 46.875%).

Dico che "tende verso" poiché il primo intero è sempre 32 bit ma, per qualsiasi array di dimensioni decenti, quel primo intero sarebbe trascurabile.

Il caso migliore è un file di numeri interi identici (nessuna variazione di bit per ogni numero intero, solo i 2 zero bit) - questo tenderà verso 2/32 delle dimensioni originali (compressione del 93,75%).

Dove in media 2 bit diversi per numero intero consecutivo (come dici tu è il tuo caso comune), otterrai 2 + 5 + 5 bit per numero intero che tenderà verso una compressione del 12/32 o del 62,5%.

Il tuo punto di pareggio (se zlib fornisce una compressione del 75%) è di 8 bit per intero che sarebbe

• modifiche a singolo bit (2 + 5 = 7 bit): 80% delle transizioni.
• modifiche a doppio bit (2 + 5 + 5 = 12 bit): 20% delle transizioni.

Ciò significa che la tua media dovrebbe essere una modifica di 1,2 bit per numero intero per renderlo utile.

Una cosa che suggerirei di guardare è 7zip: questa ha una licenza molto liberale e puoi collegarla al tuo codice (penso che anche la fonte sia disponibile).

Ho notato (comunque per le mie cose) che funziona molto meglio di WinZip su una piattaforma Windows, quindi potrebbe anche superare zlib.