Deflate

algoritmo di compressione dati

Deflate (stilizzato come DEFLATE) è un algoritmo per la compressione dati senza perdita che è stato introdotto dal programma PKZIP, e quindi formalizzato nella RFC 1951. È tuttora ampiamente utilizzato per le sue ottime prestazioni e l'assenza di brevetti.

Descrizione

modifica

L'algoritmo di Deflate opera su blocchi di dati con dimensione massima di 64KB. Ogni blocco viene preceduto da un header di 3 bit:

  • Bit-1: marcatore per l'ultimo blocco
    • 0: Il blocco è l'ultimo della serie
    • 1: Ci sono altri blocchi dopo
  • Bit-2/3: descrizione del metodo di codifica
    • 00: Il blocco non è compresso
    • 01: Il blocco usa la codifica di Huffman con un albero prestabilito
    • 10: Il blocco usa la codifica di Huffman con un blocco proprio
    • 11: Riservato

La maggior parte dei blocchi userà la codifica di Huffman con un albero proprio, sebbene in presenza di un alto livello di entropia l'algoritmo possa decidere di non comprimere affatto il blocco. In presenza di un blocco che utilizza un albero proprio, le istruzioni per costruire l'albero seguono l'header.

La compressione si suddivide in 2 stadi:

Differenze con l'algoritmo LZ77

modifica

Per quanto riguarda la variante di LZW, essa consiste nel non costruire esplicitamente il dizionario, ma nell'usare invece dei puntatori all'indietro per specificare che una determinata sotto-stringa di ingresso, è in realtà la ripetizione di un'altra già osservata in precedenza. In questo caso, anziché emettere il codice (di Huffman) associato al byte corrente, si emette (il codice di Hamming del) la lunghezza della stringa da copiare, e la distanza (nel passato) della stessa. Quindi in pratica, anziché usare una codeword di lunghezza fissa per indicizzare gli elementi del dizionario come per LZW, si usa un puntatore di lunghezza variabile, privilegiando le copie della sottostringa corrente più prossime nel tempo, oppure quelle con un maggior numero di caratteri uguali.

Voci correlate

modifica
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica