Addio ai padri degli algoritmi di compressione moderni: Jacob Ziv e Abraham Lempel

Oggi tutti conosciamo a cosa servono e l’importanza degli algoritmi di compressione lossy e lossless.
La compressione lossy è impiegata nel caso dei flussi multimediali e si basa sulla rimozione di informazioni che generalmente non impattano molto sulla qualità del video (lossy significa “con perdite”) e che permettono di avere file più leggeri da memorizzare e gestire oltre a un impegno della banda di rete nettamente inferiore.

Nel caso dei noti formati come Zip, 7-Zip, RAR e così via non possono essere ovviamente introdotte perdite altrimenti verrebbe meno l’integrità stessa dei dati: per questo si parla sempre, qui, di algoritmi di compressione lossless.

Il mondo informatico ha in queste settimane dovuto dire addio a due “pezzi da novanta”: Jacob Ziv e Abraham Lempel, scomparsi rispettivamente il 25 marzo e il 4 febbraio 2023.

I due informatici, entrambi israeliani, sono noti per aver sviluppato l’algoritmo di compressione dati LZ che prende il nome proprio dalle iniziali dei loro cognomi.
LZ è una delle tecniche di compressione dati lossless più utilizzate al mondo

L’algoritmo LZ è stato sviluppato nel 1977 e ha avuto un impatto significativo sulla compressione dati tanto che è stato poi abbracciato per il successivo sviluppo dei formati Gzip, Zip e PNG. Il lavoro svolto dai due “pionieri della compressione” è consultabile in questo documento del 1977.
L’idea di base dell’algoritmo è quella di sostituire sequenze ripetitive di caratteri con riferimenti a una posizione precedente nella stessa sequenza, in modo da ridurre lo spazio necessario per memorizzarla.

Il formato Zip è stato sviluppato da Phil Katz negli anni ’80 e prevede la creazione di un archivio che contiene uno o più file compressi utilizzando l’algoritmo LZ o altri algoritmi di compressione lossless.

Ampiamente usato in ambiente Windows, Zip fu ideato nel 1989 da Katz – fondatore della storica azienda PKWARE – che creò l’utilità per MS-DOS chiamata PKZIP e basata su riga di comando (molti dei nostri lettori la ricorderanno…).
Lo Zip è un formato che supporta diversi algoritmi per la compressione dati anche se il più comune è rimasto DEFLATE: quest’ultimo, a sua volta, poggiava su LZ77 (l’algoritmo di compressione di base sviluppato proprio da Lempel e Ziv) oltre che sul codice di Huffman.
Il codice di Huffman assegna codici di lunghezza variabile a ciascun simbolo in base alla sua frequenza di apparizione. I simboli più comuni ricevono codici più corti riducendo così lo spazio di archiviazione necessario per memorizzarli e gestirli.

Ziv e Lempel hanno ricevuto numerosi premi e riconoscimenti per il loro lavoro nell’ambito della compressione dati, tra cui il prestigioso premio IEEE Richard W. Hamming Medal nel 1998.