DEFLATE

DEFLATE, letteralmente sgonare, è un algoritmo di compressione dati lossless che utilizza una variante del metodo di compressione LZ77 combinata con la codica di Human. Fu originariamente progettato da Philip Katz come parte del software PKZIP. DEFLATE è un metodo di compressione di dominio pubblico ed è quindi implementato in un gran numero di software come nella compressione dei les tramite gzip, il formato immagine PNG e il formato le ZIP per il quale venne appositamente studiato. Al ne di comprenderne il funzionamento, è necessario ricordare le metodologie di compressione dei due algoritmi che lo costituiscono.

Come abbiamo già visto, il codice di Human è un codice senza presso. Ogni parola di codice rappresenta un elemento in uno specico alfabeto. Ad ognuno degli elementi dell'alfabeto è assegnata una probabilità, un numero che rappresenta la frequenza relativa dell'elemento all'interno della stringa da comprimere. Tali probabilità possono essere ipotizzate senza conoscere il contenuto dei dati da comprimere o calcolate esattamente attraverso un'anal- isi dei dati, o addirittura attraverso una combinazione di entrambe queste modalità.

A partire da queste probabilità DEFLATE utilizza l'algoritmo di Human per costruire un albero di decodica, ed assegna ad ognuno degli elementi una sequenza binaria che rappresenta univocamente gli elementi.

2.9 DEFLATE 57 molti degli elementi del codice ASCII saranno esclusi dall'albero di Human, mentre i caratteri frequentemente utilizzati (come A, E, T...) saranno associati ai codici di minore lunghezza.

Nella classica codica di Human, un dato insieme di elementi con asso- ciate probabilità può generare molteplici alberi. Nella variazione utilizzata dal metodo standard DEFLATE, esistono due regole aggiuntive che inducono l'unicità dell'albero:

• gli elementi con i codici più corti devono essere posizionati alla sinistra (ramo 0) degli elementi con codici più lunghi;

• nel caso in cui due elementi abbiano la medesima lunghezza di codice, l'elemento che nell'alfabeto compare per primo deve essere posizionato alla sinistra (ramo 0) dell'elemento che compare per secondo.

Con queste due restrizioni, dato un insieme di elementi e le rispettive lunghezze dei codici ad essi associati, si ottiene un'unica possibilità di costruzione del- l'albero di Human. Al ne di permettere la ricostruzione dell'albero di Human sarà quindi necessario trasmettere al decodicatore solamente le lunghezze dei codici identicativi di ogni elemento.

DEFLATE eettua la codica di Human sulla stringa già codicata con l'algoritmo LZ77. Quest'ultimo ricerca sequenze di dati ripetute e, quando una sequenza di caratteri è identica a una sequenza che si trova all'interno della sliding window, la sostituisce da una coppia di interi, (distanza, lunghez- za), che rappresentano il numero dei caratteri da scorrere all'indietro per raggiungere il primo carattere della sequenza da copiare e la lunghezza della sequenza da copiare. DEFLATE utilizza una sliding window di 32Kbytes, ciò signica che la ricerca di ogni sequenza di caratteri viene eettuata negli ultimi 32 ∗ 1024 = 32768 caratteri comparsi nella stringa da codicare.

Il compressore DEFLATE è caratterizzato da una grande essibilità nella modalità di compressione dati. Deate ha infatti a disposizione tre diversi metodi per comprimere una sequenza:

1. Non eettuare la compressione: questa può essere una scelta intelli- gente quando, ad esempio, i dati sono già stati compressi. I dati memo- rizzati non compressi comporteranno una relativa espansione del codice. Tale espansione sarà comunque inferiore rispetto all'espansione che si avrebbe memorizzando dati già compressi in precedenza attraverso uno dei metodi che seguono.

2. Compressione LZ77 + Codica di Human statica: Gli alberi utiliz- zati per questa tipologia di compressione sono deniti all'interno dello

stesso algoritmo DEFLATE, non è quindi necessario inviare l'albero di Human con la stringa compressa.

3. Compressione LZ77 + Codica di Human adattiva: codica utilizzan- do alberi creati dal compressore a partire dalla stringa originale. Gli alberi devono essere memorizzati insieme alla stringa compressa. Una stringa compressa con DEFLATE è costituita da una successione di blocchi. Ogni blocco è preceduto da un codice di tre bits detto header che ne descrive le caratteristiche di compressione:

• bit 1: indicatore dell'ultimo blocco della stringa:

 1: il blocco è l'ultimo blocco che compone la stringa;  0: il blocco è seguito da ulteriori blocchi;

• bit 2-3: indicatore del metodo di codica utilizzato per comprimere il blocco:

 00: blocco non compresso;

 01: Il blocco usa la codica di Human statica con un albero prestabilito;

 10: Il blocco usa la codica di Human dinamica con albero adattato;

 11: riservato, comando non utilizzato.

La maggior parte dei blocchi saranno compressi con il metodo 10, codica di Human dinamica, che produce un albero di Human adattato (ottimizza- to) per ognuno dei singoli blocchi. Le istruzioni necessarie alla ricostruzione dell'albero di Human seguono immediatamente l'header. Gli alberi di Hu- man usati per un blocco sono indipendenti da quelli utilizzati per blocchi precedenti o successivi, mentre in LZ77 le sequenze ripetute possono riferirsi a sequenze di blocchi precedenti, cioè un puntatore di distanza può attraver- sare uno o più blocchi singoli, senza puntare ad una posizione che vada oltre l'inizio del usso di dati in input o oltre la dimensione della nestra. Inne, se un blocco presenta un alto tasso di entropia, l'algoritmo può decidere di non comprimerlo aatto.