Utente:XDnl/Sandbox: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m fix errore di Lint - Tag di chiusura mancante |
|||
| (9 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):
buffer = VUOTO
CICLO
Riga 254:
FINE SE
FINECICLO
===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:
LEGGI k
INVIA k
Riga 376 ⟶ 375:
FINE CICLO
====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 425 ⟶ 423:
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>▼
▲Per il processo di decompressione, sorgono i primi problemi, perchè come si potrà vedere, mancherà <math>\alpha_1</math> nel dizionario del decoder:
<div style="float:left">
{| class="wikitable"
Riga 475 ⟶ 472:
<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
INVIA k
Riga 492 ⟶ 489:
buffer = sottostringa
FINE CICLO
=Implementazione=
Riga 681 ⟶ 676:
Molti formati che impiegano l'LZW costruiscono queste informazioni in specifici formati oppure forniscono campi espliciti nell'intestazione della compressione.
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.
==Varianti==▼
È 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.
*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.
<references/>
Riga 704 ⟶ 700:
* [[TIFF]]
* [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 716 ⟶ 712:
{{Portale|informatica}}
<nowiki>[[Categoria:Algoritmi di compressione]]</nowiki>
<nowiki>[[Categoria:Compressione dati]]</nowiki>
[[ar:ال زد دابليو]]
| |||