LZ77 e LZ78
L'LZ77 e LZ78 sono un algoritmi di compressione lossless (senza perdita di informazioni) pubblicati da Abraham Lempel e Jacob Ziv rispettivamente nel 1977 e nel 1978. Questi algortmi 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 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
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 rializzata da Terry Welch nel 1984 ed utilizzata nei file grafici GIF.