On the Limiting Distribution of Lempel-Ziv’78 Redundancy for Memoryless Sources - Publikacja - MOST Wiedzy

Wyszukiwarka

On the Limiting Distribution of Lempel-Ziv’78 Redundancy for Memoryless Sources

Abstrakt

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.

Cytowania

  • 1

    CrossRef

  • 1

    Web of Science

  • 4

    Scopus

Autorzy (2)

  • Zdjęcie użytkownika  Philippe Jacquet

    Philippe Jacquet

    • . .
  • Zdjęcie użytkownika prof. dr inż. Wojciech Szpankowski

    Wojciech Szpankowski prof. dr inż.

    • Purdue University Department of Computer Science

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
IEEE TRANSACTIONS ON INFORMATION THEORY nr 60, strony 6917 - 6930,
ISSN: 0018-9448
Język:
angielski
Rok wydania:
2014
Opis bibliograficzny:
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:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1109/tit.2014.2358679
Weryfikacja:
Politechnika Gdańska

wyświetlono 10 razy

Publikacje, które mogą cię zainteresować

Meta Tagi