LZW, un famoso algoritmo per la compressione dei dati

LZW è il nome di un importante algoritmo per la compressione dati che sfrutta la ripetizione di gruppi di elementi. Prende il nome dai suoi inventori, Abraham Lempel, Jacob Ziv e Terry Welch, che svilupparono un algoritmo senza perdita di informazioni (lossless).

Questa tecnica viene spesso utilizzata nella codifica delle immagini in formato GIF e, opzionalmente, nei file TIFF. Per quanto riguarda i file di tipo testo, LZW sfrutta la ripetizione di gruppi di caratteri o frasi, spesso nelle stringhe ci sono sotto-stringhe che si ripetono più volte. Il funzionamento è del tipo:

  1. Leggi in input una frase.
  2. La frase letta si trova nel dizionario?
  3. SI, restituisci in output il codice associato alla frase;
  4. NO, Inserisci la frase nel dizionario, associagli un codice e restituisci questo codice in output.

ABCDABCDE
In questa stringa di caratteri le sequenze che si ripetono sono AB e CD, percui l'algoritmo assocerà dei simboli alle ripetizioni AB, CD, ma anche a BC, DA, ABC, ecc.

Durante la fase di decompressione l’algoritmo sfrutterà il dizionario appena creato per riassociare a tutti i simboli il loro valore originario.

LZW è un algoritmo molto generico per cui non ha un ottimo fattore di compressione. I risultati migliori si ottengono con input di testo con molte ripetizioni come nei linguaggi naturali (inglese, italiano, ecc.).

Pubblicato in Informatica, Programmazione, Sistemi Informativi Taggato con: , , , , , , , ,

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

*