Towards Analytical Information Theory: Some Recent Results on Lempel-Ziv Data Compression Schemes

In this talk we analyze various aspects of data compression schemes due to Lempel and Ziv. The problems investigated range from the off-line Lempel-Ziv compression scheme, lossy extensions of the Lempel-Ziv algorithm, to the shortest superstring problem (lossless and lossy versions). We aim at discovering second-order properties (e.g., variances, limiting distributions, large deviations, etc.) of several existing and new data compression schemes in order to obtain more refined information about typical behavior of these schemes. During the talk we concentrate on proving a long standing open problem concerning the redundancy of the the Lempel-Ziv parsing scheme. While discussing it, we present several new results concerning this scheme proved recently by analytical approach. We will also pose three open problems in this area. The results presented in this talk were obtained jointly with P. Jacquet, and G. Louchard.