La compressione LZW

Thursday, 10 May 07
Formazione di rocce che sono state soggette a compressione Si puo' discutere per cercare di capire se l'informatica sia piu' arte o scienza, ma e' innegabile che nell'informatica il concetto di bellezza esiste a tutti i livelli: dagli algoritmi al codice sorgente, alle interfacce grafiche, ai singoli software stessi quando hanno quell'equilibrio tra funzionalita' e intuitivita'.

L'oggetto di questo articolo e' l'algoritmo di compressione LZW, che nella sua semplicita' e potenza rientra sicuramente nei miei canoni di bellezza degli algoritmi e rappresenta una pietra miliare nella storia degli algoritmi di compressione. In poche righe di codice e in alcuni concetti chiave si opera la magia della compressione dei file. Lo standard GIF e la utility di compressione dei sistemi UNIX coompress usata prima dell'avvento di gzip, cosi' come RAR e Pkzip, utilizzano LZW o una sua variante.

Conoscere LZW ha un risvolto importante, non ci possiamo sentire appieno programmatori considerando la compressione come qualcosa che piu' o meno capiamo ma che in realta' in concreto ci appare non del tutto chiara! LZW, (cosi' come la codifica di Huffman) e' cosi' semplice e pratico che la sua comprensione ci permette di apprezzare e dominare il concetto di compressione ad un livello piu' tangibile. Dopo la lettura di questo articolo sarete capaci di implementare a memoria un programma di compressione da zero basandovi solo sul ricordo del funzionamento di LZW e se conoscete la codifica di Huffmann utilizzando le due tecniche assieme potete raggiungere livelli di compressione simili a quelli di gzip.
Nel passato LZW e' stato afflitto dal fatto che sulle sue spalle gravavano troppi brevetti (qualcuno ricordera' i problemi con lo standard GIF che hanno generato il formato PNG per risposta). Finalmente i brevetti che coprivano LZW sono scaduti negli Stati Uniti e in Europa, per cui ormai questo algoritmo puo' essere usato liberamente per qualunque scopo.

L'idea di base

Se volessimo comprimere dei messaggi SMS cosi' da permettere il superamento del limite fisso di 160 caratteri potremmo pensare di assegnare un numero di 16 bit (ovvero un numero da 0 a 65535) ad ognuno dei termini che vengono scritti con piu' frequenza. 16 bit occupano due caratteri di spazio, meno della parola media, e un vocabolario con piu' di sessantacinquemila termini dovrebbe coprire una buona parte di un mesaggio medio. In generale l'idea di avere una tabella che mappa pezzi di stringhe che sono contenuti con alte probabilita' nel testo che vogliamo comprimere a numeri (gli indici della tabella: 0,1,2, ...) e' un sistema di compressione che sfrutta la ridondanza nei messaggi per permetterne la compressione.
Un tale sistema ha pero' un grande limite, la tabella e' specializzata per comprimere un determinato tipo di dati, tentare di comprimere una immagine con una tabella che contiene delle parole (buona per comprimere testi) sarebbe un fallimento completo e il file risultante sarebbe piu' grande di quello non compresso. La soluzione di LZW e' quella di creare la tabella in maniera adattiva, e renderla anche implicita nella fase di decompressione in modo da non doverla allegare all'output (ovvero al file compresso, tipicamente).


Descrizione dell'algoritmo

Per quanto LZW sia semplice e' bene fare degli esempi di compressione su stringhe reali, per tale ragione utilizzeremo la seguente stringa volutamente ridondante:
MAMA&MA&MA&M
Per questo esempio immaginiamo inoltre di utilizzare LZW con una tabella di 4096 simboli (che richiedono dunque 12 bit di output per ogni simbolo, poiche' 2 elevato a 12 fa 4096). Ecco cosa accade: Finita la fase di inizializzazione si entra nel vivo dell'algoritmo. E il processo continua Prossimo carattere, ma sta volta la compressione inizia a farsi viva

Quando abbiamo emesso un solo codice per "MA" abbiamo usato usato soltanto 12 bit per encodare due caratteri (che di solito ne necessitano 16)! Dunque siamo riusciti a comprimere. Provate a seguire passo passo grazie alla tabella di seguito tutto il processo di compressione della nostra stringa di esempio ripartendo dall'inizio:


NUOVO CARATTERE   STRINGA CORRENTE   OUTPUT   NUOVO ELEMENTO IN TABELLA
M                 M
A                 MA                 77       256="MA"
M                 AM                 65       257="AM"
A                 MA
&                 MA&                256      258="MA&"
M                 &M                 38       259="&M"
A                 MA
&                 MA&
M                 MA&M               258      260="MA&M"
A                 MA
&                 MA&
M                 MA&M
(fine file)       MA&M               260
L'output finale sara' dunque costituito dalla sequenza di sei codici seguente:
77,65,256,38,258,260
che a 12 bit ognuno occupano 72 bit, contro i 96 che sarebbero stati necessari senza compressione per registrare 12 caratteri di 8 bit ognuno.
L'esempio e' stato scelto apposta per mostrare compressione da subito ma in realta' nella pratica le cose iniziano a funzionare dopo un centinaio di caratteri. Con stringhe piu' corte e' probabile che otterrete un output piu' lungo invece che piu' corto dell'input.
Lasciamo per le conclusioni tutti i possibili discorsi sul quanto comprime, cosa fare se la tabella si riempie, e su quale sia la dimensione ottimale di questa, e passiamo alla decompressione. Infatti l'idea piu' importante di tutto l'algoritmo e' che durante la decompressione e' possibile ricostruire di pari passo la tabella per come la si era creata durante la compressione, per cui non e' necessario allegare nessuna tabella nell'output, semplice mente i codici dei simboli emessi.

Questo articolo pero' e' gia' troppo lungo, arrivederci a tra qualche giorno con un nuovo post in cui analizzeremo la decompressione passo dopo passo come abbiamo fatto per la compressione, e il piccolo tranello che nasconde.

Vi lascio con l'algoritmo di compressione in pseudo codice, a presto con il resto di LZW :)

COMPRESSIONE_LZW(INPUT):
    STRINGA_CORRENTE = ""
    TABELLA[da 0 a 255] = byte da 0 a 255
    per ogni carattere C dell'INPUT:
        STRINGA_CORRENTE = STRINGA_CORRENTE + C
        SE STRINGA_CORRENTE NON e' presente in TABELLA:
            STRINGA_PRESENTE = STRINGA_CORRENTE - ULTIMO CARATTERE
            CODICE = Indice di STRINGA_PRESENTE in TABELLA
            EMETTI CODICE come output
            TABELLA = TABELLA + STRINGA_CORRENTE
            STRINGA_CORRENTE = C
            ... continua il ciclo col prossimo carattere ...
    CODICE = Indice di STRINGA_CORRENTE in TABELLA
    EMETTI CODICE come output
11733 views*
Posted at 09:14:35 | permalink | 8 comments | print