antirez weblog

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.

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.

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:

• Primo step, l'algoritmo inizializza i primi 256 simboli della tabella (dall'inidice 0 all'indice 255 dunque) con il valore dei singoli byte da 0 a 255. Per cui l'elemento alla posizione 65 sara' la lettera "A" se il nostro computer utilizza il sistema ASCII (come praticamente tutti ai nostri giorni), mentre la "M" sara' alla posizione 77 e cosi' via.

Finita la fase di inizializzazione si entra nel vivo dell'algoritmo.

• Si legge il primo carattere dall'input, la M nel nostro esempio
• Si aggiunge tale carattere ad una variabile che chiamiamo STRINGA CORRENTE, che ha lo scopo di accumulare la parte di testo piu' lunga possibile per cui si riesce a trovare una corrispondenza.
• Ora STRINGA CORRENTE contiene "M"
• Si cerca la corrispondenza di STRINGA CORRENTE (ovvero "M") nella tabella e la trova all'indice 77
• Si preleva il carattere successivo, "A", e lo si accoda alla STRINGA CORRENTE come al solito
• Ora STRINGA CORRENTE contiene "MA"
• Si cerca la corrispondenza di STRINGA CORRENTE, ovvero "MA", ma NON e' presente nella tabella! Nella nostra tabella ci sono solo i 256 simboli che descrivono ogni possibile carattere del codice ASCI (in generale ogni possibile singolo byte).
• Quando una corrispondenza non viene trovata e' chiaro che la piu' lunga stringa che e' presente attualmente nella tabella e' STRINGA CORRENTE (che vale "MA") senza il suo ultimo carattere, ovvero la stringa "M" (poiche' si aggiunge un carattere alla volta solo se la stringa corrente fino a quel punto ha una corrispondenza). Chiamiamo questa stringa per cui c'e' una corrispondenza STRINGA PRESENTE, e il carattere in eccesso semplicemente ULTIMO CARATTERE.
• Si emette come output l'indice della tabella a cui e' possibile trovare STRINGA PRESENTE (che contiene "M"), ovvero 77.
• STRINGA CORRENTE, ovvero "MA", viene ora inserito nella tabella, in quanto si tratta di un simbolo sconosciuto. Siccome i primi 256 posti sono gia' occupati (da 0 a 255), il nuovo simbolo avra' indice 256 e sara' il 257esimo elemento della tabella.
• Viene assegnato ULTIMO CARATTERE a STRINGA CORRENTE, che dunque ora vale solo "A"

E il processo continua

• Viene letto il prossimo carattere, "M". STRINGA CORRENTE ora vale "AM"
• Non esiste nella tabella, per cui viene emesso il codice di "A" (STRINGA PRESENTE), ovvero 65, (dunque il nostro output fino ad ora e' 77,65), "AM" prende posto nella tabella alla posizione 257, STRINGA CORRENTE vale ora "M"

Prossimo carattere, ma sta volta la compressione inizia a farsi viva

• Viene letto il prossimo carattere, "A". STRINGA CORRENTE ora vale "MA"
• Esiste nella tabella!, indice 256, viene letto il prossimo carattere, "&".
• Ora STRINGA CORRENTE vale "MA&"
• Non esiste nella tabella, dunque si emette il codice per STRINGA PRESENTE che e' 256, e STRINGA CORRENTE viene settata al valore di "&"

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. 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