Almost Sure Optimality of Sliding Window Lempel–Ziv Algorithm and Variants Revisited

The sliding window Lempel-Ziv (SWLZ) algorithm has been studied extensively in the information theory literature and has been used in several commercial compression packages. The asymptotic behavior of this algorithm has been studied by Wyner and Ziv and by Shields using different approaches. Shields´ results proving asymptotic optimality for all individual sequences with respect to the class of all finite state encoders is known to imply the almost sure asymptotic optimality for the class of stationary and ergodic sources. We establish the almost sure asymptotic optimality (without any mixing conditions) by extending the ideas of Wyner and Ziv using results on recurrence times from ergodic theory. A nonuniversal fixed shift version of the algorithm is introduced to gain more insight into its behavior. Pointwise optimality results are also obtained for several variants based on match-length functions introduced by Gavish and Lempel. We also propose variants of the algorithm for sources with countable alphabet and demonstrate their pointwise optimality.