On Match Lengths, Zero Entropy, and Large Deviations—With Application to Sliding Window Lempel–Ziv Algorithm

Abstract

The sliding window Lempel-Ziv (SWLZ) algorithm that makes use of recurrence times and match lengths has been studied from various perspectives in information theory literature. In this paper, we undertake a finer study of these quantities under two different scenarios: 1) zero entropy sources that are characterized by strong long-term memory and 2) the processes with weak memory as described through various mixing conditions. For zero entropy sources, a general statement on match length is obtained. It is used in the proof of almost sure optimality of fixed shift variant of Lempel-Ziv (FSLZ) and SWLZ algorithms given in literature. Through an example of stationary and ergodic processes generated by an irrational rotation, we establish that for a window of size n_w, a compression ratio given by O(log n_w/n_w^a), where a depends on n_w and approaches 1 as n_w → ∞, is obtained under the application of FSLZ and SWLZ algorithms. In addition, we give a general expression for the compression ratio for a class of stationary and ergodic processes with zero entropy. Next, we extend the study of Ornstein and Weiss on the asymptotic behavior of the normalized version of recurrence times and establish the large deviation property for a class of mixing processes. In addition, an estimator of entropy based on recurrence times is proposed for which large deviation principle is proved for sources satisfying similar mixing conditions.

Additional details