2013/03/05 by Siddharth Jain, Jain, Siddharth, Rakesh Kumar Bansal +1
Computer Science · Mathematics · #Algorithms and Data Compression #Artificial Intelligence in Games #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Information Theory (cs.IT) #Mathematical Dynamics and Fractals
paper · pdf · doi:10.48550/arxiv.1303.1098
openalex publication_date 2013/03/05 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
The Sliding Window Lempel-Ziv (SWLZ) algorithm has been studied from various\nperspectives in information theory literature. In this paper, we provide a\ngeneral law which defines the asymptotics of match length for stationary and\nergodic zero entropy processes. Moreover, we use this law to choose the match\nlength Lo in the almost sure optimality proof of Fixed Shift Variant of\nLempel-Ziv (FSLZ) and SWLZ algorithms given in literature. First, through an\nexample of stationary and ergodic processes generated by irrational rotation we\nestablish that for a window size of nw a compression ratio given by\nO( frac\log nwnwa) where a is arbitrarily close to 1 and 0 < a <\n1, is obtained under the application of FSLZ and SWLZ algorithms. Further, we\ngive a general expression for the compression ratio for a class of stationary\nand totally ergodic processes with zero entropy.\n