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

Ashwin Pananjady and Orhan Ocal

Last Modification Date: Wednesday, February 10, 2016