Formati di compressione con un buon supporto per l'accesso casuale all'interno degli archivi?

https://stackoverflow.com/questions/429987

07-07-2019
|

Domanda

È simile a una domanda precedente , ma le risposte non soddisfano le mie esigenze e la mia domanda è leggermente diversa :

Attualmente uso la compressione gzip per alcuni file molto grandi che contengono dati ordinati. Quando i file non sono compressi, la ricerca binaria è un modo pratico ed efficiente per supportare la ricerca di una posizione nei dati ordinati.

Ma quando i file sono compressi, le cose si complicano. Di recente ho scoperto l'opzione zlib , che può essere utilizzata durante la compressione per inserire " punti di sincronizzazione " nell'output compresso (Z_FULL_FLUSH può quindi iniziare la lettura da vari punti del file). Va bene, anche se i file che ho già dovrebbero essere ricompressi per aggiungere questa funzione (e stranamente inflateSync() non ha un'opzione per questo, ma sono disposto a scrivere il mio programma di compressione se necessario).

Sembra da una fonte che anche gzip non è una soluzione perfetta ... non solo non è supportato da tutti gli archivi gzip, ma l'idea stessa di rilevare i punti di sincronizzazione negli archivi può produrre falsi positivi (o in coincidenza con il numero magico per i punti di sincronizzazione, oppure a causa del fatto che Z_SYNC_FLUSH produce anche punti di sincronizzazione ma non sono utilizzabili per l'accesso casuale).

C'è una soluzione migliore? Vorrei evitare di avere file ausiliari per l'indicizzazione, se possibile, e sarebbe esplicito il supporto predefinito esplicito per l'accesso quasi casuale (anche se è a grana grossa, come essere in grado di iniziare a leggere ad ogni intervallo di 10 MB). Esiste un altro formato di compressione con un supporto migliore per letture casuali di gzip?

Modifica : come ho già detto, desidero fare una ricerca binaria nei dati compressi. Non ho bisogno di cercare una posizione specifica (non compressa) - solo per cercare con una certa granularità all'interno del file compresso. Voglio solo supporto per qualcosa come & Quot; Decomprimi i dati a partire da circa il 50% (25%, 12,5%, ecc.) Del percorso in questo file compresso. & Quot;

Soluzione

Non conosco alcun formato di file compresso che supporti l'accesso casuale a una posizione specifica nei dati non compressi (beh, ad eccezione dei formati multimediali), ma puoi crearne uno tuo.

Ad esempio, i file compressi bzip2 sono composti da blocchi compressi indipendenti di dimensioni < 1 MB non compressi, che sono delimitati da sequenze di byte magici, quindi è possibile analizzare il file bzip2, ottenere i limiti del blocco e quindi decomprimere il blocco giusto. Ciò richiederebbe qualche indicizzazione per ricordare da dove iniziano i blocchi.

Tuttavia, penso che la soluzione migliore sarebbe quella di dividere il tuo file in blocchi di tua scelta, e quindi comprimerlo con qualche archiviatore, come zip o rar, che supporta l'accesso casuale ai singoli file nell'archivio.

Altri suggerimenti

Dai un'occhiata a dictzip . È compatibile con gzip e consente un accesso casuale approssimativo.

Un estratto dalla sua pagina man:

dictzip comprime i file utilizzando l'algoritmo gzip (1) (LZ77) in un modo che è completamente compatibile con il formato di file gzip. Un'estensione al gzip il formato file (Campo extra, descritto nel 2.3.1.1 della RFC 1952) consente dati extra da archiviare nell'intestazione di un file compresso. Programmi come gzip e zcat ignorerà questi dati extra. Tuttavia, [dictzcat --start] farà uso di questi dati per eseguire l'accesso pseudo-casuale sul file.

Ho il pacchetto dictzip in Ubuntu. Oppure il suo codice sorgente è in dictd - *. Tar.gz . La sua licenza è GPL. Sei libero di studiarlo.

Aggiornamento:

Ho migliorato dictzip per non avere limiti di dimensione del file. La mia implementazione è sotto licenza MIT.

Il formato di file .xz (che utilizza la compressione LZMA) sembra supportare questo:

Lettura ad accesso casuale : i dati possono essere suddivisi in blocchi compressi in modo indipendente. Ogni file .xz contiene un indice dei blocchi, il che rende possibile una lettura limitata ad accesso casuale quando la dimensione del blocco è abbastanza piccola.

Questo dovrebbe essere sufficiente per il tuo scopo. Uno svantaggio è che l'API di liblzma (per interagire con questi contenitori) non sembra ben documentata, quindi potrebbe richiedere qualche sforzo per capire come accedere ai blocchi in modo casuale.

Esistono soluzioni per fornire accesso casuale agli archivi gzip e bzip2:

gzip zran. c dal codice sorgente di ghostscript
bzip2 seek-bzip di James Taylor

( Sto cercando qualcosa per 7zip )

bgzip può comprimere i file in una variante gzip che è indicizzabile (e può essere decompresso da tabix). Questo è usato in alcune applicazioni bioinformatiche, insieme all'indicizzatore <=>.

Vedi le spiegazioni qui: http: // blastedbio .blogspot.fr / 2011/11 / bgzf-block-larger-better-gzip.html , e qui: http://www.htslib.org/doc/tabix.html .

Non so fino a che punto sia adattabile ad altre applicazioni.

Non sono sicuro se questo sarebbe pratico nella tua situazione esatta, ma non potresti semplicemente decomprimere ogni file di grandi dimensioni in file più piccoli, diciamo 10 MB ciascuno? Si finirebbe con un mucchio di file: file0.gz, file1.gz, file2.gz, ecc. In base a un dato offset all'interno del grande originale, è possibile cercare nel file denominato "file" + (offset / 10485760) + ".gz". L'offset all'interno dell'archivio non compresso sarebbe offset % 10485760.

Poiché la compressione senza perdita di dati funziona meglio su alcune aree rispetto ad altre, se memorizzi i dati compressi in blocchi di BLOCKSIZE di lunghezza conveniente, anche se ogni blocco ha esattamente lo stesso numero di byte compressi, alcuni blocchi compressi si espandono in un testo molto più lungo di altri.

Potresti guardare " Compressione: una chiave per i sistemi di recupero del testo di prossima generazione " di Nivio Ziviani, Edleno Silva de Moura, Gonzalo Navarro e Ricardo Baeza-Yates nel Computer rivista novembre 2000 http://doi.ieeecomputersociety.org/10.1109/2.881693

Il loro decompressore accetta 1, 2 o 3 byte interi di dati compressi e decomprime (usando un elenco di vocaboli) in una parola intera. Si può cercare direttamente nel testo compresso parole o frasi, che risulta essere anche più veloce della ricerca di testo non compresso.

Il loro decompressore ti consente di indicare qualsiasi parola nel testo con un normale puntatore (byte) e iniziare a decomprimere immediatamente da quel punto.

Puoi dare a ogni parola un codice univoco di 2 byte, poiché probabilmente hai meno di 65.000 parole uniche nel tuo testo. (Ci sono quasi 13.000 parole uniche nella Bibbia di KJV). Anche se ci sono più di 65.000 parole, è abbastanza semplice assegnare il primo codice a due byte 256 & Quot; parole & Quot; a tutti i possibili byte, in modo da poter compitare le parole che non sono nel lessico del 65.000 circa " parole e frasi più frequenti " ;. (La compressione ottenuta impacchettando parole e frasi frequenti in due byte di solito vale " espansione " di scrivere occasionalmente una parola usando due byte per lettera). Esistono diversi modi per scegliere un lessico di & Quot; parole e frasi frequenti & Quot; ciò darà una compressione adeguata. Ad esempio, è possibile modificare un compressore LZW per scaricare & Quot; frasi & Quot; utilizza più di una volta in un file lessico, una riga per frase, ed eseguilo su tutti i tuoi dati. Oppure potresti tagliare arbitrariamente i tuoi dati non compressi in frasi a 5 byte in un file lessico, una riga per frase. Oppure potresti tagliare i tuoi dati non compressi in parole inglesi effettive e inserire ogni parola, incluso lo spazio all'inizio della parola, nel file lessico. Quindi utilizzare & Quot; sort --unique & Quot; per eliminare le parole duplicate in quel file lessico. (La scelta del & Quot perfetto; & Quot; elenco di parole del lessico è ancora considerato NP-difficile?)

Memorizza il lessico all'inizio del tuo enorme file compresso, riempilo con un comodo BLOCKSIZE, quindi archivia il testo compresso - una serie di due byte " parole " - da lì alla fine del file. Presumibilmente il ricercatore leggerà questo lessico una volta e lo manterrà in un formato a decodifica rapida nella RAM durante la decompressione, per accelerare la decompressione & Quot; codice a due byte & Quot; a " frase a lunghezza variabile " ;. La mia prima bozza inizierebbe con un semplice elenco di una riga per frase, ma in seguito potresti passare alla memorizzazione del lessico in una forma più compressa usando una sorta di codifica incrementale o zlib.

Puoi selezionare qualsiasi offset di byte pari casuale nel testo compresso e iniziare a decomprimerlo da lì. Non credo sia possibile creare un formato di file compresso ad accesso casuale a grana fine.

Due possibili soluzioni:

Consenti al sistema operativo di gestire la compressione, creare e montare un file system compresso (SquashFS, clicfs, cloop, cramfs, e2compr o altro) contenente tutti i tuoi file di testo e non fare nulla per la compressione nel tuo programma applicativo .
Usa clicfs direttamente su ogni file di testo (un clic per file di testo) invece di comprimere un'immagine del filesystem. Pensa a & Quot; mkclicfs mytextfile mycompressedfile & Quot; essendo " gzip < mytextfile > mycompressedfile " e " clicfs mycompressedfile directory " come modo per ottenere un accesso casuale ai dati tramite il file "directory/mytextfile".

Non so se sia stato ancora menzionato, ma il progetto Kiwix ha fatto un ottimo lavoro in questo senso. Attraverso il loro programma Kiwix, offrono un accesso casuale agli archivi di file ZIM. Buona anche la compressione. Il progetto è nato quando c'era una richiesta di copie offline di Wikipedia (che ha superato i 100 GB in forma non compressa, con tutti i media inclusi). Hanno preso con successo un file da 25 GB (una forma di realizzazione di file singolo di Wikipedia senza la maggior parte dei media) e lo hanno compresso in un misero archivio di file zim da 8 GB. E attraverso il programma Kiwix, puoi richiamare qualsiasi pagina di Wikipedia, con tutti i dati associati, più velocemente di quanto puoi navigare in rete.

Anche se il programma Kiwix è una tecnologia basata sulla struttura del database di wikipedia, dimostra che puoi avere eccellenti rapporti di compressione e accesso casuale contemporaneamente.

Questa è una domanda molto vecchia ma sembra che zindex potrebbe fornire una buona soluzione (anche se non non ne ho molta esperienza)

razip supporta l'accesso casuale con prestazioni migliori rispetto a gzip / bzip2 che devono essere ottimizzate per questo supporto - riducendo la compressione a spese di " ok " accesso casuale:

http://sourceforge.net/projects/razip/

Sono l'autore di uno strumento open source per la compressione di un particolare tipo di dati biologici. Questo strumento, chiamato starch, divide i dati per cromosoma e utilizza tali divisioni come indici per un rapido accesso alle unità di dati compresse all'interno dell'archivio più grande.

I dati per cromosoma vengono trasformati per rimuovere la ridondanza nelle coordinate genomiche e i dati trasformati vengono compressi con algoritmi bzip2 o gzip. Gli offset, i metadati e i dati genomici compressi sono concatenati in un unico file.

Il codice sorgente è disponibile dal nostro GitHub . Lo abbiamo compilato sotto Linux e Mac OS X.

Nel tuo caso, puoi archiviare (10 MB o qualsiasi altra cosa) gli offset in un'intestazione in un formato di archivio personalizzato. Analizza l'intestazione, recuperi gli offset e incrementalmente fseek attraverso il file di current_offset_sum + header_size.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow