Title :
Point-wise analysis of redundancy in SWLZ algorithm for φ-mixing sources
Author :
Jain, Ayush ; Bansal, Rakesh K.
Author_Institution :
Indian Inst. of Technol. Kanpur, Kanpur, India
fDate :
April 26 2015-May 1 2015
Abstract :
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 nw is the window size.
Keywords :
Markov processes; entropy; φ-mixing sources; 2H(log2log2nw/log2nw); FDLZ algorithm; Markov sources; O(log2log2log2nw/log2nw); SWLZ algorithm; entropy rate; finite state source; fixed database Lempel-Ziv algorithm; point-wise analysis; point-wise upper bound; redundancy rate; sliding window Lempel-Ziv algorithm; unifilar source; window size; Algorithm design and analysis; Databases; Electronic mail; Markov processes; Mathematical model; Redundancy; Upper bound; φ-mixing processes; LZ77; Markov processes; almost sure convergence; fixed database Lempel-Ziv (FDLZ); point-wise redundancy rate; sliding window Lempel-Ziv (SWLZ);
Conference_Titel :
Information Theory Workshop (ITW), 2015 IEEE
Conference_Location :
Jerusalem
Print_ISBN :
978-1-4799-5524-4
DOI :
10.1109/ITW.2015.7133103
