New analysis of the asymptotic behavior of the Lempel-Ziv compression algorithm

Philippe Jacquet (1) , Szpankowski Wojciech (2)

1 HIPERCOM - High performance communication
2 Department of Computer Science [Purdue]

We give a new analysis and proof of the Normal limiting distribution of the number of phrases in the 1978 Lempel-Ziv compression algorithm on random sequences built from a memoriless source. This work is a follow-up of our last paper on this subject in 1995. The analysis stands on the asymptotic behavior of a DST obtained by the insertion of random sequences. Our proofs are augmented of new results on moment convergence, moderate and large deviations, redundancy analysis.

Mots clés: data compression; digital search tree; generating functions; depoissonization; renewal processes

Domaines: Réseaux et télécommunications [cs.NI]

Philippe Jacquet, Szpankowski Wojciech. New analysis of the asymptotic behavior of the Lempel-Ziv compression algorithm. [Research Report] 2010. ⟨inria-00476902⟩