Channels ▼
RSS

Design

Abraham Lempel Honored for Compression Algorithms


Mark is a contributing editor to Dr. Dobb's Journal and author of The Data Compression Book. He can be contacted at http://marknelson.us/.

The IEEE has announced its medal winners for 2007, and this year’s Richard W. Hamming Medal has been awarded to Dr. Abraham Lempel for his "pioneering work in data compression especially the Lempel-Ziv algorithm."

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 (PPM, for instance), 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 Hewlett-Packard, performing and directing research at HP Labs in Israel. He was kind enough to answer a few questions for this article.

DDJ: Dr. Lempel, 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?

AL: 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.

DDJ: 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 two granted patents ended up as Sperry, now Unisys, Intellectual Property.

DDJ: 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.

DDJ: 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.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.