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

preprint2013arXivOpen access

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 LoL_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 nwn_w a compression ratio given by O(log⁡nwnwa)O(\frac{\log n_w}{{n_w}^a}) where aa is arbitrarily close to 1 and 0<a<10 < 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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.