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. È 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 serie1: Ci sono altri blocchi dopo
- Bit-2/3: descrizione del metodo di codifica
00: Il blocco non è compresso01: Il blocco usa la codifica di Huffman con un albero prestabilito10: Il blocco usa la codifica di Huffman con un blocco proprio11: 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
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.
