On Match Lengths and the Asymptotic Behavior of Sliding Window Lempel-Ziv Algorithm for Zero Entropy Sequences

Abstract

The Sliding Window Lempel-Ziv (SWLZ) algorithm has been studied from various perspectives in information theory literature. In this paper, we provide a general law which defines the asymptotics of match length for stationary and ergodic zero entropy processes. Moreover, we use this law to choose the match length $L_o$ in the almost sure optimality proof of Fixed Shift Variant of Lempel-Ziv (FSLZ) and SWLZ algorithms given in literature. First, through an example of stationary and ergodic processes generated by irrational rotation we establish that for a window size of $n_w$ a compression ratio given by $O(\frac{\log n_w}{{n_w}^a})$ where $a$ is arbitrarily close to 1 and $0<a<1$, is obtained under the application of FSLZ and SWLZ algorithms. Further, we give a general expression for the compression ratio for a class of stationary and totally ergodic processes with zero entropy.

arXiv comment5 pages, International Symposium on Information Theory, 2013