Lempel-Ziv-Welch: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
m WPCleaner v2.0 - Fixed using Wikipedia:Check Wikipedia (Tag HTML con sintassi errata)
Luigi923 (discussione | contributi)
Nessun oggetto della modifica
Riga 24:
}}
 
In'''Lempel-Ziv-Welch''' [[informatica]],(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]].
 
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.
 
== Storia ==
 
<div style="display: inline; float: right">
<gallery>
Line 47 ⟶ 39:
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.
 
== Concetto di baseDescrizione ==
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 ===
 
=== 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:
Line 64 ⟶ 61:
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.
 
=== Descrizionela LZWstruttura ===
 
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.<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:
Line 103 ⟶ 99:
 
=== Compressione ===
 
Come primo passo nel dizionario vengono inseriti tutti i simboli dell'alfabeto, utilizzando gli stessi come codici speciali.
 
Line 721 ⟶ 716:
 
== Collegamenti esterni ==
 
* {{cita web|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.}}
* 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], Computer, vol. 17, no. 6, pp.&nbsp;8–19, June 1984 (Link alternativo).