Deflate

Da Wikipedia, l'enciclopedia libera.

L'algoritmo Deflate è un algoritmo per la compressione dei dati 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 | modifica wikitesto]

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:

  • 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[modifica | modifica wikitesto]

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.