Efficient Universal Data Compression
Thursday, February 5, 1998


The purpose of this talk is to summarize some of the main ideas in the theory and practice of data compression -- both lossless and lossy -- and to present some of our recent results on the performance of a family of efficient, lossy compression algorithms, that are based on the celebrated Lempel-Ziv compression scheme. In the first part we briefly recall the fundamental limits of data compression: Shannon's source coding theorems, entropy, and the rate-distortion function. In the second part, we will attempt to explain why the Lempel-Ziv _lossless_ compression algorithm has been so successful in practice: The approach that we take shows how the analysis of the practical Lempel-Ziv scheme can be reduced to an interesting (and fun) mathematical problem in probability. In the third (and main) part we show why, in sharp contrast with the lossless case, the numerous extensions of the Lempel-Ziv scheme for _lossy_ compression haven't "caught on" in practice. The intuition gained by this analysis leads us to suggest a new extension of the Lempel-Ziv algorithm which turns out to have asymptotically optimal compression performance, while its complexity is comparable to that of the corresponding lossless scheme, making it easily implementable in practice.
UC Berkeley Networking
Ashwin Pananjady and Orhan Ocal
Last Modification Date: Wednesday, February 10, 2016