The IEEE has announced its list of medal winners for 2007, and this year’s Richard Hamming medal was awarded to Dr. Abraham Lempel :

For pioneering work in data compression especially the Lempel-Ziv algorithm.

A photo of Abraham Lempel.

This is a timely award, because it comes on the 30th anniversary of the publication of the first of two seminal papers by Dr. Lempel and Jacob Ziv, his associate at Technion - Israel Institute of Technology.

In 1977 Ziv and Lempel published A Universal Algorithm for Sequential Data Compression , describing what would come to be known as the LZ77 algorithm. In 1978, they followed this with Compression of Individual Sequences via Variable-Rate Coding , which described what came to be known as the LZ78 algorithm.

Both of these algorithms use macro substitution to compress arbitrary data. By replacing a long sequence of bytes with a short macro, compression is achieved. Both algorithms build this library of macros dynamically, adjusting to the input text as it is read. They differ in the way they build the library of macros.

LZ78 was eventually reduced to practice by Terry Welch with the publication of the LZW algorithm, used in UNIX compress, GIF files, and elsewhere. LZ77 provided the core of the deflate algorithm, which is used in the Zip standard, arguably the dominant lossless compression algorithm since it was introduced by PKZIP in 1993.

It would be hard to overstate the impact of these two papers in the world of data compression. While there are other lossless algorithms that can compress as well as LZ77 and LZ78 (e.g. PPM ), the two LZ algorithms have won the battle of speed and efficiency almost 20 years. Applications for the algorithms vary from desktop applications to graphics file formats to tape drive controllers. As an example of their influence, Citeseer lists 458 citations for the 1977 paper , and 293 for the 1978 paper . Dr. Lempel is currently employed by HP, performing and directing research at HP Labs in Israel. He was kind enough to answer a few questions for this article.

Mark Nelson: In 1977 and 1978, you published two now-famous compression papers with Jacob Ziv that provided the background for some of today’s most effective and popular compression algorithms, such as the deflate standard used in Zip-compatible programs. At the time, did you imagine that your work would be so broadly used 30 years later?

Abraham Lempel: We were so excited with the results of our work, that we did not give too much thought to this question at the time. As more and more extensions and versions were published by other researchers, we recognized the seminal nature of this work and viewed our approach to lossless data compression as a long term method.

MN: The papers you published provide a mathematical and theoretical description of universal compressors, but don’t dig into implementation details. Do you have much personal interest in converting theory into practice, or do you get the most satisfaction from the research work that provides the foundation?

AL: Following the publication of 1977 and 1978 papers, we both participated in writing an invention disclosure which included all the details of a preferred embodiment implementation. This was done while I was on sabbatical at Sperry Research, and the 2 granted patents ended up as Sperry, now Unisys, Intellectual Property.

MN: Since your seminal work, I think the most significant advance in lossless compression has been the creation of block-sorting algorithms, as described by Burrows and Wheeler. Do you think there are any revolutionary new techniques on the horizon, or should we just expect minor incremental improvements?

AL: Hard to tell. When we worked on our method, the Huffman algorithm was considered the last word in lossless data compression. Now, the various LZ versions are treated as such. All this is in the context of text compression. I do expect radical progress in lossless image compression, which is a different beast from text.

MN: After a distinguished career at Technion - Israel Institute of Technology and almost 25 years with HP Labs, you’re at a point where many people would be thinking of retiring and slowing down. Is that in your near-term plans?

AL: I do plan to retire in 2008.

It is great to see the IEEE honor Dr. Lempel for his work. It would have been hard to understand how important this was in 1977. Today, with the benefit of 30 years hindsight, it clearly stands out as a masterpiece.

Reference Links