Dr. Abraham Lempel

In three fundamental papers published between 1976 and 1978, Lempel and Ziv developed a theory of finite-state compressibility, and, based on that notion, a universal noiseless source-coding technique, known today as the LZ algorithm. In a theoretical sense, the LZ algorithm yields the best compression rate achievable by any lossless finite-state encoder. For any stationary ergodic finite-alphabet source, the LZ algorithm achieves a compression rate whose limiting value, as the number of source samples goes to infinity, is the string entropy. In addition to being theoretically optimal in this sense, the LZ algorithm performs superbly on real-world, finite-length strings, and lends itself, through string matching and dictionary management, to very efficient software and hardware implementations.

The evolution of computing and communication technology has made ever growing demands on storage, bandwidth, and speed, with data compression playing a critical role in satisfying these demands. The LZ algorithm has made the use of lossless data compression pervasive in day-to-day computing, to the point that virtually every modern computer or workstation runs one or, more likely, several implementations of LZ compression in hardware, software, or both. We use the LZ algorithm, often without being aware of it, when we archive our files with {\sf compress}, {\sf gzip}, or {\sf pkzip}; when we use software compression of our hard drives (DriveSpace in MS Windows 95), when we install software that comes compressed on diskette or other media; when we back up our hard drives to magnetic tapes (ECMA-151 DCLZ standard); when we go online via our modems (V.42bis standard); when we display images from the WWW (GIF, TIFF, and PNG formats); and so on and on.

These examples of the practical impact add to the well-recognized theoretical significance of the work of Lempel and Ziv. The LZ papers are considered a milestone in source-coding theory and have generated a vast amount of research since their publications, resulting in hundreds of articles, ranging from the most theoretical to the very practical.

The work by Lempel and Ziv on finite-state compressibility and universal data compression led many researchers to new approaches and techniques in data compression, statistics, string and pattern matching, cryptography, and algorithm analysis.

The work of Lempel and Ziv has proven to be so seminal that current research in this area is just as active today as it was 20 years ago, with each year seeing more theoreticians as well as more implementers engaged in the extension and evolution of their elegant concept. It is not an exaggeration to say that the practicality of mobile computing and multimedia applications were both accelerated greatly and made economically feasible by the performance gains made possible by data compression technology, which owes its development to Lempel and Ziv's pioneering work. For this important contribution, Lempel and Ziv are recognized with the ACM Kanellakis Award for Theory and Practice.