LZ77 e LZ78

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica sorgente]

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 che 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.

LZ78[modifica | modifica sorgente]

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

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

Collegamenti esterni[modifica | modifica sorgente]

Voci correlate[modifica | modifica sorgente]

informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica