Skip to Main content Skip to Navigation
Reports

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

Philippe Jacquet 1 Szpankowski Wojciech 2
1 HIPERCOM - High performance communication
Inria Paris-Rocquencourt, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : 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.
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/inria-00476902
Contributor : Philippe Jacquet <>
Submitted on : Tuesday, April 27, 2010 - 3:17:21 PM
Last modification on : Wednesday, September 16, 2020 - 5:06:56 PM
Long-term archiving on: : Monday, October 22, 2012 - 3:26:16 PM

File

LZ-RR.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00476902, version 1

Collections

INRIA | X | CNRS | LARA

Citation

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

Share

Metrics

Record views

459

Files downloads

128