Lempel-Ziv-Welch
Da Wikipedia, l'enciclopedia libera.
 |
Questa voce di informatica è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia.
|
 |
In informatica, LZW (acronimo di Lempel-Ziv-Welch, i nomi dei suoi inventori) è un algoritmo che permette la compressione di dati senza perdita di informazioni (lossless). Tale procedimento, ad esempio, è utilizzato nella codifica delle immagini in formato GIF e, facoltativamente, nei file TIFF.
[modifica] Storia
È 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.
[modifica] Descrizione dell'algoritmo
L'algoritmo di compressione costruisce una tabella di traduzione stringhe dal testo da comprimere. La tabella di traduzione stringhe mappa da codici di lunghezza fissata in stringhe. La tabella di stringhe è inizializzata con tutte le stringhe di lunghezza 1 (256 stringhe nel caso di caratteri a 8 bit). Mentre il compressore esamina il testo carattere per carattere, immagazzina ogni stringa distinta di due caratteri nella tabella come una concatenazione di codice/carattere, essendo il codice quello corrispondente al primo carattere. Mentre viene immagazzinata ogni stringa di due caratteri, il primo carattere è messo in output. Ogni volta che una stringa incontrata precendentemente è letta dall'input, si determina la più lunga stringa incontrata precedentemente, e quindi il codice di quest'ultima concatenato con il carattere d'estensione (il carattere successivo nell'input) viene memorizzato nella tabella. Il codice per questa stringa (la più lunga precedentemente incontrata) è messo in output e il carattere d'estensione è usato come inizio della stringa successiva.
L'algoritmo di decompressione richiede solo il testo compresso come input, dal momento che può costruire una string table identica dal testo compresso mentre lo ricrea dal testo originale. Comunque, può manifestarsi un caso anormale ogni volta che la sequenza C/S/C/S/C ( con lo stesso carattere per ogni C e la stessa stringa per ogni S) viene incontrata nell'input e C/S è già stata immagazzinata nella tabella di stringhe. Quando il decompressore legge il codice C/S/C nell'input, non può decodificarlo dal momento che non ha ancora immagazzinato questo codice nella tabella. Questo caso speciale può essere aggirato perché il decompressore sa che il carattere d'estensione è il carattere precedentemente incontrato.
