학술논문
On Certain Pathwise Properties of the Sliding-Window Lempel–Ziv Algorithm
Document Type
Periodical
Author
Source
IEEE Transactions on Information Theory IEEE Trans. Inform. Theory Information Theory, IEEE Transactions on. 52(12):5267-5283 Dec, 2006
Subject
Language
ISSN
0018-9448
1557-9654
1557-9654
Abstract
We derive several almost-sure results related to the sliding-window Lempel–Ziv (SWLZ) algorithm. A principal result is a path-wise lower bound to the redundancy equal to ${1 \over 2} h {\log_2 \log_2 n_w \over \log_2 n_w}$ in the main term, where $n_w$ is the sliding window size. This bound is off by a factor of two from the main term in the lower bound of A. J. Wyner and the work of Yang and Kieffer, which hold in the expected sense for the fixed-database Lempel–Ziv algorithm (FDLZ). Another aspect of the present work studies the asymptotic behavior of the ratio of the number of phrases to the length of the parsed string for any finite sliding window size; in here we exploit the theory of asymptotic mean stationary processes of Gray and Kieffer and some results of Kieffer and Rahe. In all cases it is assumed that the source is stationary and that in the most restrictive case it is an irreducible and aperiodic Markov chain; some of the results hold for sources that have exponential rates for entropy and more generally for the ergodic setting.