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.
Type de document :
Rapport
[Research Report] 2010
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00476902
Contributeur : Philippe Jacquet <>
Soumis le : mardi 27 avril 2010 - 15:17:21
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : lundi 22 octobre 2012 - 15:26:16

Fichier

LZ-RR.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00476902, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

338

Téléchargements de fichiers

102