In informatica, LZW è il nome di un algoritmo per la compressione dati senza perdita di informazioni (lossless). Tale tecnica, ad esempio, è utilizzata nella codifica delle immagini in formato GIF e, facoltativamente, nei file TIFF.

Alcuni vantaggi della compressione LZW sono:

La facilità di implementazione
L'applicabilità a qualsiasi tipo di dati (testo, immagini, suoni, ecc...)

Tuttavia è da sottolineare che il fattore di compressione spesso risulta essere non molto elevato, proprio per la genericità dell'algoritmo.

Storia modifica

Presentato^[1] da Welch nel 1984, l'algoritmo si basa su precedenti ricerche effettuate da Jacob Ziv ed Abraham Lempel.
Questi ultimi, infatti, pubblicarono nel 1977 un documento sulla compressione "sliding-window" (a finestre scorrevoli), seguito poi nel 1978 da un'altra ricerca relativa alla compressione basata su "dizionari".
I due algoritmi furono chiamati, rispettivamente, LZ77 ed LZ78. Nel 1984, Terry Welch migliorò LZ78 dando origine all'algoritmo conosciuto oggi come LZW (acronimo di Lempel-Ziv-Welch).

Concetto di base modifica

Premesse modifica

L'input dell'algoritmo di compressione (encoder) e di decompressione (decoder) è costituito da una sequenza finita di simboli (stringa), appartenenti ad un insieme detto alfabeto.
Come esempio, immaginiamo di voler archiviare una sequenza di DNA.
In generale, una parte di DNA è composta da una sequenza (finita) di 4 tipi di acidi: Adenina, Timina, Citosina e Guanina.
L'alfabeto, sulla quale è costruita una sequenza di DNA, è l'insieme:

\sum =\{A,C,G,T\}

Una stringa sull'alfabeto $\sum$ è costituita da una qualunque sequenza finita di A, C, G e T, ad esempio:

"ACGTACGTACG"

(in realtà non tutte le stringhe così costruite sono valide, infatti esistono alcune "regole" per la combinazione degli acidi, qui ignorate per semplificare la trattazione).

La quantità di memoria necessaria per archiviare una stringa è proporzionale al numero di simboli di cui è composta.
Comprimere una stringa, quindi, significa esprimere la stessa informazione impiegando un numero inferiore di simboli.

Descrizione LZW modifica

Molto spesso la stringa in input contiene alcune parti (sotto-stringhe), che si ripetono più volte all'interno della stessa.
Ad esempio, esaminando la stringa precedente, possiamo evidenziare le seguenti ripetizioni:

ACGTACGTACG

(si noti che non esiste un unico modo di scegliere le sotto-stringhe ripetute)

L'idea centrale dell'algoritmo LZW è sfruttare la presenza di queste ripetizioni per la compressione. E' ovvio che tale algoritmo avrà prestazioni differenti in base ai dati in input, e che in generale è più adatto nella compressione di file testuali. Man mano che viene esaminata la stringa in input, vengono automaticamente determinate ed inserite in un dizionario le sotto-stringhe che si ripetono. A ciascuna sotto-stringa verrà associato un nuovo simbolo che non appartiene all'alfabeto iniziale.
Quest'ultimo viene quindi esteso con dei simboli speciali, ognuno dei quali rappresenta una particolare sottostringa.

Nell'esempio precedente è possibile individuare due sequenze che si ripetono:

AG
GT

Queste due sottostringhe saranno "rilevate" dall'algoritmo, che provvederà ad inserirle nel dizionario e ad associargli due nuovi simboli:

Dizionario
Sequenza	Simbolo
AC	$\alpha _{1}$
GT	$\alpha _{2}$

Le nuove voci vengono aggiunte a quelle già presenti nel dizionario, estendendolo man mano che si avanza con l'elaborazione dell'input.
Rimpiazzando le sequenze ripetute con i nuovi simboli, otteniamo il seguente risultato:

\alpha _{1}

\alpha _{2}

\alpha _{1}

\alpha _{2}

\alpha _{1}

G

La nuova stringa è costruita su un'estensione dell'alfabeto iniziale, precisamente:

\sum =\{A,C,G,T,\alpha _{1},\alpha _{2}\}

L'output della compressione è costituito solamente dalla stringa codificata (il dizionario non viene memorizzato). Questo perchè la scelta delle sotto-stringhe da inserire nel dizionario avviene secondo criteri ben precisi, che permettono la ricostruzione dello stesso a partire dai dati compressi.

L'input dell'algoritmo di decompressione (decoder) è perciò una stringa costituita dai dati (simboli A, C, G, T) e da codici speciali (simboli $\alpha _{1}$ , $\alpha _{2}$ ). Compito della decompressione è quello di ricostruire la stringa originale elaborando i dati codificati.
Nelle successive voci viene discusso in dettaglio l'elaborazione dell'input nella fase di compressione (detta anche fase di encoding) e di decompressione (decoding).

Compressione modifica

Come primo passo nel dizionario vengono inseriti tutti i simboli dell'alfabeto, utilizzando gli stessi come codici speciali.
Nell'esempio il dizionario iniziale è così composto:

Dizionario
Sequenza	Codice
A	A
C	C
G	G
T	T

L'algoritmo, per determinare le voci da inserire nel dizionario, utilizza una stringa a parte (d'ora in avanti chiamata buffer) che verrà modificata/cancellata più volte durante l'esecuzione. Inizialmente il buffer è vuoto (cioè non contiene alcun simbolo).

La stringa inizia ad essere esaminata dal primo simbolo; nel buffer vengono collezionati i vari caratteri incontrati, fino a che non si formi una sequenza non contenuta nel dizionario. Nel nostro esempio,

"ACGTACGTACG"

si hanno i seguenti passaggi (in giallo viene evidenziata la parte contenuta nel buffer):
(per una migliore lettura: ogni riga descrive lo stato dell'algortimo prima che venga eseguita la relativa iterazione)

Iterazione	Input	Buffer corrente	Simbolo in output	Voce aggiunta nel dizionario
1	ACGTACGTACG	(vuoto)	(nessuno)	(nessuna)
2	ACGTACGTACG	A
3	ACGTACGTACG	AC

A questo punto il buffer contiene una sequenza non presente nel dizionario. Quando verrà eseguita la terza iterazione, verranno effettuati i seguenti passi:

Del buffer (che non è contenuto nel dizionario) vengono considerati tutti i simboli tranne l'ultimo (ottenendo A). Si noti che così facendo si ottiene una stringa contenuta nel dizionario.
Questa sottostringa del buffer (A) viene cercata nel dizionario, mandando in output il codice associato (che in questo caso coincide con A)
L'intero buffer (AC) viene inserito come nuova voce del dizionario, associandogli un nuovo simbolo ( $\alpha _{1}$ ).
Il buffer viene rimpiazzato con il suo ultimo carattere (in questo caso da AC diventa C)

A questo punto la scansione riprende dal simbolo successivo (ossia dal terzo). Di seguito è riportata la tabella con i vari passi eseguiti dall'algoritmo:

Iterazione	Input	Buffer corrente	Simbolo in output	Voce aggiunta nel dizionario
4	ACGTACGTACG	C	A	AC (( $\alpha _{1}$ ))
5	ACGTACGTACG	CG
6	ACGTACGTACG	G	C	CG (( $\alpha _{2}$ ))
7	ACGTACGTACG	GT
8	ACGTACGTACG	T	G	GT (( $\alpha _{3}$ ))
9	ACGTACGTACG	TA
10	ACGTACGTACG	A	T	TA (( $\alpha _{4}$ ))

Dizionario
Sequenza	Codice
A	A
C	C
G	G
T	T
AC	$\alpha _{1}$
CG	$\alpha _{2}$
GT	$\alpha _{3}$
TA	$\alpha _{4}$

Con l'avanzare dell'elaborazione, all'interno del dizionario saranno disponibili sequenze sempre più lunghe, rappresentabili in output con un singolo simbolo. Continuando ad eseguire l'algoritmo si hanno i seguenti passaggi:

Iterazione	Input	Buffer corrente	Simbolo in output	Voce aggiunta nel dizionario
11	ACGTACGTACG	AC
12	ACGTACGTACG	ACG
13	ACGTACGTACG	G	$\alpha _{1}$	ACG (( $\alpha _{5}$ ))
14	ACGTACGTACG	GT
15	ACGTACGTACG	GTA
16	ACGTACGTACG	A	$\alpha _{3}$	GTA (( $\alpha _{6}$ ))
17	ACGTACGTACG	AC
18	ACGTACGTACG	ACG
19	ACGTACGTACG		$\alpha _{5}$

Dizionario
Sequenza	Codice
A	A
C	C
G	G
T	T
AC	$\alpha _{1}$
CG	$\alpha _{2}$
GT	$\alpha _{3}$
TA	$\alpha _{4}$
ACG	$\alpha _{5}$
GTA	$\alpha _{6}$

La stringa codificata risulta ACGT $\alpha _{1}\alpha _{3}\alpha _{5}$ . L'input ACGT ACGT ACG è di 12 simboli, mentre l'output ACGT $\alpha _{1}\alpha _{3}\alpha _{5}$ è di 7 simboli, quindi il rapporto di compressione è: $\left(1-{\frac {7}{12}}\right)*100\approx 42\%$

Da questo esempio si evince che per ottenere una buona compressione, è necessario che i dati in input contengano numerose ripetizioni. All'aumentare della lunghezza dell'input, tuttavia, il rapporto di compressione tende asintoticamente al massimo.^[2]

Di seguito è riportato lo pseudocodice relativo alla compressione (si assume che il dizionario sia già inizializzato con i simboli dell'alfabeto):

buffer = VUOTO
CICLO
  LEGGI IL SIMBOLO k
  SE buffer + k ESISTE NEL DIZIONARIO
      buffer = buffer + k
  ALTRIMENTI
      // Cerca il buffer all'interno del DIZIONARIO, ritornando il codice associato
      codice = DIZIONARIO[buffer] 
      INVIA codice
      AGGIUNGI buffer + k AL DIZIONARIO
      buffer = k
  FINE SE
FINECICLO

Decompressione modifica

Inzialmente il dizionario del decoder è identico a quello dell'encoder (all'inizio del processo di compressione), che conterrà anch'egli solamente voci dei simboli dell'alfabeto.
Quindi, analogamente il dizionario si presenta:

Dizionario
Sequenza	Codice
A	A
C	C
G	G
T	T

Anche il buffer assume lo stesso stato iniziale del buffer dell'encoder, infatti è attualmente vuoto, ma verrà utilizzato sempre per il nuovo inserimento delle voci.

Il decoder comincia il processo di decompressione analizzando la stringa compressa, traducendo e convertendo ogni singolo simbolo. In questo caso:

ACGT

\alpha _{1}\alpha _{3}\alpha _{5}

Le iterazioni sono le seguenti:

Iterazione	Input	Buffer corrente	Congettura	Simbolo in output	Voce aggiunta nel dizionario
1	ACGT $\alpha _{1}\alpha _{3}\alpha _{5}$	(vuoto)		(nessuno)	(nessuna)
2	ACGT $\alpha _{1}\alpha _{3}\alpha _{5}$	A	A+?	A
3	ACGT $\alpha _{1}\alpha _{3}\alpha _{5}$	C	C+?	C	AC (( $\alpha _{1}$ ))
4	ACGT $\alpha _{1}\alpha _{3}\alpha _{5}$	G	G+?	G	CG (( $\alpha _{2}$ ))
5	ACGT $\alpha _{1}\alpha _{3}\alpha _{5}$	T	T+?	T	GT (( $\alpha _{3}$ ))

Dizionario
Sequenza	Codice
A	A
C	C
G	G
T	T
AC	$\alpha _{1}$
CG	$\alpha _{2}$
GT	$\alpha _{3}$

Ad ogni iterazione, il decoder legge un simbolo X, viene inviato in output ed inserito nel buffer, composto dalla congettura X+? dove "?" è il simbolo successivo (Che ancora il decoder non conosce). Da notare che il simbolo successivo è sempre il primo della lettura successiva, incluso anche il caso di lettura di nuove voci(ad esempio se la lettura successiva è una nuova voce, avente come sottostringa di simboli ACG, viene considerato solo A); il contenuto del buffer viene aggiunto come nuova voce e dopo viene lasciato solo il simbolo attualmente in lettura. C'è un caso però in cui il simbolo successivo non è presente nel dizionario(vedi Caso speciale). Come si può notare, fino ad ora, il processo di decompressione segue un procedimento simile a quello della compressione, considerando il fatto che i primi simboli non sono stati compressi perchè la stringa inizialmente non conteneva nessuna sequenza che non sia presente nel dizionario; le differenze sostanziali della decompressione stanno, dunque, nell' utilizzo delle congetture X+? del buffer. Quando il decoder giunge in un simbolo coincidente con una delle nuove voci del dizionario, lo traduce, lo manda in output e viene applicata la sua congettura. Il simbolo $\alpha _{1}$ coincide nel dizionario con AC, quindi l'econder invia in output AC ed applica la congettura AC+? dimostrato qua di seguito con la 6° iterazione. Il processo di decompressione procederà in maniera analoga finquando termina la stringa.

Iterazione	Input	Buffer corrente	Congettura	Simbolo in output	Voce aggiunta nel dizionario	Conversione
6	ACGT $\alpha _{1}$ $\alpha _{3}\alpha _{5}$	AC	AC+?	AC	TA (( $\alpha _{4}$ ))	$\alpha _{1}$ =AC
7	ACGT $\alpha _{1}\alpha _{3}$ $\alpha _{5}$	CG	GT+?	GT	ACG(( $\alpha _{5}$ ))	$\alpha _{3}$ =GT
8	ACGT $\alpha _{1}$ $\alpha _{3}\alpha _{5}$	GTA	ACG+?	ACG	GTA(( $\alpha _{6}$ ))	$\alpha _{5}$ =ACG
9	ACGT $\alpha _{1}$ $\alpha _{3}\alpha _{5}$

Dizionario
Sequenza	Codice
A	A
C	C
G	G
T	T
AC	$\alpha _{1}$
CG	$\alpha _{2}$
GT	$\alpha _{3}$
TA	$\alpha _{4}$
ACG	$\alpha _{5}$
GTA	$\alpha _{6}$

La stringa ottenuta è quindi ACGTACGTACG (12 simboli), che rispetto a quella compressa ACGT $\alpha _{1}\alpha _{3}\alpha _{5}$ (7 simboli), presenta 5 simboli in più (12-7 simboli), riportando così la stessa dimensione della stringa iniziale prima del processo di compressione e decompressione; da notare il fatto che al termine della decompressione, si ha lo stesso dizionario finale della compressione, giungendo così alle conclusioni che non è necessario l'invio del dizionario, visto e considerato che viene ricostruito dal decoder in maniera del tutto indipendente. Questo conferma la validità del metodo di compressione LZW senza riportare alcuna perdita di simboli (o genericamente di dati). Lo pseudocodice abbinato alla decompressione è così strutturato:

LEGGI k
INVIA k
buffer = k
CICLO
  LEGGI codice
  sottostringa= DIZIONARIO[codice]
  output sottostringa
  AGGIUNGI buffer + PRIMO CARATTERE DI sottostringa AL DIZIONARIO
  buffer = sottostringa
FINE CICLO

Caso speciale modifica

Come accennato prima, vi è un caso speciale di decompressione: Cosa succede se il decoder riceve un codice Z che non è ancora nel dizionario? Finchè il decoder è sempre un codice indietro all'encoder, Z può essere nel dizionario dell'encoder solo se l'encoder lo genera, quando emette il precedente codice X per Y. Così gli Z codici, alcuni ω che sono Y + ? e il decoder possono determinare il carattere sconosciuto come segue:

Il decoder legge X=C e poi Z=alpha1
Conosce la sequenza di X e Z identificati con Y + alcune ω sequenze sconosciute
Il decoder sa che Z è stato aggiunto nel dizionario dell'encoder per Y+qualche carattere sconosciuto "?"
Conosce che "?" è la prima lettera di ω
La prima lettera di ω=Y+? deve essere anche la prima lettera di Y
ω deve essere quindi Y+x, dove x è la prima lettera di Y(x=?)
Ciò implica che Z=ω=Y+x
Trovato Z, questo viene inserito nel dizionario
Si procede in maniera analoga con il resto della decompressione

Questa situazione accade ogni volta che l'encoder incontra input sotto la forma cScSc, dove c è un singolo carattere ed S è una stringa; cS è già all'interno del dizionario, ma cSc no. L'encoder emette il codice per cS, inserendo un nuovo codice per cSc nel dizionario. Dopo individua la presenza di cSc nell'input (partendo dalla seconda c di cScSc) ed emette il nuovo codice appena inserito. Anche se l'input sotto tale forma è un caso raro, questo schema diventa piuttosto comune quando il flusso di input è caratterizzato da significanti ripetizioni. In particolare, lunghe stringhe di un singolo carattere (che sono comuni in vari tipi di immagini la quale l'LZW spesso comprime) generano ripetutamente schemi di questo genere. Per rendere chiaro il processo utilizzato in tale caso speciale, si consideri il seguente esempio:

"CCC"

Anche questo è un caso speciale nella forma cScSc (per la precisione cS, che è pur sempre un derivato della forma del caso speciale). Il processo di compressione di tale stringa avviene regolarmente, come è mostrato nella seguente tabella:

Iterazione	Input	Buffer corrente	Simbolo in output	Voce aggiunta nel dizionario
1	CCC	(vuoto)	(nessuno)	(nessuna)
2	CCC	C
3	CCC	CC
4	CCC	C	C	CC (( $\alpha _{1}$ ))
5	CCC	CC
6	CCC		$\alpha _{1}$

Dizionario
Sequenza	Codice
C	C
CC	$\alpha _{1}$

La Stringa compressa risulta quindi:

"C

\alpha _{1}

"

Per il processo di decompressione, sorgono i primi problemi, perchè come si potrà vedere, mancherà $\alpha _{1}$ nel dizionario del decoder:

Iterazione	Input	Buffer corrente	Congettura	Simbolo in output	Voce aggiunta nel dizionario	Conversione
1	C $\alpha _{1}$	(vuoto)		(nessuno)	(nessuna)
2	C $\alpha _{1}$	C	C+?	C
3	C $\alpha _{1}$					$\alpha _{1}$ =???

Dizionario
Sequenza	Codice
C	C

È necessario, dunque, dover adottare il metodo suddetto: la voce mancante si ottiene sommando il simbolo decompresso nella iterazione precedente con il suo primo carattere che lo compone. In questo caso C è il simbolo precedentemente decompresso (e già mandato in output); il suo primo carattere non può che essere sè stesso, visto che il simbolo non è una voce nuova (per chiarimento, se la precedente decompressione era un simbolo composto dai caratteri AC, allora la voce mancante si otteneva da questa sommata al suo primo carattere, ossia A quindi risultava: $\alpha 1$ =AC+A=ACA). Quindi la voce mancate è $\alpha _{1}$ =CC. Si procede quindi:

Iterazione	Input	Buffer corrente	Primo carattere	Congettura	Simbolo in output	Voce aggiunta nel dizionario	Conversione
1	C $\alpha _{1}$	(vuoto)			(nessuno)	(nessuna)
2	C $\alpha _{1}$	C		C+?	C
3	C $\alpha _{1}$	C	C			CC (( $\alpha _{1}$ ))
4	C $\alpha _{1}$	CC		CC+?	CC		$\alpha _{1}$ =CC

Dizionario
Sequenza	Codice
C	C
CC	$\alpha _{1}$

Si otterrà così la stessa stringa decompressa di partenza, senza alcuna perdita di dati e risolvendo anche il problema del codice mancante nel dizionario. Lo pseudocodice "alternativo" per questo caso speciale è il seguente:

LEGGI k
INVIA k
buffer = k
CICLO
  LEGGI codice
  SE codice È PRESENTE NEL DIZIONARIO
     sottostringa= DIZIONARIO[codice]
     output sottostringa
     AGGIUNGI buffer + PRIMO CARATTERE DI sottostringa AL DIZIONARIO
     buffer = sottostringa
  ALTRIMENTI
     AGGIUNGI k + PRIMO CARATTERE DI k AL DIZIONARIO
     sottostringa= DIZIONARIO[codice]
     outuput sottostringa
     buffer = sottostringa
FINE CICLO

Implementazione modifica

La concreta implementazione dell'algoritmo LZW presenta alcune considerazioni/problematiche che non emergono dagli esempi precedenti.
Finora infatti nella descrizione si è fatto uso di strumenti "matematici", ideali.

In informatica, un simbolo (o più propriamente carattere) è rappresentato da una sequenza di bit di lunghezza prefissata.
Ad esempio tutti i possibili caratteri di 3 bit (che costituiscono, quindi, ciò che chiamiamo alfabeto) sono:

Alfabeto (3 bit/simbolo)
Stringa di bit	Valore decimale
000	0
001	1
010	2
011	3
100	4
101	5
110	6
111	7

Una stringa di '0' e '1' può essere interpretata come un numero naturale scritto in base 2, al quale spesso si usa fare riferimento in decimale.
Il numero di simboli rappresentabili con n bit è dato dalla formula $2^{n}$ . I corrispettivi valori in decimale andranno da $0$ a $2^{n}-1$ .

Input modifica

I dati in input di entrambe le fasi (encoding e decoding) sono sostanzialmente un flusso di bit di lunghezza qualsiasi.
Il modo in cui essi vengono interpretati, però, può essere diverso tra le due fasi. Per esempio, la seguente stringa

potrebbe essere intesa come due simboli di 3 bit,

010 111

oppure tre simboli di 2 bit:

01 01 11

E' chiaro quindi che l'encoder ed il decoder, per leggere un simbolo, devono stabilire da quanti bit è formato.

Input dell'encoder modifica

L'input dell'algoritmo di compressione potrebbe essere, ad esempio:

010101110100100101001011010010010101000001000101010001000100100101000001

Una scelta tipica è quella di utilizzare stringhe lunghe 8 bit per rappresentare ciascun carattere. Ciò è dovuto principalmente a due motivi:

La CPU può manipolare, in base alla sua architettura, blocchi di dati la cui lunghezza è multipla di 8 bit.
La codifica ASCII standard, diffusa in tutto il mondo, utilizza 8 bit per carattere.

Nell'esempio l'alfabeto iniziale (sul quale l'encoder si basa per leggere l'input), è composto da tutti i simboli rappresentabili da tale codifica, che sono $2^{8}=256$ .

In base a quanto detto, allora, il flusso di bit precedente è da leggere a blocchi di 8 bit:

01010111_01001001_01001011_01001001_01010000_01000101_01000100_01001001_01000001

La codifica ASCII associa ad ogni stringa di 8 bit un carattere visualizzabile a video (per esempio, la lettera 'A' corrisponde al codice 65, in binario 01000001).

L'input visto in precedenza, perciò, è la rappresentazione codificata della scritta

WIKIPEDIA

Output dell'encoder/Input del decoder modifica

L'output dell'encoder costituisce ciò che il decoder leggerà in input, dunque è indispensabile che le due fasi siano concordi nel modo in cui vengono interpretati i dati.

Come descritto in precedenza, l'idea fondamentale di LZW è quella di estendere l'alfabeto iniziale aggiungendo nuovi simboli "speciali", ognuno dei quali potrà essere usato nel dizionario.

L'alfabeto esteso dovrà comprendere sia i simboli dell'alfabeto iniziale (nel nostro esempio quelli della codifica ASCII) sia simboli "speciali".
In ogni caso tutti i simboli dovranno essere rappresentati da stringhe di bit differenti tra di loro, altrimenti non sarà possibile distinguere un simbolo dall'altro.

Nel nostro esempio la codifica ASCII adottata utilizza già tutte le possibili stringhe di 8 bit, perciò risulta evidente che non c'è "spazio" per l'aggiunta di nuovi simboli a 8 bit. Generalmente, per estendere l'alfabeto, bisogna impiegare un numero di bit maggiore per codificare ciascun simbolo.

Nella pubblicazione di Welch del 1984, l'autore sceglie di codificare i simboli di 8 bit dell'alfabeto iniziale in simboli di lunghezza fissa di 12 bit (che costituiranno l'alfabeto esteso). Le prime 256 combinazioni corrispondono ai simboli iniziali, mentre le restanti 3840 ( $2^{12}-2^{8}=4096-256=3840$ ) vengono utilizzate nel dizionario come simboli speciali. Normalmente, quando si estende un'alfabeto, si fa in modo che i simboli dell'alfabeto iniziale e quelli dell'alfabeto esteso abbiano gli stessi valori in decimale.
Per chiarire meglio il concetto, consideriamo il simbolo "A" ad 8 bit (secondo la codifica ASCII):

0100 0001

lo stesso, nell'alfabeto esteso di 12 bit, diventa:

0000 0100 0001

Ovviamente, in entrambi i casi, la lettera 'A' corrisponde al numero decimale 65.

Ricapitolando, bisogna fare distinzione tra:

Il numero di bit utilizzati per rappresentare ciascun simbolo dell'alfabeto iniziale (es. 8 bit per la codifica ASCII).
Il numero di bit utilizzati per rappresentare ciascun simbolo dell'alfabeto esteso (es. 12 bit).

Come già accennato, tra l'algoritmo di encoding e di decoding deve esserci una certa concordanza: il numero di bit per simbolo è uno tra i parametri da stabilire.

Ordine dei bit modifica

Un ulteriore parametro da concordare è l'ordine in cui i bit vengono scritti/letti in memoria.
Qui conveniamo (in modo analogo alla scrittura dei numeri decimali) che una stringa binaria venga scritta dalla cifra col peso maggiore (MSB) fino alla cifra col peso minore (LSB) da sinistra verso destra.

MSB ---> 100011110100 <--- LSB

Implementare l'algoritmo LZW presenta la necessità (specialmente per i simboli dell'alfabeto esteso) di lavorare con stringhe di lunghezza qualsiasi. Immaginiamo di dover mandare in output un simbolo di 12 bit

100011110100

Come già accennato, la CPU non è in grado di manipolare stringhe di lunghezza qualsiasi, ma solo di lunghezza multipla di 8 bit (cioè un byte).
Per questo motivo non è possibile scrivere direttamente 12 bit, ma si è costretti a mandare in output una stringa lunga 16 bit (2 byte).
Vi sono due convenzioni per ordinare i bit:

LSB-First ("Least Significant Bit First", bit meno significativo prima).
MSB-First ("Most Significant Bit First", bit più significativo prima).

I file GIF usano LSB-First, mentre i file TIFF e PDF utilizzano MSB-First.

LSB-First modifica

Col metodo LSB-First, i primi 8 bit meno significativi (nell'esempio 11110100) sono allineati con l'LSB del primo byte. I restanti 4 bit più significativi (1000) sono allineati con l'LSB del secondo byte. Gli eventuali bit rimanenti vengono completati con degli zeri (in questo caso 4). Se in seguito verrà inviato un nuovo simbolo, esso partirà dall'LSB di un nuovo byte. La stringa 100011110100 mandata in output con il metodo LSB-First diventa:

Byte in output
Primo byte	Secondo byte
11110100	00001000

MSB-First modifica

Col metodo MSB-First, i primi 8 bit più significativi (nell'esempio 10001111) sono allineati con l'MSB del primo byte. I restanti 4 bit meno significativi (0100) sono allineati con l'MSB del secondo byte. Gli eventuali bit rimanenti vengono completati con degli zeri (in questo caso 4). Se in seguito verrà inviato un nuovo simbolo, esso partirà dall'MSB di un nuovo byte. La stringa 100011110100 mandata in output con il metodo MSB-First diventa:

Byte in output
Primo byte	Secondo byte
10001111	01000000

Codici a lunghezza variabile modifica

I codici a lunghezza variabilie sono utilizzati in vari contesti di dati. In una immagine basata su una tavola di colori (o tavolozza), per esempio, l'alfabeto dei caratteri naturali è un set di tavolozze indicizzate; nel 1980, diverse immagini avevano piccole tavolozze (nell'ordine dei 16 colori). Per un tale alfabeto, i codici a 12 bit producevano una scarsa compressione se l'immagine non era grande; da questo vincolo si cominciò ad introdurre il concetto di codice a lunghezza variabile: i codici iniziavano tipicamente con una lunghezza di un bit più grande rispetto ai simboli da codificare e, come si usa in ogni codice, la lunghezza aumenta progressivamente di un bit, fino a un massimo prescritto (tipicamente 12 bits). Un esempio banale potrebbe essere un flusso di codici che parte da 0 e arriva sino a 10000 (binario):

Codice in bit	Numero di bits
0	1
1	1
10	2
11	2
100	3
101	3
110	3
111	3
1000	4
1001	4
1010	4
1011	4
1100	4
1101	4
1110	4
1111	4
10000	5

Se vengono usati i codici a lunghezza variabile, l'encoder ed il decoder devono sincronizzarsi nel cambio di lunghezza, in modo che venga effettuato nello stesso punto di un dato codificato, altrimenti saranno in disaccordo sulle lunghezze codice nei due flussi. Nella versione standard, l'encoder incrementa la lunghezza p a p+1 quando si incontra una sequenza ω che non è presente nel dizionario (quindi il codice deve essere aggiunto) ma il successivo codice disponibile nel dizionario è lungo 2^p(il primo codice richiede p+1 bits). L'encoder manda in output il codice per ω con lunghezza p (finchè il codice non richiede p+1 bits per essere inviato), quindi incrementa la lunghezza, in modo tale che il codice successivo sarà lungo p+1 bits. Il decoder è sempre un codice avanti rispetto all'encoder nella costruzione del dizionario, così quando legge il codice per ω, genera un input di lunghezza 2^p-1. Nel momento in cui l'encoder incrementa la lunghezza codice, deve incrementarla anche il decoder allo stesso modo, in modo tale che il codice più lungo dovrà essere contenuto in p bits (la stessa lunghezza quindi del codice più lungo dell'encoder).

Cambio Anticipato modifica

Le prime implementazioni dell'algoritmo prima incrementano la lunghezza codice e poi inviano il codice per ω, con la conseguenza che ω avesse la nuova lunghezza codice e non quella vecchia; stessa cosa anche per il decoder, che cambia troppo presto la lunghezza di un codice. Questo fenomeno è chiamato "Cambio Anticipato" (Early Change); questa versione ha causato molta confusione nell'ambito di file gestiti, ad esempio, da Adobe, al punto che ora permette entrambe le versioni (ossia con o senza Cambio Anticipato) in file PDF, includendo un flag esplicito nell'intestazione di ogni flusso di compressione LZW, indicando quando è utilizzato il Cambio Anticipato. Per quanto riguarda i formati che gestiscono dati grafici (Gif o Tif, per esempio), il Cambio Anticipato non è utilizzato. Quando il dizionario viene ripulito da un "clear code", sia l'encoder che il decoder cambiano la lunghezza codice solo dopo che il "clear code" ritorna alla lunghezza iniziale.

Raffinamenti modifica

Ulteriori raffinamenti includono:

Un "clear code": un codice riservato ad indicare quando il dizionario deve essere ripulito. Tipicamente è il primo valore immediatamente successivo a tutti i valori di ogni carattere dell'alfabeto (ad esempio se in totale l'alfabeto di ogni singolo carattere è 255, il clear code è 256). Il clear code permette di essere reinizializzato il dizionario, dopo che viene riempito, in modo da permettere un adattamento della codifica, cambiando lo schema dei dati in input.
Uno "stop code": un codice per indicare la fine del dato. Tipicamente un valore più grande del clear code (seguendo il precedente esempio, lo stop code sarebbe 257).

Alcuni encoder sviluppati possono monitorare l'efficenza e ripulire la tavola ogni qualvolta il dizionario esistente non corrisponde all'input. È fondamentale che encoder e decoder siano in accordo alla varietà di LZW da utilizzare:

La dimensione dell'alfabeto
La lunghezza massima del codice
Quale lunghezza variabile è in uso
La dimensione del codice iniziale
Quale clear e stop codes sono in uso (e i loro valori).

Molti formati che impiegano l'LZW costruiscono queste informazioni in specifici formati oppure forniscono campi espliciti nell'intestazione della compressione.

Applicazioni modifica

Il metodo divenne ampiamente usato in programmi di compressione, che divenne più o meno una utility standard nei sistemi Unix circa nel 1986. Da allora è scomparso da molti sistemi, per ragioni giuridiche e tecniche, ma a partire dal 2008 almeno FreeBSD comprende le utilità di compressione e decompressione come parte della distribuzione. Molti altri popolari programmi utilizzano anche questo metodo, o quelli strettamente connessi. È diventato in uso in larga scala dopo che divenne parte del formato GIF nel 1987. È anche (facoltativamente) usato in file TIFF. La compressione LZW fornisce uno dei migliori livelli di compressione, in molte applicazioni, rispetto a qualsiasi metodo ben noto a disposizione fino a quel momento. È diventato il primo metodo di compressione dei dati universale utilizzato ampiamente su computer. In genere comprime grandi testi in lingua inglese a circa la metà delle loro dimensioni originali. Oggi, una implementazione dell'algoritmo è contenuta nei popolari programmi software Adobe Acrobat. Acrobat, comunque, per default usa l'algoritmo Deflate per molti testi ed immagini basati su tavole di colori.

Varianti modifica

LZMW (1985, by V. Miller, M. Wegman)^[3] - Cerca input per le stringhe più lunghe presenti nel dizionario (la corrispondenza "corrente"); aggiunge la concatenazione di precedenti corrispondeze con quella corrente al dizionario. (Il dizionario si riempie più velocemente, ma questo schema è più complesso da implementare). Miller e Wegman inoltre consigliano di eliminare le voci con bassa ricorrenza dal dizionario quando si riempie.
LZAP (1988, by James Storer)^[4] - modifica dell'LZMW: invece di aggiungere solo la concatenazione della corrispondenza precedente con quella corrente al dizionario, aggiunge le concatenazioni della corrispondenza precedente con ogni sottostringa iniziale di quella in corso.
LZWL è una variante dell'LZW basata su sillabe.

Bibliografia modifica

^ Terry Welch, "A Technique for High-Performance Data Compression", IEEE Computer, June 1984, p. 8–19.
^ Jacob Ziv and Abraham Lempel; Compression of Individual Sequences Via Variable-Rate Coding, IEEE Transactions on Information Theory, September 1978.
^ David Salomon, Data Compression – The complete reference, 4th ed., page 209
^ David Salomon, Data Compression – The complete reference, 4th ed., page 212

Voci correlate modifica

Collegamenti esterni modifica

Un applet JAVA che mostra passo passo il processo di compressione/decompressione di una stringa.

Welch, T.A., A Technique for High-Performance Data Compression, Computer, vol. 17, no. 6, pp. 8-19, June 1984 (Link alternativo).

(EN) – Un articolo sulla compressione LZW.

(EN) US4558302, United States Patent and Trademark Office, Stati Uniti d'America., Terry A. Welch, High speed data compression and decompression apparatus and method

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica

[[Categoria:Algoritmi di compressione]] [[Categoria:Compressione dati]]

[WelchIEEE-1] Terry Welch, "A Technique for High-Performance Data Compression", IEEE Computer, June 1984, p. 8–19.

[2] Jacob Ziv and Abraham Lempel; Compression of Individual Sequences Via Variable-Rate Coding, IEEE Transactions on Information Theory, September 1978.

[3] David Salomon, Data Compression – The complete reference, 4th ed., page 209

[4] David Salomon, Data Compression – The complete reference, 4th ed., page 212

[1]

[2]

[3]

[4]

Utente:XDnl/Sandbox

Indice