|
}}
In [[informatica]], '''LZW''' è un [[algoritmo]] per la [[compressione dati]] senza perdita di informazioni ([[Compressione dati lossless|lossless]]). TalePer tecnica,esempio adquesto esempio,algoritmo è utilizzatautilizzato nella [[codifica]] delle [[immagine digitale|immagini]] in formato [[Graphics Interchange Format|GIF]] e, facoltativamente, nei file [[Tagged Image File Format|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 ilIl 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.
== Storia ==
Presentato<ref name="WelchIEEE">Terry Welch, [http://ieeexplore.ieee.org/xpls/abs_all.jsp?tp=&arnumber=1659158&isnumber=34743 "A Technique for High-Performance Data Compression"], ''IEEE Computer'', June 1984, p. 8–19.</ref> da [[Terry Welch]] nel 1984, l'algoritmo si basa su precedenti ricerche effettuate da [[Jacob Ziv]] ed [[Abraham Lempel]].
QuestiInfatti ultimi,questi infatti,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.
Nel 1984, [[Terry Welch]] migliorò [[LZ78]] dando origine all'algoritmo conosciuto oggi come LZW (acronimo di Lempel-Ziv-Welch).
== Concetto di base ==
[[File:DNA sequence.svg|thumb|upright=0.6|Il DNA può essere visto come sequenza di A, C, G e T]]
<br style="clear: left" />L'input dell'algoritmo di compressione ('''encoder''') e di decompressione ('''decoder''') è costituito da una sequenza finita di simboli ([[Stringa (linguaggi formali)|stringa]]) appartenenti ad un insieme detto alfabeto.<br />Come esempio si immagini di voler archiviare una sequenza di [[DNA]].<br />In generale una porzione di DNA è composta da una ''sequenza'' (finita) di 4 basi azotate: [[Adenina|'''A'''denina]], [[Timina|'''T'''imina]], [[Citosina|'''C'''itosina]] e [[Guanina|'''G'''uanina]].<br />L'alfabeto su cui è costruita una sequenza di DNA è l'insieme:
<br style="clear: left" />
L'input dell'algoritmo di compressione ('''encoder''') e di decompressione ('''decoder''') è costituito da una sequenza finita di simboli ([[Stringa (linguaggi formali)|stringa]]), appartenenti ad un insieme detto alfabeto.<br />
Come esempio, immaginiamo di voler archiviare una sequenza di [[DNA]].<br />
In generale, una parte di DNA è composta da una ''sequenza'' (finita) di 4 tipi di acidi:
'''A'''denina, '''T'''imina, '''C'''itosina e '''G'''uanina.<br />
L'alfabeto, sulla quale è costruita una sequenza di DNA, è l'insieme:
<div style="text-align: center;"><math>\sum = \{ A, C, G, T \}</math></div>
<div style="text-align: center; font-size: 15px">"ACGTACGTACG"</div>
(''inIn realtà non tutte le stringhe così costruite sono valide, infatti esistono alcune "regole" per la combinazione deglidelle acidibasi, qui ignorate per semplificare la trattazione'').
La quantità di memoria necessaria per archiviare una stringa è proporzionale al numero di simboli di cui è composta.<br />Comprimere una stringa significa esprimere la stessa informazione impiegando un numero inferiore di simboli.
Comprimere una stringa, quindi, significa esprimere la stessa informazione impiegando un numero inferiore di simboli.
=== Descrizione LZW ===
Molto spesso la stringa in inputingresso contiene alcune parti ('''sotto-stringhe'''), che si ripetono più volte all'interno della stessa.<br />Ad esempio, esaminando la stringa precedente, possiamo evidenziare le seguenti ripetizioni:
Ad esempio, esaminando la stringa precedente, possiamo evidenziare le seguenti ripetizioni:
<div style="text-align: center; font-size: 15px"><span style="color: red">AC</span><span style="color: blue">GT</span><span style="color: red">AC</span><span style="color: blue">GT</span><span style="color: red">AC</span>G</div>
''(si noti che nonNon 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.<br />Quest'ultimo viene quindi esteso con dei simboli speciali ognuno dei quali rappresenta una particolare sottostringa.
L'idea centrale dell'algoritmo LZW è sfruttare la presenza di queste ripetizioni per la compressione.
È 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.<br />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:
* GT
Queste due sottostringhe saranno "rilevate" dall'algoritmo, che provvederà ad inserirle nel dizionario e ad associarvi due nuovi simboli:
{| class="wikitable"
|}
Le nuove voci vengono aggiunte a quelle già presenti nel dizionario, estendendolo man mano che si avanza con l'elaborazione dell'inputinformazione da comprimere.
Rimpiazzando le sequenze ripetute con i nuovi simboli, otteniamo il seguente risultato:
<div style="text-align: center; font-size: 20px"><math>\sum = \{ A, C, G, T, \alpha_1, \alpha_2 \}</math></div>
L'outputIl 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.
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'inputingresso dell'algoritmo di decompressione ('''decoder''') è perciò una stringa costituita dai dati (simboli A, C, G, T) e dadai codici speciali (simboli <math>\alpha_1</math>, <math>\alpha_2</math>). Compito della decompressione è quello di ricostruire la stringa originale elaborando i dati codificati.
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 ===
|}
L'algoritmo, perPer 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):
(d'ora in avanti chiamata '''buffer''') che verrà modificata/cancellata più volte durante l'esecuzione. Inizialmente il buffer è vuoto (cioè non contiene alcun simbolo).
O''gni riga descrive lo stato dell'algortimo '''prima''' che venga eseguita la relativa iterazione.''
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,
<div style="text-align: center; font-size: 15px">"ACGTACGTACG"</div>
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'')
{| class="wikitable"
|}
A questo punto il buffer contiene una sequenza ''non'' presente nel dizionario. Quando verrà eseguita la terza iterazione, verranno effettuati i seguenti passi:
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: (ottenendonell'esempio A). Si noti che cosìCosì facendo si ottiene una stringa ''contenuta'' nel dizionario.
* QuestaLa sottostringa delA nel buffer (A) viene cercata nel dizionario, mandando in outputuscita 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 (<math>\alpha_1</math>).
* 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:
Di seguito è riportata la tabella con i vari passi eseguiti dall'algoritmo:
<div style="float: left">
{| class="wikitable"
</div>
<br style="clear: both" />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:
<br style="clear: both" />
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:
<div style="float: left">
{| class="wikitable"
</div>
<br style="clear: both" />La stringa codificata risulta ACGT<math>\alpha_1\alpha_3\alpha_5</math>. L'input ACGT ACGT ACG è di 11 simboli, mentre l'output ACGT<math>\alpha_1\alpha_3\alpha_5</math> è di 7 simboli, quindi il rapporto di compressione è:
<br style="clear: both" />
La stringa codificata risulta ACGT<math>\alpha_1\alpha_3\alpha_5</math>.
L'input ACGT ACGT ACG è di 11 simboli, mentre l'output ACGT<math>\alpha_1\alpha_3\alpha_5</math> è di 7 simboli, quindi il rapporto di compressione è:
<math>\left(1 - \frac{7}{11} \right) * 100 \approx 36%</math>
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.<ref>Jacob Ziv and Abraham Lempel; [http://www.cs.duke.edu/courses/spring03/cps296.5/papers/ziv_lempel_1978_variable-rate.pdf ''Compression of Individual Sequences Via Variable-Rate Coding''], IEEE Transactions on Information Theory, September 1978.</ref>
All'aumentare della lunghezza dell'input, tuttavia, il rapporto di compressione tende asintoticamente al massimo.<ref>Jacob Ziv and Abraham Lempel; [http://www.cs.duke.edu/courses/spring03/cps296.5/papers/ziv_lempel_1978_variable-rate.pdf ''Compression of Individual Sequences Via Variable-Rate Coding''], IEEE Transactions on Information Theory, September 1978.</ref>
Di seguito è riportato lo pseudocodice relativo alla compressione. (siSi assume che il dizionario sia già inizializzato con i simboli dell'alfabeto):<code></code>
<code>
buffer = VUOTO
CICLO
buffer = k
FINE SE
FINECICLO</code>
</code>
=== Decompressione ===
Inizialmente il dizionario del decoder è identico a quello dell'encoder (all'inizio del processo di compressione), chee conterràcontiene anch'egliesso solamente voci dei simboli dell'alfabeto.
Quindi, analogamente il dizionario si presenta:
{| class="wikitable"
</div>
<br style="clear: both" />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 <math>\alpha_1</math> coincide nel dizionario con AC, quindi l'econder 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.
<br style="clear: both" />
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 <math>\alpha_1</math> 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 fin quando termina la stringa.
<div style="float: left">
{| class="wikitable"
</div>
<br style="clear: both" />La stringa ottenuta è quindi ACGTACGTACG (11 simboli), che rispetto a quella compressa ACGT<math>\alpha_1\alpha_3\alpha_5</math>(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:<code></code>
<br style="clear: both" />
La stringa ottenuta è quindi ACGTACGTACG (11 simboli), che rispetto a quella compressa ACGT<math>\alpha_1\alpha_3\alpha_5</math>(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; 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:
<code>
LEGGI k
INVIA k
AGGIUNGI buffer + PRIMO CARATTERE DI sottostringa AL DIZIONARIO
buffer = sottostringa
FINE CICLO</code>
<code>
</code>
==== Caso speciale ====
Come accennato prima, vi èEsiste un caso speciale di decompressione:, Cosaquello succedein secui 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
# 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:
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:
<div style="text-align: center; font-size: 15px">"CCC"</div>
Anche questo è un caso speciale nella forma cScSc (e per la precisione cS,. cheIl èprocesso purdi semprecompressione undi derivatoquesta dellastringa formaavviene delregolarmente, casocome speciale).mostrato nella seguente tabella:
Il processo di compressione di tale stringa avviene regolarmente, come è mostrato nella seguente tabella:
<div style="float: left">
{| class="wikitable"
</div>
<br style="clear: both" />La Stringa compressa risulta quindi:
La Stringa compressa risulta quindi:
<div style="text-align: center; font-size: 15px">"C<math>\alpha_1</math>"</div>
Per il processo di decompressione, sorgono i primi problemi, perché come si potrà vedere, mancheràmanca <math>\alpha_1</math> nel dizionario del decoder:
<div style="float: left">
{| class="wikitable"
</div>
<br style="clear: both" />È 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 è <math>\alpha_1</math>=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: <math>\alpha_1</math>=AC+A=ACA.
<br style="clear: both" />
È 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: <math>\alpha_1</math>=AC+A=ACA). Quindi la voce mancate è <math>\alpha_1</math>=CC. Si procede quindi:
Tornando all'esempio:
<div style="float: left">
{| class="wikitable"
</div>
<br style="clear: both" />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:<code></code>
<br style="clear: both" />
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:
<code>
LEGGI k
INVIA k
outuput sottostringa
buffer = sottostringa
FINE CICLO</code>
<code>
</code>
== 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''.
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:
Ad esempio tutti i possibili caratteri di 3 bit (che costituiscono, quindi, ciò che chiamiamo ''alfabeto'') sono:
{| class="wikitable"
|}
Una stringa di '0' e '1' può essere interpretata come un numero naturale scritto in [[Sistema numerico binario|base 2]], ala qualecui spesso si usa fare riferimento in ''[[Sistema numerico decimale|decimale]]''.
Il numero di simboli rappresentabili con ''n'' bit è dato dalla formula <math>2^n</math>. I corrispettivi valori in decimale andranno da <math>0</math> a <math>2^n-1</math>.
I corrispettivi valori in decimale andranno da <math>0</math> a <math>2^n-1</math>.
=== Input ===
I dati in inputingresso 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
Il modo in cui essi vengono interpretati, però, può essere diverso tra le due fasi. Per esempio, la seguente stringa
<pre>010111</pre>
potrebbe essere intesa come due simboli di 3 bit,
oppure tre simboli di 2 bit:
<pre>01 01 11</pre>
È chiaro quindi che l'encoder ede il decoder, per leggere un simbolo, devono stabilire da quanti bit è formato.
==== Input dell'encoder ====
L'inputIl dato in ingresso dell'algoritmo di compressione potrebbe essere, ad esempio:
<pre>010101110100100101001011010010010101000001000101010001000100100101000001</pre>
Una scelta tipica è quella di utilizzare stringhe lunghe 8 bit per rappresentare ciascun carattere. Ciò è dovuto principalmente a due motivi:
* 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 talequesta codifica, che sono <math>2^8=256</math>. Quindi il flusso di bit precedente è da leggere a blocchi di 8 bit:<pre>01010111_01001001_01001011_01001001_01010000_01000101_01000100_01001001_01000001</pre>
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.
In base a quanto detto, allora, il flusso di bit precedente è da leggere a blocchi di 8 bit:
<pre>01010111_01001001_01001011_01001001_01010000_01000101_01000100_01001001_01000001</pre>
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
<pre>WIKIPEDIA</pre>
==== Output dell'encoder/Input del decoder ====
L'output dell'encoder costituisce ciò che il decoder leggeràlegge in input, dunque è indispensabile che le due fasi siano concordi nel modo in cui vengono interpretati i dati.
Come descritto in precedenza, lL'idea fondamentale di LZW è quella di ''estendere'' l'alfabeto iniziale aggiungendo nuovi simboli "speciali", ognuno dei quali potràpuò essere usato nel dizionario.
L'alfabeto esteso dovràdeve comprendere sia i simboli dell'alfabeto iniziale, (nel nostro 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.
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 Nell'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.
Generalmente, per estendere l'alfabeto, bisogna impiegare un numero di bit maggiore per codificare ciascun simbolo.
Nella pubblicazione di [[Terry Welch|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 (<math>2^{12} - 2^{8} = 4096 - 256 = 3840</math>) 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]]:<pre>0100 0001</pre>
nell'alfabeto esteso di 12 bit diventa:
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]]):
<pre>0100 0001</pre>
lo stesso, nell'alfabeto esteso di 12 bit, diventa:
<pre>0000 0100 0001</pre>
Ovviamente, inIn entrambi i casi, la lettera 'A' corrisponde al numero decimale 65.
Ricapitolando,Esiste bisognaquindi fareuna 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).
ComeGli già accennato, tra l'algoritmoalgoritmi di encoding e di decoding devedevono esserciavere unadelle certaconvenzioni concordanzacomuni: il numero di bit per simbolo è uno tra i parametri dacomuni concordati a stabilirepriori.
=== Ordine dei bit ===
Un ulteriore parametro da concordare è l'ordine in cui i bit vengono scritti/letti in memoria.
QuiNell'esempio, conveniamo (in modo analogo alla scrittura dei numeri decimali) che, una stringa binaria vengaviene scritta dalla cifra col peso maggiore ('''MSB''') fino alla cifra col peso minore ('''LSB''') da sinistra verso destra.
<pre>
MSB ---> 100011110100 <--- LSB
</pre>
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
Immaginiamo di dover mandare in output un simbolo di 12 bit
<pre>100011110100</pre>
Comesi giàè accennato,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]]).
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 ====
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:
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:
{| class="wikitable"
==== 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:
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:
{| class="wikitable"
=== Codici a lunghezza variabile ===
I codici a lunghezza variabile sono utilizzati in vari contesti di dati. InPer esempio, 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, (nelldell'ordine dei 16 colori). Per un talequesto 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)bit. Ne è un esempio un flusso di codici che parte da 0 e arriva sino a 10000 (binario):
Un esempio banale potrebbe essere un flusso di codici che parte da 0 e arriva sino a 10000 (binario):
{| class="wikitable"
|}
Se vengono usati i codici a lunghezza variabile, l'encoder ed il decoder devono sincronizzarsisincronizzare nelil 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<sup>p</sup> (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<sup>p</sup>-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).
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<sup>p</sup>(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<sup>p</sup>-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 ====
Le prime implementazioni dell'algoritmo prima incrementano la lunghezza codice e poi inviano il codice per ω, con la conseguenza chequindi ω avesseaveva 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, adper esempio, da Adobe,. alOra puntoAdobe chenei orafile PDF 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, indicandoper quando è utilizzatoindicare 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.
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.
=== RaffinamentiAffinamenti ===
Ulteriori raffinamentiaffinamenti 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. (adAd esempio se in totale l'alfabeto di ogni singolo carattere è 255, il clear code è 256). Il clear code permette di essere reinizializzatoreinizializzare il dizionario, dopo cheuna vienevolta riempitopieno, 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 ilNel precedente esempio, lo stop code sarebbeè 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:
* Quale lunghezza variabile è in uso
* La dimensione del codice iniziale
* QualeQuali clear e stop codescode 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, chee divenne più o meno una 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 metodo,algoritmo o quellimetodi strettamente connessi. È diventato in uso in larga scala dopo che divenne parte del formato [[Graphics Interchange Format|GIF]] nel 1987. È anche facoltativamente usato in file [[Tagged Image File Format|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.
È diventato in uso in larga scala dopo che divenne parte del formato [[Graphics Interchange Format|GIF]] nel 1987. È anche (facoltativamente) usato in file [[Tagged Image File Format|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 ==
* LZMW (1985, by V. Miller, M. Wegman)<ref>David Salomon, ''Data Compression – The complete reference'', 4th ed., page 209</ref> - 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)<ref>David Salomon, ''Data Compression – The complete reference'', 4th ed., page 212</ref> - 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.
| 