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:
  • 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 "&"


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
14867 views*
Posted at 05:14:35 | permalink | 8 comments | print
Do you like this article?
Subscribe to the RSS feed of this blog or use the newsletter service in order to receive a notification every time there is something of new to read here.

Note: you'll not see this box again if you are a usual reader.

Comments

riffraff writes:
10 May 07, 09:35:56
credo che pkzip/rar usino varianti di LZ77 come gzip, ma non ho fonti a sostegno della mia memoria :)
Per il resto: bell'articolo!
antirez writes:
10 May 07, 13:34:03
@riffraff: si hai ragione, LZMA (usato da RAR) somiglia di piu' a LZ77 che a LZW, anche Pkzip sembra utilizzare un algoritmo simile a DEFLATE. Grazie per la precisazione.
neon writes:
12 May 07, 13:39:53
Ricordo di aver conosciuto questi algoritmi (LZW ed LZSS) in un periodo in cui mi sono interessato al rom-hacking.

In molti giochi, sopratutto RPG (data la mole dei testi) utilizzano questo tipo di compressioni. Alcuni addirittura hanno creato delle varianti di questi formati. Square ad esempio non usava quasi mai una compressione standard.
antirez writes:
12 May 07, 14:04:47
@neon: tempo fa queste cose contavano davvero un po' per tutti i programmatori. Oggi invece c'e' un allontanamento preoccupante dalla "computer science" spicciola, algoritmi e strutture dati. Ma purtroppo questo allontanamento si riflette tantissimo sulla qualita' dei programmatori, che precipita.
Agorà writes:
07 Jul 08, 14:03:08
Mmm mi aspettavo anche una spiegazione sul perchè, in caso di sequenza CHAR STRING CHAR STRING CHAR, l'algoritmo non funziona e come si risolveil problema
Navigatore Anonimo writes:
08 Jan 09, 09:43:01
mi servirebbe anche l'algoritmo di decompressione.
Giulio writes:
17 Dec 09, 09:03:54
magari mi davate direttamente un sorgente che decomprime un file in PKZIP (per DOS) perche ha parole molte volte non basta a conoscere determinati dettagli, poi volevo chiedervi una cosa sul modo protetto 386: se si usa un selettore nullo per calcolare la base si prende GDT[0].base (che in alcuni programmi è diversa da 0) o avviene una eccezione? Grazie e Auguri a tutti da Giulio
Fabio Iotti writes:
17 Mar 11, 10:57:35
Nonostante questo articolo abbia già i suoi anni mi è stato utile, e per ricambiare, ecco a voi la versione in C++ (Dizionario di massimo 4096 stringhe!)...
http://tinyurl.com/LMZ-Compress

Ora aspetto l'algoritmo di decompressione...
comments closed