On certain pathwise properties of the sliding-window Lempel Ziv algorithm

Abstract

We derive a number of pathwise results related to the sliding window Lempel-Ziv (SWLZ) algorithm, including an upper bound on the redundancy and reasonably tight upper and lower bounds for the number of bits spent on the encoding of the phrase lengths. We also investigate important basic properties of the various limits involved in this study; for example, we succeed in demonstrating that for sources that have exponential rates for entropy and for any database length, the limiting average number of phrases per symbol exists and is constant with probability one.