Utente:XDnl/Sandbox: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
m fix errore di Lint - Tag di chiusura mancante
 
(16 versioni intermedie di 6 utenti non mostrate)
Riga 1:
<nowiki>{{S|informatica}}</nowiki>
 
{{Compressione |
Riga 234:
La stringa codificata risulta ACGT<math>\alpha_1\alpha_3\alpha_5</math>.
L'input ACGT ACGT ACG è di 12 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}{12} \right) * 100 \approx 42\%</math>
 
Da questo esempio si evince che per ottenere una buona compressione, è necessario che i dati in input contengano numerose ripetizioni.
Riga 240:
 
Di seguito è riportato lo pseudocodice relativo alla compressione (si assume che il dizionario sia già inizializzato con i simboli dell'alfabeto):
 
<code>
buffer = VUOTO
CICLO
Riga 254:
FINE SE
FINECICLO
</code>
 
===Decompressione===
Riga 364 ⟶ 363:
La stringa ottenuta è quindi ACGTACGTACG (12 simboli), che rispetto a quella compressa ACGT<math>\alpha_1\alpha_3\alpha_5</math>(7 simboli), presenta 5 simboli in più (12-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
Riga 376 ⟶ 375:
FINE CICLO
 
</code>
====Caso speciale====
Come accennato prima, vi è un caso speciale di decompressione: Cosa succede se 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:
Riga 421 ⟶ 419:
| CC || <math>\alpha_1</math>
|}
</div>
<br style="clear:both" />
La Stringa compressa risulta quindi:
<div style="text-align:center;font-size:15px">"C<math>\alpha_1</math>"</div>
<p>Per il processo di decompressione, sorgono i primi problemi, perchè come si potrà vedere, mancherà <math>\alpha_1</math> nel dizionario del decoder:</p>
<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>
<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>\alpha1</math>=AC+A=ACA). Quindi la voce mancate è <math>\alpha_1</math>=CC. Si procede quindi:
<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>
<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:
 
LEGGI k
==Implementazione==
INVIA k
===Premesse===
buffer = k
===Algoritmo===
CICLO
==Applicazioni==
LEGGI codice
==Varianti==
SE codice È PRESENTE NEL DIZIONARIO
== Brevetti ==
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. <br />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.<br />Ad esempio tutti i possibili caratteri di 3 bit (che costituiscono, quindi, ciò che chiamiamo ''alfabeto'') 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]], al quale spesso si usa fare riferimento in [[Sistema_numerico_decimale|''decimale'']].<br/>
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 input di entrambe le fasi ('''encoding''' e '''decoding''') sono sostanzialmente un flusso di bit di lunghezza qualsiasi.<br /> 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,
<pre>010 111</pre>
oppure tre simboli di 2 bit:
<pre>01 01 11</pre>
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:
<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 tale codifica, che sono <math>2^8=256</math>.
 
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à 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".<br/> 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 [[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.<br/>
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, 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==
{{vedi anche|Ordine dei bit}}
Un ulteriore parametro da concordare è l'ordine in cui i bit vengono scritti/letti in memoria.<br />
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.
<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.
Immaginiamo di dover mandare in output un simbolo di 12 bit
<pre>100011110100</pre>
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]]).<br/>
Per questo motivo non è possibile scrivere direttamente 12 bit, ma si è costretti a mandare in output una stringa lunga 16 bit (2 byte).<br/>
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:
{| 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 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"
!colspan="2"|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):
{| class="wikitable"
|-
! 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<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 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:
Vari [[Brevetto|brevetti]] sono sono stati rilasciati negli [[USA]] ed in altri paesi per LZW ed algoritmi similari.
*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.
 
=Applicazioni=
<!-- LZ78 was covered by {{US patent|4464650}} by Lempel, Ziv, Cohn, and Eastman, assigned to [[Sperry Corporation]], later [[Unisys]] Corporation, filed on August 10, 1981. Two US patents were issued for the LZW algorithm: {{US patent|4814746}} by [[Victor S. Miller]] and Mark N. Wegman and assigned to [[International Business Machines|IBM]], originally filed on June 1, 1983, and {{US patent|4558302}} by Welch, assigned to Sperry Corporation, later Unisys Corporation, filed on June 20, 1983. On June 20, 2003, this patent on the LZW algorithm expired [http://www.unisys.com/about__unisys/lzw].
Il metodo divenne ampiamente usato in programmi di compressione, che divenne più o meno una 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, o quelli strettamente connessi.
È diventato in uso in larga scala dopo che divenne parte del formato GIF nel 1987. È anche (facoltativamente) usato in file 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=
US Patent 4,558,302 received a lot of negative press after LZW compression was used in the GIF image format (see [[Graphics Interchange Format#Unisys and LZW patent enforcement]]). -->
*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 corrispondeze 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.
 
==Bibliografia==
<references/>
 
==Voci correlate==
* [[lossless|Compressione lossless]]
* [[LZ77]]
Riga 448 ⟶ 700:
* [[TIFF]]
 
==Collegamenti esterni==
 
* [http://projects.hudecof.net/diplomovka/online/ucebnica/applets/AppletLZW.html Un applet JAVA che mostra passo passo il processo di compressione/decompressione di una stringa.]
Riga 460 ⟶ 712:
{{Portale|informatica}}
 
<nowiki>[[Categoria:Algoritmi di compressione]]</nowiki>
<nowiki>[[Categoria:Compressione dati]]</nowiki>
 
[[ar:ال زد دابليو]]