An almost sure convergence proof of the sliding-window Lempel-Ziv algorithm

Abstract

The convergence proof of a finite memory version of the sliding window Lempel-Ziv algorithm (LZ77) was presented. This proof is valid for those sources which are stationary, ergodic and have exponential rates for entropy. It was shown that if the source is stationary, ergodic and possesses exponential rates for entropy, the compression ratio of the algorithm, when operating on each individual finite sequence, approaches infinity, except for a set of source sequences with measure ratio.