|
Listen to this story
|
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.
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.
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.
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.
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.
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.
