Point-wise analysis of redundancy in SWLZ algorithm for φ-mixing sources
Ayush Jain, Rakesh K Bansal · 2015
In this paper, we bound the number of phrases of the sliding window Lempel-Ziv (SWLZ) algorithm using an upper bound on the expected number of phrases in the fixed database Lempel-Ziv (FDLZ) algorithm for a class of φ-mixing sources which includes Markov sources, unifilar sources and finite state sources as special cases, as developed by Yang and Kieffer [1]. We use this bound to obtain a point-wise upper bound on the redundancy rate of SWLZ algorithm to be 2H(log2log2nw/log2nw) + O(log2log2log2nw/log2nw). Here H is the entropy rate of the source and nwis the window size.