Utente:XDnl/Sandbox prova

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 tutti i possibili caratteri di 3 bit (che costituiscono, quindi, ciò che chiamiamo alfabeto) sono:

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 base 2, al quale spesso si usa fare riferimento in decimale.
Il numero di simboli rappresentabili con n bit è dato dalla formula $2^{n}$. I corrispettivi valori in decimale andranno da $0$ a $2^{n}-1$.

Input

I dati in input di entrambe le fasi (encoding e decoding) sono sostanzialmente un flusso di bit di lunghezza qualsiasi.
Il modo in cui essi vengono interpretati, però, può essere diverso tra le due fasi. Per esempio, la seguente stringa

010111

potrebbe essere intesa come due simboli di 3 bit,

010 111

oppure tre simboli di 2 bit:

01 01 11

E' chiaro quindi che l'encoder ed il decoder, per leggere un simbolo, devono stabilire da quanti bit è formato.

Input dell'encoder

L'input dell'algoritmo di compressione potrebbe essere, ad esempio:

010101110100100101001011010010010101000001000101010001000100100101000001

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 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 tale codifica, che sono $2^{8}=256$.

In base a quanto detto, allora, il flusso di bit precedente è da leggere a blocchi di 8 bit:

01010111_01001001_01001011_01001001_01010000_01000101_01000100_01001001_01000001

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

WIKIPEDIA

Output dell'encoder/Input del decoder

L'output dell'encoder costituisce ciò che il decoder leggerà in input, dunque è indispensabile che le due fasi siano concordi nel modo in cui vengono interpretati i dati.

Come descritto in precedenza, l'idea fondamentale di LZW è quella di estendere l'alfabeto iniziale aggiungendo nuovi simboli "speciali", ognuno dei quali potrà essere usato nel dizionario.

L'alfabeto esteso dovrà comprendere sia i simboli dell'alfabeto iniziale (nel nostro esempio quelli della codifica ASCII) sia simboli "speciali".
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 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.

Nella pubblicazione di 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 ($2^{12}-2^{8}=4096-256=3840$) 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 chiarire meglio il concetto, consideriamo il simbolo "A" ad 8 bit (secondo la codifica ASCII):

0100 0001

lo stesso, nell'alfabeto esteso di 12 bit, diventa:

0000 0100 0001

Ovviamente, in entrambi i casi, la lettera 'A' corrisponde al numero decimale 65.

Ricapitolando, bisogna fare 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).

Come già accennato, tra l'algoritmo di encoding e di decoding deve esserci una certa concordanza: il numero di bit per simbolo è uno tra i parametri da stabilire.

Ordine dei bit

Un ulteriore parametro da concordare è l'ordine in cui i bit vengono scritti/letti in memoria.
Qui conveniamo (in modo analogo alla scrittura dei numeri decimali) che una stringa binaria venga scritta dalla cifra col peso maggiore (MSB) fino alla cifra col peso minore (LSB) da sinistra verso destra.

MSB ---> 100011110100 <--- LSB

Implementare l'algoritmo LZW presenta la necessità (specialmente per i simboli dell'alfabeto esteso) di lavorare con stringhe di lunghezza qualsiasi. Immaginiamo di dover mandare in output un simbolo di 12 bit

100011110100

Come già accennato, 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 ("Least Significant Bit First", bit meno significativo prima).
• MSB-First ("Most Significant Bit First", bit più significativo prima).

I file GIF usano LSB-First, mentre i file 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 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:

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

Byte in output
Primo byte	Secondo byte
10001111	01000000

Codici a lunghezza variabile

I codici a lunghezza variabilie sono utilizzati in vari contesti di dati. 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 (nell'ordine dei 16 colori). Per un tale 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). Un esempio banale potrebbe essere un flusso di codici che parte da 0 e arriva sino a 10000 (binario):

Codice in bit	Numero di bits
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 sincronizzarsi nel 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 si incontra una sequenza ω che non è presente nel dizionario (quindi il codice deve essere aggiunto) ma il successivo codice disponibile nel dizionario è lungo 2^p(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^p-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 che ω avesse 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 ha causato molta confusione nell'ambito di file gestiti, ad esempio, da Adobe, al punto che ora 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, indicando quando è utilizzato 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 che il decoder cambiano la lunghezza codice solo dopo che il "clear code" ritorna alla lunghezza iniziale.

Raffinamenti

Ulteriori raffinamenti 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 essere reinizializzato il dizionario, dopo che viene riempito, 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 il precedente esempio, lo stop code sarebbe 257).

Alcuni encoder sviluppati possono monitorare l'efficenza 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
• Quale clear e stop codes 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.