Second-order analysis of lossless and lossy versions of Lempel-Ziv codes
Ioannis Kontoyiannis · 2002
We present an overview of several recent results (some new and some known) on the asymptotic performance of different variants of the Lempel-Ziv coding algorithm, in both the lossless case and the lossy case. The results are based on the asymptotic behavior of waiting times, following the general methodology introduced by Wyner and Ziv (1989). We show that, in this framework, very precise statements can be made about the second-order (asymptotic) properties of the codeword lengths.