Lempel-Ziv-Welch

LZW
Sviluppatore	Abraham Lempel, Jacob Ziv, Terry Welch
Tipo	Compressione dei dati
Compressione	Lossless

Lempel-Ziv-Welch (abbreviato LZW) è un algoritmo utilizzato in informatica per la compressione dati senza perdita di informazioni (lossless). Per esempio questo algoritmo è utilizzato nella codifica delle immagini in formato GIF e facoltativamente nei file TIFF.

Storia

• 
  Abraham Lempel
• 
  Jacob Ziv

Presentato da Terry Welch nel 1984, l'algoritmo si basa su precedenti ricerche effettuate da Jacob Ziv ed Abraham Lempel.

Infatti questi ultimi 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.

Descrizione

Alcuni vantaggi della compressione LZW sono:

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

Il fattore di compressione spesso risulta essere non molto elevato, proprio per la genericità dell'algoritmo che non trae vantaggio dalle peculiarità dei dati da comprimere.

Premesse

Il DNA può essere visto come sequenza di A, C, G e T

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 si immagini di voler archiviare una sequenza di DNA.
In generale una porzione di DNA è composta da una sequenza (finita) di 4 basi azotate: Adenina, Timina, Citosina e Guanina.
L'alfabeto su cui è 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 delle basi, 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 significa esprimere la stessa informazione impiegando un numero inferiore di simboli.

La struttura

Molto spesso la stringa in ingresso 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

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. L'algoritmo ha prestazioni differenti in base ai dati in ingresso e in generale è più adatto nella compressione di file testuali. Man mano che viene esaminata la stringa in ingresso, 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:

• AC
• GT

Queste due sottostringhe saranno "rilevate" dall'algoritmo che provvederà ad inserirle nel dizionario e ad associarvi 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'informazione da comprimere.

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}\}$

Il risultato della compressione è costituito solamente dalla stringa codificata in quanto il dizionario non viene memorizzato perché in realtà 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'ingresso dell'algoritmo di decompressione (decoder) è perciò una stringa costituita dai dati (simboli A, C, G, T) e dai 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

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

Per determinare le voci da inserire nel dizionario l'algoritmo utilizza una stringa a parte, d'ora in poi 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. Nell'esempio "ACGTACGTACG" si hanno i seguenti passaggi (in giallo viene evidenziata la parte contenuta nel buffer):

Ogni riga descrive lo stato dell'algoritmo 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: nell'esempio A. Così facendo si ottiene una stringa contenuta nel dizionario.
• La sottostringa A nel buffer viene cercata nel dizionario, mandando in uscita 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 11 simboli, mentre l'output ACGT$\alpha _{1}\alpha _{3}\alpha _{5}$ è di 7 simboli, quindi il rapporto di compressione è:

$\left(1-{\frac {7}{11}}\right)*100\approx 36\%$

Da questo esempio si evince che per ottenere una buona compressione, è necessario che i dati in input contengano numerose ripetizioni. All'aumentare della lunghezza dei dati da comprimente il rapporto di compressione tende asintoticamente al massimo.

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, restituendo il codice associato
codice = DIZIONARIO[buffer]
INVIA codice
AGGIUNGI buffer + k AL DIZIONARIO
buffer = k
FINE SE
FINECICLO

Decompressione

Inizialmente il dizionario del decoder è identico a quello dell'encoder all'inizio del processo di compressione e contiene anch'esso 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	Conversione
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, lo invia in uscita e lo inserisce nel buffer, composto dalla congettura X+? dove "?" è il simbolo successivo che ancora il decoder non conosce. Il simbolo successivo è sempre il primo della lettura successiva, incluso anche il caso di lettura di nuove voci: per esempio se la lettura successiva è una nuova voce avente come sottostringa di simboli ACG si considera 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 (vedere caso speciale). Fino a qui il processo di decompressione ha seguito 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 fosse presente nel dizionario. Le differenze sostanziali della decompressione stanno nell'utilizzo delle congetture X+? del buffer. Quando il decoder giunge a un simbolo coincidente con una delle nuove voci del dizionario lo traduce, lo manda in uscita e applica la sua congettura. Il simbolo $\alpha _{1}$ coincide nel dizionario con AC, quindi l'encoder invia in uscita AC e applica la congettura AC+?, come mostrato qua di seguito con la 6ª iterazione. Il processo di decompressione procede in maniera analoga fin quando 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}$	ACG	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 (11 simboli), che rispetto a quella compressa ACGT$\alpha _{1}\alpha _{3}\alpha _{5}$(7 simboli), presenta 4 simboli in più (11-7 simboli), riportando così la stessa dimensione della stringa iniziale prima del processo di compressione e decompressione. Al termine della decompressione si ha lo stesso dizionario finale della compressione, giungendo così alle conclusioni che non è necessario l'invio del dizionario, dato 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 più genericamente di dati. Lo pseudocodice abbinato alla decompressione è così strutturato:

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

Esiste un caso speciale di decompressione, quello in cui il decoder riceve un codice Z 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:

1. Il decoder legge X=C e poi Z=alpha1
2. Conosce la sequenza di X e Z identificati con Y + alcune ω sequenze sconosciute
3. Il decoder sa che Z è stato aggiunto nel dizionario dell'encoder per Y+qualche carattere sconosciuto "?"
4. Conosce che "?" è la prima lettera di ω
5. La prima lettera di ω=Y+? deve essere anche la prima lettera di Y
6. ω deve essere quindi Y+x, dove x è la prima lettera di Y(x=?)
7. Ciò implica che Z=ω=Y+x
8. Trovato Z, questo viene inserito nel dizionario
9. 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 un dato in ingresso di questo forma è 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, generano ripetutamente schemi di questo genere. Il seguente esempio rende chiaro questo caso:

"CCC"

Anche questo è un caso speciale nella forma cScSc e per la precisione cS. Il processo di compressione di questa 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é manca $\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 quindi 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 uscita; il suo primo carattere non può che essere sé stesso, visto che il simbolo non è una voce nuova. Quindi la voce mancate è $\alpha _{1}$=CC. Se la precedente decompressione era un simbolo composto dai caratteri AC, allora la voce mancante si otteneva aggiungendo a questa voce il suo primo carattere, ossia A: $\alpha _{1}$=AC+A=ACA.

Tornando all'esempio:

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

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 i simboli di un alfabeto costituito da tutti i possibili caratteri di 3 bit 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 a cui 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

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

010111

potrebbe essere intesa come due simboli di 3 bit,

010 111

oppure tre simboli di 2 bit:

01 01 11

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

Input dell'encoder

Il dato in ingresso dell'algoritmo di compressione potrebbe essere:

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 questa codifica, che sono $2^{8}=256$. Quindi 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. Per esempio, la lettera 'A' corrisponde al codice 65, in binario 01000001.

L'input dell'esempio è la rappresentazione codificata della scritta.

WIKIPEDIA

Output dell'encoder/Input del decoder

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

L'idea fondamentale di LZW è quella di estendere l'alfabeto iniziale aggiungendo nuovi simboli "speciali", ognuno dei quali può essere usato nel dizionario.

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

Nell'esempio la codifica ASCII adottata utilizza già tutte le possibili stringhe di 8 bit, perciò 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. 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 esempio il simbolo "A" ad 8 bit secondo la codifica ASCII:

0100 0001

nell'alfabeto esteso di 12 bit diventa:

0000 0100 0001

In entrambi i casi la lettera 'A' corrisponde al numero decimale 65.

Esiste quindi una 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).

Gli algoritmi di encoding e di decoding devono avere delle convenzioni comuni: il numero di bit per simbolo è uno tra i parametri comuni concordati a priori.

Ordine dei bit

Un ulteriore parametro da concordare è l'ordine in cui i bit vengono scritti/letti in memoria.

Nell'esempio, in modo analogo alla scrittura dei numeri decimali, una stringa binaria viene 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. Se si deve mandare in output un simbolo di 12 bit

100011110100

si è costretti a mandare in output una stringa lunga 16 bit (2 byte) perché la CPU non è in grado di manipolare stringhe di lunghezza qualsiasi, ma solo di lunghezza multipla di 8 bit (cioè un 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

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

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

I codici a lunghezza variabile sono utilizzati in vari contesti di dati. Per esempio, in una immagine basata su una tavola di colori (o tavolozza) l'alfabeto dei caratteri naturali è un set di tavolozze indicizzate; nel 1980 diverse immagini avevano piccole tavolozze, dell'ordine dei 16 colori. Per questo 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 bit. Ne è un esempio un flusso di codici che parte da 0 e arriva sino a 10000 (binario):

Codice in bit	Numero di bit
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 sincronizzare il 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 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 bit). L'encoder manda in output il codice per ω con lunghezza p (finché il codice non richiede p+1 bit per essere inviato), quindi incrementa la lunghezza, in modo tale che il codice successivo sarà lungo p+1 bit. 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 che il codice più lungo dovrà essere contenuto in p bit (la stessa lunghezza quindi del codice più lungo dell'encoder).

Cambio Anticipato

Le prime implementazioni dell'algoritmo prima incrementano la lunghezza codice e poi inviano il codice per ω, quindi ω aveva 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 in passato ha causato molta confusione nell'ambito di file gestiti per esempio da Adobe. Ora Adobe nei file PDF permette entrambe le versioni, ossia con o senza Cambio Anticipato, includendo un flag esplicito nell'intestazione di ogni flusso di compressione LZW per indicare 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 sia il decoder cambiano la lunghezza codice solo dopo che il "clear code" è ritornato alla lunghezza iniziale.

Affinamenti

Ulteriori affinamenti 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 reinizializzare il dizionario, una volta pieno, 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. Nel precedente esempio, lo stop code è 257.

Alcuni encoder sviluppati possono monitorare l'efficienza 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
• Quali clear e stop code 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

Il metodo divenne ampiamente usato in programmi di compressione e divenne più o meno un'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 algoritmo o metodi 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 di dati universale utilizzato ampiamente su computer. In genere comprime grandi testi in lingua inglese a circa la metà delle loro dimensioni originali. Oggi un'implementazione dell'algoritmo è contenuta nei popolari programmi software Adobe Acrobat. Comunque Acrobat per default usa l'algoritmo DEFLATE per molti testi ed immagini basati su tavole di colori.

Varianti

• LZMW (1985, by V. Miller, M. Wegman) - Cerca input per le stringhe più lunghe presenti nel dizionario (la corrispondenza "corrente"); aggiunge la concatenazione di precedenti corrispondenze 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) - 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.

Voci correlate

• Abraham Lempel
• Compressione lossless
• Graphics Interchange Format
• Jacob Ziv
• LZ77
• LZ78
• Tagged Image File Format
• Terry Welch

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su Lempel-Ziv-Welch

Collegamenti esterni

• Un applet JAVA che mostra passo passo il processo di compressione/decompressione di una stringa., su projects.hudecof.net. URL consultato il 2 marzo 2010 (archiviato dall'url originale il 7 gennaio 2010).
• Welch, T.A., A Technique for High-Performance Data Compression Archiviato il 30 maggio 2019 in Internet Archive., Computer, vol. 17, no. 6, pp. 8–19, June 1984 (Link alternativo).
• (EN)  – Un articolo sulla compressione LZW. Archiviato il 22 febbraio 2010 in Internet Archive.
• Un'implementazione ottimizzata in C++ dell'algoritmo di LZW, sorgenti e articolo dell'autore., su oldwildweb.com.
• (EN) US4558302, United States Patent and Trademark Office, Stati Uniti d'America., Terry A. Welch, High speed data compression and decompression apparatus and method