Deflate

Da Wikipedia, l'enciclopedia libera.

[modifica] Storia

E' un metodo di compressione dati che introdotto dal programma PKZIP da Phil Katz, e quindi formalizzato nella RFC 1951, e tuttora ampiamente utilizzato per le sue ottime prestazioni e l'assenza di brevetti.

[modifica] Descrizione

Usa una variante dell'algoritmo LZW, al cui risultato applica poi una codifica di Huffman. Deflate opera su blocchi di dati con dimensione massima 64Kbyte, ognuno dei quali può essere replicato intatto (come nel caso in cui i bit siano già sufficientemente impredicibili), oppure essere compresso con un codice di Huffman statico, oppure ancora dinamico.

[modifica] Funzionamento

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 LWZ, si usa un puntatore di lunghezza variabile, privilegiando le copie della sottostriga corrente più prossime nel tempo, oppure quelle con un maggior numero di caratteri uguali.