Average profile and limiting distribution for a phrase size in thw Lempel-Ziv parsing algorithm

Guy Louchard Wojciec Szpankowski 1
1 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : Consider the parsing algorithm due to Lempel and Ziv that partitions a sequence of length n into variable phrases (blocks) such that a new block is the shortest substring not seen in the past as a phrase. In practice the following parameters are of interest : number of phrases, the size of a phrase, the number of phrases of given size and so forth. In this paper, we focus on the size of a randomly selected phrases and the average number of phrases of a given size (the so called average profile of phrase sizes). These parameters can be efficiently analyzed through a digital search tree representation. For a memoryless source with unequal probabilities of symbols generation (the so called asymmetric Bernoulli model) we prove that the size of a typical phrase is asymptotically normally distributed with the average value and the variance explicity computed. In terms of digital search trees, we prove the normal limiting distribution of the typical depth (i.e., the length of a path from the root to a randomly selected node). The latter finding is proved by a technique that belongs to the toolkit of the "analytical analysis of algorithms" but which seems to be novel in the context of data compression.
Type de document :
Rapport
[Research Report] RR-1886, INRIA. 1993
Liste complète des métadonnées

https://hal.inria.fr/inria-00074786
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:20:30
Dernière modification le : vendredi 25 mai 2018 - 12:02:02
Document(s) archivé(s) le : mardi 12 avril 2011 - 19:22:10

Fichiers

Identifiants

  • HAL Id : inria-00074786, version 1

Collections

Citation

Guy Louchard, Wojciec Szpankowski. Average profile and limiting distribution for a phrase size in thw Lempel-Ziv parsing algorithm. [Research Report] RR-1886, INRIA. 1993. 〈inria-00074786〉

Partager

Métriques

Consultations de la notice

81

Téléchargements de fichiers

44