A Toast to Lossless Lempel: The Pioneer of Data Compression Will be Missed

Lempel’s algorithms, LZ77 and LZ78, became popular inspiring different variants in a short time but most of them like DEFLATE, LZMA or LZX went away just as quickly

On February 5, Israeli computer scientist Abraham Lempel, father of the lossless data compression algorithm, passed away at the age of 86. 

Lempel, along with Jacob Ziv and Terry Welch, had built a universal lossless data compression algorithm in 1984 called the Lempel-Ziv-Welch (LZW), an improved version of the LZ78 algorithm that had been published in a paper co-authored by Lempel and Ziv in 1978. 

If all this sounds too obscure, the value of Lempel’s contributions can be measured by the ubiquitousness of the LZW algorithm in modern technology. 

AIM Daily XO

Join our editors every weekday evening as they steer you through the most significant news of the day, introduce you to fresh perspectives, and provide unexpected moments of joy
Your newsletter subscriptions are subject to AIM Privacy Policy and Terms and Conditions.

It wouldn’t be such a stretch to say that some of the biggest tech companies would have struggled to exist without Lempel’s data compression techniques. The bigger the organisation, the more the need for data compression – Tech giants like Alphabet, Facebook, Spotify or even Apple for iTunes make the most use these algorithms. Social media companies like Facebook or Instagram have to deal with massive loads of user uploads and need to compress data while Google also uses compression software to back up its memory.

Implementation of LZW data compression algorithm, Source: Semantic Scholar

Why is data compression needed?

The need underlying data compression itself is pretty simple – it allows organisations to maximise the amount of data they have while being able to manage it more easily by minimising the relevant storage space and costs. 

Download our Mobile App

But how exactly does it do this? Data compression can be categorised by the two different techniques through which it is performed – lossy and lossless. Essentially, both of them have the same goal – to search for duplicate data in a graphic (mostly GIFs for LZW) and replace it with a much more compact data representation instead. The lossless algorithm searches for statistically redundant bits and reduces them, while on the other hand, a lossy algorithm simply picks out the irrelevant parts of information and removes them. 

Compression that removes blank values (white) and encodes repetitive values. Source: Faust 2013. 

While data compression gained more importance in computing, starting from the 1970s, there is a much bigger history behind it even outside of computing. Even the Morse Code, which came about in 1838 is one of the earliest illustrations of data compression. Currently, compression algorithms are implemented in multiple file formats like GIFs for image compression, PDFs for file compression and MP3 for audio compression apart from digital cables and satellite television. 

But even saying this would be to undersell the importance of data compression – the LZ algorithm is found virtually in every modern computer in software or hardware and at times in both. While using it normally, there isn’t a full awareness that we are using it because we use it so much – while archiving files, installing software on a disk, backing up hard drives or even upgrading the quality of cinema cameras to 4K. 

Lempel’s algorithm

Both of Lempel’s algorithms, the LZ77 and LZ78, became popular and inspired different variants of them within a short span. But most of these variants like DEFLATE, LZMA or LZX went away just as quickly. This wasn’t particularly because it was technically proficient, but because the LZ77 was patented soon after. 

Notably in 1993, Stac Electronics built another version of the LZW, called the LZS or the Lempel-Ziv-Stac, to use it in their disk compression software Stacker. The LZS was known to be pretty fast and was picked up by Microsoft while creating a disk compression software with MS-DOS 6.0 which would double the capacity of a hard drive. Stac Electronics ended up suing Microsoft for using its algorithm illegally after which the tech giant eventually had to fork out USD 120 million for patent infringement. 

The patent on the LZW algorithm expired in 2003 ending most of the legal issues that surrounded it but the algorithm stuck and is still typically used in GIFs and PDFs. 

Lempel, who was a resident professor at Technion, the Israel Institute of Technology, continued his academic career quietly for over 40 years. While teaching both electrical engineering and computer science at the university, he served as the head of Technion’s computer science department between 1981 and 1984. 

Professor Lempel at a conference at Technion University, Source: Technion

Life and achievements

In 1993, Lempel joined the research unit for HP called Hewlett-Packard Labs. He worked to bring a sister facility to Israel. Having established HP Labs in his country, he served as the director of the division until October 2007 and went on to work quietly around the development of basic and universal image processing tools and customised applications. 

Lempel was also an IEEE or Institute of Electrical and Electronics Engineers Fellow and a Senior Fellow at HP. Lempel has eight US patents, plus more than 90 published research papers on data compression and information theory, the study of mathematical concepts and parameters around message transmission in communication. 

In 2004, the IEEE Executive Committee and History Committee named the LZ algorithm as a milestone in electronics. Lempel himself was awarded the Golden Jubilee Award for Technological Innovation in 1998 and the 2007 Richard W. Hamming Medal by IEEE for the LZW algorithm. It pays to commemorate the value that pioneers brought to the field and it is safe to say that Lempel’s algorithm will be alive for a long, long time. 

Sign up for The Deep Learning Podcast

by Vijayalakshmi Anandan

The Deep Learning Curve is a technology-based podcast hosted by Vijayalakshmi Anandan - Video Presenter and Podcaster at Analytics India Magazine. This podcast is the narrator's journey of curiosity and discovery in the world of technology.

Poulomi Chatterjee
Poulomi is a Technology Journalist with Analytics India Magazine. Her fascination with tech and eagerness to dive into new areas led her to the dynamic world of AI and data analytics.

Our Upcoming Events

27-28th Apr, 2023 I Bangalore
Data Engineering Summit (DES) 2023

23 Jun, 2023 | Bangalore
MachineCon India 2023

21 Jul, 2023 | New York
MachineCon USA 2023

3 Ways to Join our Community

Telegram group

Discover special offers, top stories, upcoming events, and more.

Discord Server

Stay Connected with a larger ecosystem of data science and ML Professionals

Subscribe to our Daily newsletter

Get our daily awesome stories & videos in your inbox