On match lengths and the asymptotic behavior of Sliding Window Lempel-Ziv algorithm for zero entropy sequences
Siddharth Jain, Rakesh K. Bansal · 2013
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 Loin 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 nwa compression ratio given by O(log nw/nwa) 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.