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
PresentatoTerry Welch, "A Technique for High-Performance Data Compression", IEEE Computer, June 1984, p. 8–19. 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
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:
Una stringa sull'alfabeto è 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 GT
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: G La nuova stringa è costruita su unestensione dell'alfabeto iniziale, precisamente:
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 , ). 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 (). 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 (()) 5 ACGTACGTACG CG 6 ACGTACGTACG G C CG (()) 7 ACGTACGTACG GT 8 ACGTACGTACG T G GT (()) 9 ACGTACGTACG TA 10 ACGTACGTACG A T TA (())
Dizionario Sequenza Codice A A C C G G T T AC CG GT TA 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 ACG (()) 14 ACGTACGTACG GT 15 ACGTACGTACG GTA 16 ACGTACGTACG A GTA (()) 17 ACGTACGTACG AC 18 ACGTACGTACG ACG 19 ACGTACGTACG
Dizionario Sequenza Codice A A C C G G T T AC CG GT TA ACG GTA La stringa codificata risulta ACGT. L'input ACGT ACGT ACG è di 11 simboli, mentre l'output ACGT è di 7 simboli, quindi il rapporto di compressione è:
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.Jacob Ziv and Abraham Lempel; Compression of Individual Sequences Via Variable-Rate Coding , IEEE Transactions on Information Theory, September 1978.
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
Le iterazioni sono le seguenti: Iterazione Input Buffer corrente Congettura Simbolo in output Voce aggiunta nel dizionario Conversione 1 ACGT (vuoto) (nessuno) (nessuna) 2 ACGT A A+? A 3 ACGT C C+? C AC (()) 4 ACGT G G+? G CG (()) 5 ACGT T T+? T GT (())
Dizionario Sequenza Codice A A C C G G T T AC CG GT 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 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 AC AC+? AC TA (()) =AC 7 ACGT ACG GT+? GT ACG(()) =GT 8 ACGT GTA ACG+? ACG GTA(()) =ACG 9 ACGT
Dizionario Sequenza Codice A A C C G G T T AC CG GT TA ACG GTA La stringa ottenuta è quindi ACGTACGTACG (11 simboli), che rispetto a quella compressa ACGT(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