Visualizza wikitesto di Lempel-Ziv-Welch

{{w|informatica|agosto 2011}}
{{Formato file
| nome = LZW
| logo =
| icona =
| immagine =
| didascalia =
| estensione =
| mime =
| typecode =
| sviluppatore = [[Abraham Lempel]], [[Jacob Ziv]], [[Terry Welch]]
| proprietario =
| licenza =
| data_pubblicazione =
| ultima_versione =
| data_ultima_versione =
| genere = [[Compressione dei dati]]
| compressione = [[Compressione dati senza perdita|Lossless]]
| estensione_di =
| esteso_a =
| standard =
| aperto =
| sito =
}}

'''Lempel-Ziv-Welch''' (abbreviato '''LZW''') è un [[algoritmo]] utilizzato in [[informatica]] per la [[compressione dati]] senza perdita di informazioni ([[Compressione dati lossless|lossless]]). Per esempio questo algoritmo è utilizzato nella [[codifica]] delle [[immagine digitale|immagini]] in formato [[Graphics Interchange Format|GIF]] e facoltativamente nei file [[Tagged Image File Format|TIFF]].

== Storia ==
<div style="display: inline; float: right">
<gallery>
Immagine:Abraham Lempel.JPG|[[Abraham Lempel]]
Immagine:Jacob Ziv.jpeg|[[Jacob Ziv]]
</gallery>
</div>
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.&nbsp;8–19.</ref> 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 ===
[[File:DNA sequence.svg|thumb|upright=0.6|Il DNA può essere visto come sequenza di A, C, G e T]]
{{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:

<div style="text-align: center;"><math>\sum = \{ A, C, G, T \}</math></div>

Una stringa sull'alfabeto <math>\sum</math> è costituita da una qualunque sequenza finita di A, C, G e T, ad esempio:

<div style="text-align: center; font-size: 15px">"ACGTACGTACG"</div>

''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.<br />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.<br />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>
''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:

{| class="wikitable"
!colspan="2"|Dizionario
|-
! Sequenza !! Simbolo
|-
| AC || <math>\alpha_1</math>
|-
| GT || <math>\alpha_2</math>
|}

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:
<div style="text-align: center; font-size: 15px"><math>\alpha_1</math><math>\alpha_2</math><math>\alpha_1</math><math>\alpha_2</math><math>\alpha_1</math>G</div>
La nuova stringa è costruita su un{{'}}''estensione'' dell'alfabeto iniziale, precisamente:
<div style="text-align: center; font-size: 20px"><math>\sum = \{ A, C, G, T, \alpha_1, \alpha_2 \}</math></div>

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 <math>\alpha_1</math>, <math>\alpha_2</math>). 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:

{| class="wikitable"
!colspan="2"|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):

O''gni riga descrive lo stato dell'algoritmo '''prima''' che venga eseguita la relativa iterazione.''

{| class="wikitable"
! Iterazione !! Input !! Buffer corrente !! Simbolo in output !! Voce aggiunta nel dizionario
|-
| 1 || ACGTACGTACG || (vuoto) || (nessuno) || (nessuna)
|-
| 2 || <span style="background-color: yellow">A</span>CGTACGTACG || A || || 
|-
| 3 || <span style="background-color: yellow">AC</span>GTACGTACG || 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 (<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:
<div style="float: left">
{| class="wikitable"
! Iterazione !! Input !! Buffer corrente !! Simbolo in output !! Voce aggiunta nel dizionario
|-
| 4 || A<span style="background-color: yellow">C</span>GTACGTACG || C || A || AC ((<math>\alpha_1</math>))
|-
| 5 || A<span style="background-color: yellow">CG</span>TACGTACG || CG || || 
|-
| 6 || AC<span style="background-color: yellow">G</span>TACGTACG || G || C || CG ((<math>\alpha_2</math>))
|-
| 7 || AC<span style="background-color: yellow">GT</span>ACGTACG || GT || || 
|-
| 8 || ACG<span style="background-color: yellow">T</span>ACGTACG || T || G || GT ((<math>\alpha_3</math>))
|-
| 9 || ACG<span style="background-color: yellow">TA</span>CGTACG || TA || || 
|-
| 10 || ACGT<span style="background-color: yellow">A</span>CGTACG || A || T || TA ((<math>\alpha_4</math>))
|}
</div>

<div style="float: right; clear: right">
{| class="wikitable"
!colspan="2"|Dizionario
|-
! Sequenza !! Codice
|-
| A || A
|-
| C || C
|-
| G || G
|-
| T || T
|-
| AC || <math>\alpha_1</math>
|-
| CG || <math>\alpha_2</math>
|-
| GT || <math>\alpha_3</math>
|-
| TA || <math>\alpha_4</math>
|}
</div>
{{clear}}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"
! Iterazione !! Input !! Buffer corrente !! Simbolo in output !! Voce aggiunta nel dizionario
|-
| 11 || ACGT<span style="background-color: yellow">AC</span>GTACG || AC || || 
|-
| 12 || ACGT<span style="background-color: yellow">ACG</span>TACG || ACG || || 
|-
| 13 || ACGTAC<span style="background-color: yellow">G</span>TACG || G || <math>\alpha_1</math>
 || ACG ((<math>\alpha_5</math>))
|-
| 14 || ACGTAC<span style="background-color: yellow">GT</span>ACG || GT || || 
|-
| 15 || ACGTAC<span style="background-color: yellow">GTA</span>CG || GTA || || 
|-
| 16 || ACGTACGT<span style="background-color: yellow">A</span>CG || A || <math>\alpha_3</math> || GTA ((<math>\alpha_6</math>))
|-
| 17 || ACGTACGT<span style="background-color: yellow">AC</span>G || AC || || 
|-
| 18 || ACGTACGT<span style="background-color: yellow">ACG</span> || ACG || || 
|-
| 19 || ACGTACGTACG || || <math>\alpha_5</math> || 
|}
</div>

<div style="float: right; clear: right">
{| class="wikitable"
!colspan="2"|Dizionario
|-
! Sequenza !! Codice
|-
| A || A
|-
| C || C
|-
| G || G
|-
| T || T
|-
| AC || <math>\alpha_1</math>
|-
| CG || <math>\alpha_2</math>
|-
| GT || <math>\alpha_3</math>
|-
| TA || <math>\alpha_4</math>
|-
| ACG || <math>\alpha_5</math>
|-
| GTA || <math>\alpha_6</math>
|}
</div>
{{clear}}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''] {{Webarchive|url=https://web.archive.org/web/20120412115357/http://www.cs.duke.edu/courses/spring03/cps296.5/papers/ziv_lempel_1978_variable-rate.pdf |date=12 aprile 2012 }}, IEEE Transactions on Information Theory, September 1978.</ref>

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:

{| class="wikitable"
!colspan="2"|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:

<div style="text-align: center; font-size: 15px">ACGT<math>\alpha_1\alpha_3\alpha_5</math></div>

Le iterazioni sono le seguenti:
<div style="float: left">
{| class="wikitable"
! Iterazione !! Input !! Buffer corrente !! Congettura !! Simbolo in output !! Voce aggiunta nel dizionario !! Conversione
|-
| 1 || ACGT<math>\alpha_1\alpha_3\alpha_5</math> || (vuoto) || || (nessuno) || (nessuna) || 
|-
| 2 || <span style="background-color: yellow">A</span>CGT<math>\alpha_1\alpha_3\alpha_5</math> || A || A+? || A || || 
 |-
| 3 || <span style="background-color: yellow">AC</span>GT<math>\alpha_1\alpha_3\alpha_5</math> || C || C+? || C || AC ((<math>\alpha_1</math>)) || 
|-
| 4 || A<span style="background-color: yellow">CG</span>T<math>\alpha_1\alpha_3\alpha_5</math> || G || G+? || G || CG ((<math>\alpha_2</math>)) || 
|-
| 5 || AC<span style="background-color: yellow">GT</span><math>\alpha_1\alpha_3\alpha_5</math> || T || T+? || T || GT ((<math>\alpha_3</math>)) || 
|}
</div>

<div style="float: right; clear: right">
{| class="wikitable"
!colspan="2"|Dizionario
|-
! Sequenza !! Codice
|-
| A || A
|-
| C || C
|-
| G || G
|-
| T || T
|-
| AC || <math>\alpha_1</math>
|-
| CG || <math>\alpha_2</math>
|-
| GT || <math>\alpha_3</math>
|}
</div>
{{clear}}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'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.
<div style="float: left">
{| class="wikitable"
! Iterazione !! Input !! Buffer corrente !! Congettura !! Simbolo in output !! Voce aggiunta nel dizionario !! Conversione
|-
| 6 || ACG<span style="background-color: yellow">T<math>\alpha_1</math></span><math>\alpha_3\alpha_5</math> || AC || AC+? || AC || TA ((<math>\alpha_4</math>)) || <math>\alpha_1</math>=AC
|-
| 7 || ACGT<span style="background-color: yellow"><math>\alpha_1\alpha_3</math></span><math>\alpha_5</math> || ACG || GT+? || GT || ACG((<math>\alpha_5</math>)) || <math>\alpha_3</math>=GT
|-
| 8 || ACGT<math>\alpha_1</math><span style="background-color: yellow"><math>\alpha_3\alpha_5</math></span> || GTA || ACG+? || ACG || GTA((<math>\alpha_6</math>)) || <math>\alpha_5</math>=ACG
|-
| 9 || ACGT<math>\alpha_1</math><math>\alpha_3\alpha_5</math> || || || || || 
|}
</div>

<div style="float: right; clear: right">
{| class="wikitable"
!colspan="2"|Dizionario
|-
! Sequenza !! Codice
|-
| A || A
|-
| C || C
|-
| G || G
|-
| T || T
|-
| AC || <math>\alpha_1</math>
|-
| CG || <math>\alpha_2</math>
|-
| GT || <math>\alpha_3</math>
|-
| TA || <math>\alpha_4</math>
|-
| ACG || <math>\alpha_5</math>
|-
| GTA || <math>\alpha_6</math>
|}
</div>
{{clear}}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:

 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:

# Il decoder legge X=C e poi Z=alpha1
# Conosce la sequenza di X e Z identificati con Y + alcune ω sequenze sconosciute
# Il decoder sa che Z è stato aggiunto nel dizionario dell'encoder per Y+qualche carattere sconosciuto "?"
# Conosce che "?" è la prima lettera di ω
# La prima lettera di ω=Y+? deve essere anche la prima lettera di Y
# ω deve essere quindi Y+x, dove x è la prima lettera di Y(x=?)
# Ciò implica che Z=ω=Y+x
# Trovato Z, questo viene inserito nel dizionario
# 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:
<div style="text-align: center; font-size: 15px">"CCC"</div>
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:
<div style="float: left">
{| class="wikitable"
! Iterazione !! Input !! Buffer corrente !! Simbolo in output !! Voce aggiunta nel dizionario
|-
| 1 || CCC || (vuoto) || (nessuno) || (nessuna)
|-
| 2 || <span style="background-color: yellow">C</span>CC || C || || 
|-
| 3 || <span style="background-color: yellow">CC</span>C || CC || || 
|-
| 4 || C<span style="background-color: yellow">C</span>C || C || C || CC ((<math>\alpha_1</math>))
|-
| 5 || C<span style="background-color: yellow">CC</span> || CC || || 
|-
| 6 || CCC || || <math>\alpha_1</math> || 
|}
</div>

<div style="float: right; clear: right">
{| class="wikitable"
!colspan="2"|Dizionario
|-
! Sequenza !! Codice
|-
| C || C
|-
| CC || <math>\alpha_1</math>
|}
</div>
{{clear}}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é manca <math>\alpha_1</math> nel dizionario del decoder:
<div style="float: left">
{| class="wikitable"
! Iterazione !! Input !! Buffer corrente !! Congettura !! Simbolo in output !! Voce aggiunta nel dizionario !! Conversione
|-
| 1 || C<math>\alpha_1</math> || (vuoto) || || (nessuno) || (nessuna) || 
|-
| 2 || <span style="background-color: yellow">C</span><math>\alpha_1</math> || C || C+? || C || || 
|-
| 3 || <span style="background-color: yellow">C<math>\alpha_1</math></span> || || || || || <math>\alpha_1</math>=???
|}
</div>

<div style="float: right; clear: right">
{| class="wikitable"
!colspan="2"|Dizionario
|-
! Sequenza !! Codice
|-
| C || C
|}
</div>
{{clear}}È 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.

Tornando all'esempio:
<div style="float: left">
{| class="wikitable"
! Iterazione !! Input !! Buffer corrente !! Primo carattere !! Congettura !! Simbolo in output !! Voce aggiunta nel dizionario !! Conversione
|-
| 1 || C<math>\alpha_1</math> || (vuoto) || || || (nessuno) || (nessuna) || 
|-
| 2 || <span style="background-color: yellow">C</span><math>\alpha_1</math> || C || || C+? || C || || 
|-
| 3 || <span style="background-color: red">C</span><math>\alpha_1</math> || C || C || || || CC ((<math>\alpha_1</math>)) || 
|-
| 4 || <span style="background-color: yellow">C<math>\alpha_1</math></span> || CC || || CC+? || CC || || <math>\alpha_1</math>=CC
|}
</div>

<div style="float: right; clear: right">
{| class="wikitable"
!colspan="2"|Dizionario
|-
! Sequenza !! Codice
|-
| C || C
|-
| CC || <math>\alpha_1</math>
|}
</div>
{{clear}}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:

{| class="wikitable"
!colspan="2"|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 [[Sistema numerico binario|base 2]] a cui 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>.

=== 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
<pre>010111</pre>
potrebbe essere intesa come due simboli di 3 bit,
<pre>010 111</pre>
oppure tre simboli di 2 bit:
<pre>01 01 11</pre>
È 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:
<pre>010101110100100101001011010010010101000001000101010001000100100101000001</pre>
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 [[8 bit|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 <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.
<pre>WIKIPEDIA</pre>

==== 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 [[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. 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:
<pre>0000 0100 0001</pre>
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 ===
{{vedi anche|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.
<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
<pre>100011110100</pre>
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 [[Graphics Interchange Format|GIF]] usano '''LSB-First''', mentre i file [[Tagged Image File Format|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:

{| class="wikitable"
!colspan="2"|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:

{| class="wikitable"
!colspan="2"|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):

{| class="wikitable"
|-
! 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<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).

==== 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 [[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.

== 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.

== Note ==

<references/>
== Voci correlate ==

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

== Altri progetti ==
{{interprogetto}}

== Collegamenti esterni ==
* {{Collegamenti esterni}}
* {{cita web | 1 = http://projects.hudecof.net/diplomovka/online/ucebnica/applets/AppletLZW.html | 2 = Un applet JAVA che mostra passo passo il processo di compressione/decompressione di una stringa. | accesso = 2 marzo 2010 | urlarchivio = https://web.archive.org/web/20100107055136/http://projects.hudecof.net/diplomovka/online/ucebnica/applets/AppletLZW.html | dataarchivio = 7 gennaio 2010 | urlmorto = sì }}
* Welch, T.A., [http://www.cs.duke.edu/courses/spring03/cps296.5/papers/welch_1984_technique_for.pdf A Technique for High-Performance Data Compression] {{Webarchive|url=https://web.archive.org/web/20190530042731/https://www2.cs.duke.edu/courses/spring03/cps296.5/papers/welch_1984_technique_for.pdf |date=30 maggio 2019 }}, Computer, vol. 17, no. 6, pp.&nbsp;8–19, June 1984 (Link alternativo).
* {{en}}&nbsp;– [http://marknelson.us/1989/10/01/lzw-data-compression/ Un articolo sulla compressione LZW.] {{Webarchive|url=https://web.archive.org/web/20100222084753/http://marknelson.us/1989/10/01/lzw-data-compression |date=22 febbraio 2010 }}
* {{cita web|http://www.oldwildweb.com/implementazione-lzw-c-ugo-cirmignani.html|Un'implementazione ottimizzata in C++ dell'algoritmo di LZW, sorgenti e articolo dell'autore.}}
* {{US patent|4558302}}, Terry A. Welch, ''High speed data compression and decompression apparatus and method''

{{Portale|informatica}}

[[Categoria:Algoritmi di compressione]]
[[Categoria:Compressione dei dati]]
[[Categoria:Teoria dei codici]]