Search
Abstract
We study the Lempel-Ziv'78 algorithm and show that its (normalized) redundancy rate tends to a Gaussian distribution for memoryless sources. We accomplish it by extending findings from our 1995 paper, in particular, by presenting a new simplified proof of the central limit theorem (CLT) for the number of phrases in the LZ'78 algorithm. We first analyze the asymptotic behavior of the total path length in the associated digital search tree built from independent sequences. Then, a renewal theory type argument yields CLT for LZ'78 scheme. Here, we extend our analysis of LZ'78 algorithm to present new results on the convergence of moments, moderate and large deviations, and CLT for the (normalized) redundancy. In particular, we confirm that the average redundancy rate decays as 1/log n, and we find that the variance is of order 1/n, where n is the length of the text.
Citations
-
1
CrossRef
-
0
Web of Science
-
4
Scopus
Authors (2)
-
Philippe Jacquet
- . .
-
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
IEEE TRANSACTIONS ON INFORMATION THEORY
no. 60,
pages 6917 - 6930,
ISSN: 0018-9448 - Language:
- English
- Publication year:
- 2014
- Bibliographic description:
- Jacquet P., Szpankowski W.: On the Limiting Distribution of Lempel-Ziv’78 Redundancy for Memoryless Sources// IEEE TRANSACTIONS ON INFORMATION THEORY. -Vol. 60, nr. 11 (2014), s.6917-6930
- DOI:
- Digital Object Identifier (open in new tab) 10.1109/tit.2014.2358679
- Verified by:
- Gdańsk University of Technology
seen 87 times