Un brindisi a Lempel senza perdite: il pioniere della compressione dei dati ci mancherà
Gli algoritmi di Lempel, LZ77 e LZ78, sono diventati popolari ispirando diverse varianti in breve tempo, ma la maggior parte di essi come DEFLATE, LZMA o LZX sono scomparsi altrettanto rapidamente
Il 5 febbraio è morto all’età di 86 anni lo scienziato informatico israeliano Abraham Lempel, padre dell’algoritmo di compressione dei dati senza perdita di dati.
Lempel, insieme a Jacob Ziv e Terry Welch, nel 1984 aveva costruito un algoritmo universale di compressione dei dati senza perdita chiamato Lempel-Ziv-Welch (LZW), una versione migliorata dell’algoritmo LZ78 che era stata pubblicata in un articolo co-autore di Lempel e Ziv nel 1978.
Se tutto ciò sembra troppo oscuro, il valore dei contributi di Lempel può essere misurato dall’ubiquità dell’algoritmo LZW nella tecnologia moderna.
Non sarebbe così esagerato affermare che alcune delle più grandi aziende tecnologiche avrebbero faticato a esistere senza le tecniche di compressione dei dati di Lempel. Più grande è l’organizzazione, maggiore è la necessità di compressione dei dati: giganti della tecnologia come Alphabet, Facebook, Spotify o persino Apple per iTunes utilizzano maggiormente questi algoritmi. Le società di social media come Facebook o Instagram devono gestire enormi carichi di caricamenti degli utenti e devono comprimere i dati mentre Google utilizza anche software di compressione per eseguire il backup della propria memoria.
Perché è necessaria la compressione dei dati?
La stessa esigenza alla base della compressione dei dati è piuttosto semplice: consente alle organizzazioni di massimizzare la quantità di dati di cui dispongono pur essendo in grado di gestirli più facilmente riducendo al minimo lo spazio di archiviazione e i costi pertinenti.
Ma come lo fa esattamente? La compressione dei dati può essere classificata in base alle due diverse tecniche attraverso le quali viene eseguita: con perdita e senza perdita. In sostanza, entrambi hanno lo stesso obiettivo: cercare dati duplicati in un grafico (principalmente GIF per LZW) e sostituirli invece con una rappresentazione dei dati molto più compatta. L’algoritmo senza perdita cerca bit statisticamente ridondanti e li riduce, mentre un algoritmo con perdita seleziona semplicemente le parti irrilevanti delle informazioni e le rimuove.
Compressione che rimuove i valori vuoti (bianco) e codifica i valori ripetitivi. Fonte: Faust 2013.
Sebbene la compressione dei dati abbia acquisito maggiore importanza nell’informatica, a partire dagli anni ’70, dietro di essa c’è una storia molto più ampia anche al di fuori dell’informatica. Anche il codice Morse, nato nel 1838, è uno dei primi esempi di compressione dei dati. Attualmente, gli algoritmi di compressione sono implementati in più formati di file come GIF per la compressione delle immagini, PDF per la compressione dei file e MP3 per la compressione audio oltre ai cavi digitali e alla televisione satellitare.
Ma anche dire questo significherebbe sottovalutare l’importanza della compressione dei dati: l’algoritmo LZ si trova praticamente in ogni computer moderno nel software o nell’hardware e talvolta in entrambi. Mentre lo usiamo normalmente, non c’è la piena consapevolezza che lo stiamo usando perché lo usiamo così tanto – durante l’archiviazione di file, l’installazione di software su un disco, il backup di dischi rigidi o persino l’aggiornamento della qualità delle videocamere cinematografiche a 4K.
Algoritmo di Lempel
Entrambi gli algoritmi di Lempel, LZ77 e LZ78, sono diventati popolari e ne hanno ispirato diverse varianti in breve tempo. Ma la maggior parte di queste varianti come DEFLATE, LZMA o LZX sono scomparse altrettanto rapidamente. Questo non era particolarmente perché fosse tecnicamente competente, ma perché l’LZ77 è stato brevettato poco dopo.
In particolare nel 1993, Stac Electronics ha costruito un’altra versione di LZW, chiamata LZS o Lempel-Ziv-Stac, per utilizzarla nel proprio software di compressione del disco Stacker. L’LZS era noto per essere piuttosto veloce ed è stato raccolto da Microsoft durante la creazione di un software di compressione del disco con MS-DOS 6.0 che avrebbe raddoppiato la capacità di un disco rigido. Stac Electronics ha finito per citare in giudizio Microsoft per aver utilizzato illegalmente il suo algoritmo, dopodiché il gigante della tecnologia ha dovuto sborsare 120 milioni di dollari per violazione di brevetto.
Il brevetto sull’algoritmo LZW è scaduto nel 2003 ponendo fine alla maggior parte dei problemi legali che lo circondavano, ma l’algoritmo si è bloccato ed è ancora tipicamente utilizzato in GIF e PDF.
Lempel, che era un professore residente al Technion , l’Israel Institute of Technology, ha continuato la sua carriera accademica in silenzio per oltre 40 anni. Mentre insegnava ingegneria elettrica e informatica all’università, ha lavorato come capo del dipartimento di informatica del Technion tra il 1981 e il 1984.
Vita e successi
Nel 1993, Lempel è entrato a far parte dell’unità di ricerca di HP chiamata Hewlett-Packard Labs . Ha lavorato per portare una struttura gemella in Israele. Dopo aver fondato HP Labs nel suo paese, ha ricoperto il ruolo di direttore della divisione fino all’ottobre 2007 e ha continuato a lavorare silenziosamente allo sviluppo di strumenti di elaborazione delle immagini di base e universali e di applicazioni personalizzate.
Lempel è stato anche IEEE o Institute of Electrical and Electronics Engineers Fellow e Senior Fellow presso HP. Lempel detiene otto brevetti statunitensi , oltre a più di 90 documenti di ricerca pubblicati sulla compressione dei dati e sulla teoria dell’informazione, lo studio dei concetti e dei parametri matematici relativi alla trasmissione dei messaggi nella comunicazione.
Nel 2004, il Comitato Esecutivo IEEE e il Comitato Storico hanno definito l’algoritmo LZ una pietra miliare dell’elettronica. Lo stesso Lempel ha ricevuto il Golden Jubilee Award for Technological Innovation nel 1998 e la Richard W. Hamming Medal nel 2007 dall’IEEE per l’algoritmo LZW. Vale la pena commemorare il valore che i pionieri hanno portato sul campo ed è sicuro affermare che l’algoritmo di Lempel sarà vivo per molto, molto tempo.
