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 di compressione 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, le stringhe in input contengono una o più parti (sotto-stringhe) ripetute 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; ad ogni stringa del dizionario, viene associato un nuovo simbolo non appartenente 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 ed inserite nel dizionario, alle quali verrano associati 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

All'inizio il dizionario contiene tante voci quanti sono i simboli dell'alfabeto.
Ogni sequenza corrisponde a un singolo simbolo, che coincide con il codice associato.
Nell'esempio precedente quindi, 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, collezionando i vari caratteri incontrati nel buffer, 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 (in questo caso dal terzo simbolo). 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 è quindi ACGT${\displaystyle \alpha _{1}\alpha _{3}\alpha _{5}}$ . La stringa iniziale ACGT ACGT ACG è di 12 simboli, mentre quella codificata 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
 ALTRIMENTNI
     INVIA IL CODICE ASSOCIATO A BUFFER
     AGGIUNGI BUFFER + K AL DIZIONARIO
     BUFFER = K
 FINECICLO

Decompressione

Inzialmente il dizionario del decoder è identico a quello dell'encoder (all'inizio del processo di compressione), che conterrà anch'egli solamente voci contenenti i 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 codificata, traducendo e convertendo ogni singolo simbolo. In questo caso:

ACGT${\displaystyle \alpha _{1}\alpha _{3}\alpha _{5}}$ 

i passaggi sono i seguenti:

Iterazione	Input	Buffer corrente	Simbolo in output	Voce aggiunta nel dizionario
1	ACGT${\displaystyle \alpha _{1}\alpha _{3}\alpha _{5}}$	(vuoto)	(nessuno)	(nessuna)
2	ACGT${\displaystyle \alpha _{1}\alpha _{3}\alpha _{5}}$	A
3	ACGT${\displaystyle \alpha _{1}\alpha _{3}\alpha _{5}}$	AC
4	ACGT${\displaystyle \alpha _{1}\alpha _{3}\alpha _{5}}$	C	A	AC ((${\displaystyle \alpha _{1}}$ ))
5	ACGT${\displaystyle \alpha _{1}\alpha _{3}\alpha _{5}}$	CG
6	ACGT${\displaystyle \alpha _{1}\alpha _{3}\alpha _{5}}$	G	C	CG ((${\displaystyle \alpha _{2}}$ ))
7	ACGT${\displaystyle \alpha _{1}\alpha _{3}\alpha _{5}}$	GT
8	ACGT${\displaystyle \alpha _{1}\alpha _{3}\alpha _{5}}$	T	G	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}}$

Come si può notare, fino ad ora, il processo di decompressione segue un procedimento identico a quello della compressione, considerando il fatto che i primi simboli non sono stati compressi perchè ancora la stringa non compressa non conteneva nessuna sequenza che non sia presente nel dizionario, compresele due nuove voci appena inserite (nell'iterazione 4 e 6) allo stesso modo. Nella terza iterazione, il decoder esegue gli stessi passi dell'encoder, procedendo quindi allo stesso processo di inserimento delle nuove voci, sfruttando il buffer (è evidenziato di giallo nella tabella il suo contenuto). Nell'iterazione successiva, viene letto il primo simbolo nuovo del dizionario; il decoder procede dunque all'identificazione della stringa compressa associata a quel simbolo, ricercandolo nel dizionario. Il simbolo ${\displaystyle \alpha _{1}}$  coincide nel dizionario con AC, quindi l'econder invia nel buffer in output AC, dimostrato qua di seguito con la 9° e la 10° iterazione:

Iterazione	Input	Buffer corrente	Simbolo in output	Voce aggiunta nel dizionario
9	ACGT${\displaystyle \alpha _{1}}$ ${\displaystyle \alpha _{3}\alpha _{5}}$	T${\displaystyle \alpha _{1}}$
10	ACGT${\displaystyle \alpha _{1}}$ ${\displaystyle \alpha _{3}\alpha _{5}}$		T	GT ((${\displaystyle \alpha _{3}}$ )) Implementazione Premesse Algoritmo Applicazioni Varianti Brevetti Vari brevetti sono sono stati rilasciati negli USA ed in altri paesi per LZW ed algoritmi similari. Bibliografia ^ 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. 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. (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