LZ77 e LZ78

L'LZ77 e LZ78 sono algoritmi di compressione lossless (senza perdita di informazioni) pubblicati da Abraham Lempel e Jacob Ziv rispettivamente nel 1977 e nel 1978. Questi algoritmi sono alla base di molte varianti come LZW o LZSS.

Il metodo trova impiego della compressione di dati eterogenei, testi o immagini, e non necessita di informazioni a priori sui dati da comprimere.

LZ77

La compressione avviene per sostituzione di parti di dati con altre già processate. Nel caso l'algoritmo di codifica incontri un dato ripetuto, questo viene sostituito con un puntatore di lunghezza-distanza che indica essenzialmente di copiare una certa lunghezza di dati da una determinata distanza.

Sia l'algoritmo di codifica sia quello di decodifica devono tenere traccia di una certa quantità di dati incontrati. Questa viene in genere chiamata finestra e per questa l'LZ77 viene anche denominato compressione a finestra.

Sulla base di questo algoritmo è stata implementata da IBM la tecnologia Memory eXpansion Technology (MXT).

LZ78

La compressione avviene in modo simile all'LZ77, ma in questo caso si realizza un dizionario delle parti di dati già incontrati. L'algoritmo di codifica sostituisce i dati già presenti nel dizionario con un riferimento ad essi.

Per i primi decenni dalla sua introduzione è stato coperto da brevetti negli Stati Uniti che ne hanno pregiudicato il largo utilizzo, benché fosse popolare sin dalla sua apparizione. La forma più popolare di compressione LZ78 rimane LZW, una variante realizzata da Terry Welch nel 1984 ed utilizzata nei file grafici GIF.

Voci correlate

• Compressione dati senza perdita
• Compressione dati lossy
• Compressione dei dati
• Memory eXpansion Technology

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su LZ77 e LZ78

Collegamenti esterni

• Un'implementazione in C dell'algoritmo LZSS, sorgenti e articolo dell'autore., su oldwildweb.com.