Utente:XDnl/Sandbox

Template:Compressione

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

•  
  Abraham Lempel
•  
  Jacob Ziv

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

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, 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:

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

Una stringa sull'alfabeto ${\displaystyle \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

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	${\displaystyle \alpha _{1}}$
GT	${\displaystyle \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:

${\displaystyle \alpha _{1}}$ ${\displaystyle \alpha _{2}}$ ${\displaystyle \alpha _{1}}$ ${\displaystyle \alpha _{2}}$ ${\displaystyle \alpha _{1}}$ G

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

${\displaystyle \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 ${\displaystyle \alpha _{1}}$ , ${\displaystyle \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

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 (${\displaystyle \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 ((${\displaystyle \alpha _{1}}$ ))
5	ACGTACGTACG	CG
6	ACGTACGTACG	G	C	CG ((${\displaystyle \alpha _{2}}$ ))
7	ACGTACGTACG	GT
8	ACGTACGTACG	T	G	GT ((${\displaystyle \alpha _{3}}$ ))
9	ACGTACGTACG	TA
10	ACGTACGTACG	A	T	TA ((${\displaystyle \alpha _{4}}$ ))

Dizionario
Sequenza	Codice
A	A
C	C
G	G
T	T
AC	${\displaystyle \alpha _{1}}$
CG	${\displaystyle \alpha _{2}}$
GT	${\displaystyle \alpha _{3}}$
TA	${\displaystyle \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	${\displaystyle \alpha _{1}}$	ACG ((${\displaystyle \alpha _{5}}$ ))
14	ACGTACGTACG	GT
15	ACGTACGTACG	GTA
16	ACGTACGTACG	A	${\displaystyle \alpha _{3}}$	GTA ((${\displaystyle \alpha _{6}}$ ))
17	ACGTACGTACG	AC
18	ACGTACGTACG	ACG
19	ACGTACGTACG		${\displaystyle \alpha _{5}}$

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

La stringa codificata risulta ACGT${\displaystyle \alpha _{1}\alpha _{3}\alpha _{5}}$ . L'input ACGT ACGT ACG è di 12 simboli, mentre l'output ACGT${\displaystyle \alpha _{1}\alpha _{3}\alpha _{5}}$  è di 7 simboli, quindi il rapporto di compressione è: ${\displaystyle \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

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${\displaystyle \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${\displaystyle \alpha _{1}\alpha _{3}\alpha _{5}}$	(vuoto)		(nessuno)	(nessuna)
2	ACGT${\displaystyle \alpha _{1}\alpha _{3}\alpha _{5}}$	A	A+?	A
3	ACGT${\displaystyle \alpha _{1}\alpha _{3}\alpha _{5}}$	C	C+?	C	AC ((${\displaystyle \alpha _{1}}$ ))
4	ACGT${\displaystyle \alpha _{1}\alpha _{3}\alpha _{5}}$	G	G+?	G	CG ((${\displaystyle \alpha _{2}}$ ))
5	ACGT${\displaystyle \alpha _{1}\alpha _{3}\alpha _{5}}$	T	T+?	T	GT ((${\displaystyle \alpha _{3}}$ ))

Dizionario
Sequenza	Codice
A	A
C	C
G	G
T	T
AC	${\displaystyle \alpha _{1}}$
CG	${\displaystyle \alpha _{2}}$
GT	${\displaystyle \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 ${\displaystyle \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${\displaystyle \alpha _{1}}$ ${\displaystyle \alpha _{3}\alpha _{5}}$	AC	AC+?	AC	TA ((${\displaystyle \alpha _{4}}$ ))	${\displaystyle \alpha _{1}}$ =AC
7	ACGT${\displaystyle \alpha _{1}\alpha _{3}}$ ${\displaystyle \alpha _{5}}$	CG	GT+?	GT	ACG((${\displaystyle \alpha _{5}}$ ))	${\displaystyle \alpha _{3}}$ =GT
8	ACGT${\displaystyle \alpha _{1}}$ ${\displaystyle \alpha _{3}\alpha _{5}}$	GTA	ACG+?	ACG	GTA((${\displaystyle \alpha _{6}}$ ))	${\displaystyle \alpha _{5}}$ =ACG
9	ACGT${\displaystyle \alpha _{1}}$ ${\displaystyle \alpha _{3}\alpha _{5}}$

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

La stringa ottenuta è quindi ACGTACGTACG (12 simboli), che rispetto a quella compressa ACGT${\displaystyle \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

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:

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 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 ((${\displaystyle \alpha _{1}}$ ))
5	CCC	CC
6	CCC		${\displaystyle \alpha _{1}}$

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

La Stringa compressa risulta quindi:

"C${\displaystyle \alpha _{1}}$ "

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

Iterazione	Input	Buffer corrente	Congettura	Simbolo in output	Voce aggiunta nel dizionario	Conversione
1	C${\displaystyle \alpha _{1}}$	(vuoto)		(nessuno)	(nessuna)
2	C${\displaystyle \alpha _{1}}$	C	C+?	C
3	C${\displaystyle \alpha _{1}}$					${\displaystyle \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: ${\displaystyle \alpha 1}$ =AC+A=ACA). Quindi la voce mancate è ${\displaystyle \alpha _{1}}$ =CC. Si procede quindi:

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

Dizionario
Sequenza	Codice
C	C
CC	${\displaystyle \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

Premesse

Algoritmo

Applicazioni

Varianti

Brevetti

Vari brevetti sono sono stati rilasciati negli USA ed in altri paesi per LZW ed algoritmi similari.

Bibliografia

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.

Voci correlate

• Compressione lossless
• LZ77
• LZ78
• Abraham Lempel
• Jacob Ziv
• Terry Welch
• GIF
• TIFF

Collegamenti esterni

• 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