Diodati.org - Accessibilità e traduzioni dal W3C

Sponsor ufficiale di Diodati.org: Hosting a partire da 25 euro/anno | Domini a partire da 10,79 euro/anno | Server dedicati a partire da 120 euro/mese

L'algoritmo non distruttivo che va sotto il nome di LZW è il risultato delle modifiche apportate nel 1984 da Terry Welch ai due algoritmi sviluppati nel 1977 e nel 1978 da Jacob Ziv e Abraham Lempel, e chiamati rispettivamente LZ77 e LZ78.

Il funzionamento di questo metodo è molto semplice: viene creato un dizionario delle stringhe di simboli ricorrenti nel file, costruito in modo tale che ad ogni nuovo termine aggiunto al dizionario sia accoppiata in modo esclusivo un'unica stringa. Esiste un dizionario di partenza costituito dai 256 simboli del codice ASCII, che viene incrementato con l'aggiunta di tutte le stringhe ricorrenti nel file, che siano maggiori di un carattere. Ciò che viene memorizzato nel file compresso è un codice breve che rappresenta in modo inequivocabile la stringa inserita nel dizionario così creato.

Esiste, naturalmente, un insieme di regole non ambigue per la codifica del dizionario, che permetterà in seguito al sistema di decompressione di generare un dizionario esattamente uguale a quello di partenza, in modo tale da poter effettuare l'operazione inversa a quella di compressione, consistente nella sostituzione del codice compresso con la stringa originale. La reversibilità completa e precisa dell'operazione è indispensabile al fine di riottenere l'esatto contenuto del file originale.

Il risparmio di spazio in un file compresso con LZW dipende dal fatto che il numero di bit necessari a codificare il "termine" che rappresenta una stringa nel dizionario è inferiore al numero di bit necessari a scrivere nel file non compresso tutti i caratteri che compongono la stringa. Quanto più numerose e lunghe sono le stringhe che è possibile inserire nel dizionario, tanto maggiore sarà il coefficiente di compressione del file. I formati grafici più noti che utilizzano l'algoritmo LZW sono il TIFF e il GIF. Esso è utilizzato anche dallo standard V.42bis, implementato su tutti i modem di ultima generazione come uno dei protocolli per la trasmissione di dati compressi.

Per avere una dimostrazione pratica di come funziona questo tipo di codifica per mezzo di dizionari di simboli, potete collegarvi su Internet alla pagina http://www.cs.sfu.ca/CC/365/li/squeeze/LZW.html, dalla quale è possibile accedere ad una interessante applet java. La sua interfaccia, molto intuitiva, vi consentirà di effettuare in prima persona una codifica di stringhe di testo con LZW, verificando direttamente la creazione del dizionario, la sua ricostruzione in un'altra finestra ed il coefficiente finale di compressione ottenuto. 

Fig. 4 – Il medesimo dizionario creato in fase di compressione viene generato durante la decompressione del file