Deflate

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

Descrizione

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 albero 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:

• Nel primo viene usata una variante dell'algoritmo LZ77 per sostituire le stringhe duplicate con dei puntatori;
• Nel secondo il blocco viene codificato, se necessario, con la codifica di Huffman.

Differenze con l'algoritmo LZ77

L'algoritmo di sostituzione delle stringhe duplicate è LZW, una variante di LZ77, e consiste nel non costruire esplicitamente il dizionario, ma nell'utilizzare dei puntatori all'indietro per indicare che una determinata sottostringa è in realtà la ripetizione di un'altra sottostringa già osservata in precedenza. In tal caso, anziché emettere il codice di Huffman associato alla sottostringa corrente, si emette il codice di Hamming della lunghezza della sua lunghezza, e la distanza (nel passato) dalla sua copia già osservata. Quindi in pratica, anziché usare una codeword di lunghezza fissa per indicizzare gli elementi del dizionario come fa LZ77, 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

• Compressione dei dati

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