Dove posso trovare un algoritmo di compressione senza perdita di dati, che produce uscite senza intestazione?

Question

Qualcuno di voi conosce un algoritmo di compressione senza perdita di dati, che produce uscite senza intestazione? Per esempio non conservare l'albero di Huffman utilizzato per la compressione? Non parlo di alberi di Huffman hard coded, ma mi piacerebbe sapere se c'è qualche algoritmo in grado di comprimere e decomprimere in ingresso senza memorizzare alcuni metadati nella sua produzione. O è ancora teoricamente impossibile?

Answer 1

Adaptive codifica di Huffman fa esattamente questo. Più in generale, il termine adattativo codifica è usato per descrivere noreferrer codici entropia con questa proprietà. Alcuni href="http://en.wikipedia.org/wiki/Dictionary_coder" hanno questa proprietà anche, ad esempio, run-length encoding (RLE) e Lempel-Ziv-Welch (LZW) .

Answer 2

Certo che è posible. Tra gli altri, la famiglia LZ di compressori non hanno bisogno di uscita nulla a parte l'dati compressi in sé, come il dizionario è costruita on-line come la compressione (o decompressione) il progresso. Hai un sacco di implementazioni di riferimento per questi algoritmi LZ-tipo. Ad esempio, LZMA , componente del 7zip.

Answer 3

Run Length Encoding sarebbe un esempio

Answer 4

LZO viene in mente. è usato in OpenVPN, con ottimi risultati

Answer 5

Perché siete alla ricerca di algoritmi di compressione con uscita compressa senza intestazione?

Forse (a) si dispone di un sistema come la telefonia a 2 vie che ha bisogno di bassa latenza compressione streaming / decompressione. La categoria codifica adattativa di algoritmi di compressione menzionato da Zach Scrivena e la famiglia LZ di compressione dizionario algoritmi citati da Diego Sevilla e Javier sono eccellenti per questo tipo di applicazione. implementazioni pratiche di questi algoritmi di solito do avere un byte o due di metadati all'inizio (rendendoli inutili per (b) applicazioni), ma che ha poco o nessun effetto sulla latenza.

Forse (b) siete interessati principalmente in crittografia, e si sente che comprimere-prima-cifrare dà alcune proprietà di protezione migliorate, fino a quando il testo compresso non hanno fissato i metadati intestazione "culla". algoritmi di crittografia moderni non sono (per quanto ne sappiamo) vulnerabili a tali "presepi", ma se siete paranoici si potrebbero essere interessati a "Compressione bijective" ( un , b , c , ecc). Non è possibile rilevare errori di trasmissione (bit capovolto, bit inseriti, punte cancellate, ecc) quando un ricevitore riceve tale uscita compresso (rendendo questi algoritmi non particolarmente utili per (a) applicazioni).

Forse (c) siete interessati a compressione senza intestazione per qualche altro motivo. Suoni affascinante - qual è quella ragione