Accesso casuale ai pacchetti di dati in un file compresso

Gli schemi di compressione basati su LZ si basano sul trovare ed eliminare stringhe di caratteri ripetute. Mentre comprimono un flusso, creano un dizionario di stringhe che sono state incontrate, così quando viene ritrovata la stessa stringa, trasmettono la posizione di quella stringa nel dizionario invece di ritrasmettere l'intera stringa.

In un caso tipico, i primi kilobyte di dati in realtà si espandono un po ', perché il dizionario inizia (essenzialmente ¹ ) vuoto. Solo dopo che alcuni kilobyte sono stati scansionati e le stringhe sono state aggiunte al dizionario, inizierai a ottenere molta compressione.

Per fare in modo che un tale algoritmo funzioni in modo decente su dati orientati alla registrazione, probabilmente si desidera raggruppare i record in blocchi di, ad esempio, qualcosa come 64K ciascuno. La lettura di un record sarà una procedura in due fasi. Per prima cosa troverai il blocco che contiene il record, lo leggi in memoria e decomprime l'intero blocco. Quindi troverai il record che ti interessa in quei dati decompressi.

La dimensione del blocco selezionata è un compromesso tra efficienza di compressione ed efficienza di accesso casuale. Un blocco più grande generalmente migliora la compressione, ma (ovviamente abbastanza) richiede di leggere più dati per ottenere i record in un blocco. Una dimensione di blocco più piccola riduce i dati aggiuntivi che è necessario leggere per ottenere un determinato record, ma riduce anche la compressione.

Se sei disposto a eseguire manualmente la compressione, puoi fare le cose in modo diverso. L'idea generale sarebbe quella di scansionare una grande quantità di dati per costruire un dizionario (approssimativamente simile a LZ) di stringhe ripetute, ma non fare la compressione al volo come fa LZ. Invece, memorizzare il dizionario (separatamente dai dati). Dopo aver analizzato tutti i dati, utilizzare il dizionario completo per comprimere i dati. Ciò richiede di memorizzare il dizionario (che utilizza un po 'di spazio) ma consente di averlo pre-compilato quando si decomprimono i dati. Questo riduce la penalità per la compressione di ogni record separatamente, quindi quando leggi i dati dovrai solo leggere un record (più le parti associate del dizionario - ma quando è in uso, probabilmente avrai la maggior parte del dizionario nella RAM la maggior parte del tempo).

¹ In alcune implementazioni, il dizionario inizia inizializzato con le voci per i 256 valori di byte possibili, ma questo risulta ancora in espansione - ognuna di quelle stringhe di un carattere è rappresentata nel bit-stream con un codice (minimo di) a 9 bit. In altri casi, quelle voci del dizionario sono "virtuali" - ciascuna viene considerata presente nella posizione corretta nel dizionario, ma mai effettivamente memorizzata.

Se hai a che fare con pacchetti ben definiti, allora la risposta deve essere che sì questo è tutto possibile.

Suggerirei: - il file contiene 2 tipi di informazioni: un indice e un record di dati - i record di dati sono compressi - Gli indici puntano a record di dati o un nuovo indice

Gli indici devono essere estensibili in modo che quando si cresce un file aggiungendo più record è possibile creare e aggiungere un nuovo indice se necessario.

Questo potrebbe essere tutto racchiuso in un'API abbastanza carina.

Se si desidera comprimere i record di dati, suggerirei di guardare 7-zip, sembra avere un'interfaccia COM o simile, e si comprime meglio del semplice zip.

Qualcosa da tenere a mente è che quando si ha a che fare con file di grandi dimensioni, è possibile che si ottenga una compressione di gran lunga migliore dell'intero file, rispetto alla compressione individuale dei record. Questo perché la maggior parte di questi algoritmi di compressione si basa sul rilevamento di pattern ripetuti in un file e, se ci sono informazioni ripetute su tutti i record, questo si riduce molto bene. Un singolo record potrebbe non avere molte informazioni ripetute e quindi potrebbe anche non comprimere.

Molto dipende dal tipo di file con cui si ha a che fare e dalla loro struttura interna.

Esiste un motivo logico / strutturale per i file che sono così grandi come sono?

Quanto sono interconnessi i dati all'interno di ciascun file?

È probabile che una volta che inizi a leggere, finirai la lettura a livello locale o ti ritroverai a saltare intorno al file per terminare la lettura?

Partendo dal presupposto che le tue letture sono per lo più locali e relativamente piccole, un algoritmo di compressione LZ modificato dovrebbe fare il trucco. Puoi eseguire il rollover o utilizzare uno degli esempi disponibili sul Web e ottenere una compressione abbastanza decente pur consentendo l'accesso casuale.

Se hai a che fare con architetture e contenuti più complessi, dovrai essere più creativo. Potresti voler analizzare i contenuti di ciascun file e quindi archiviarli in un database che viene fornito con algoritmi di compressione incorporati, come Oracle, ad esempio, poiché può farti risparmiare grattacapi.

Potresti considerare di andare da una direzione diversa. Che ne dici di memorizzare i file su un'unità compressa? Saranno accessibili come file normali, ma occuperanno meno spazio sulle unità.