ON ASYMPTOTIC OPTIMALITY OF A SLIDING WINDOW VARIATION OF LEMPEL-ZIV CODES

Ziv and Lempel proposed two important universal coding algorithms in 1977 and 1978. While the second algorithm, called LZ78, has been sufficiently analyzed in the literature, the first, LZ77, has not yet. LZ77 parses input data into a sequence of phrases, each of which is the longest match in a fixed-sized sliding window which consists of the previously encoded M symbols. Each phrase is replaced by a pointer to denote the longest match in the window. Then, a window slides to just before the next symbol to be encoded, and so on. In this paper, we modify the algorithm of LZ77 to restrict pointers to starting only at the boundary of a previously parsed phrase in a window. Although the number of parsed phrases should increase more than those in LZ77, the amount of bits needed to encode pointers is considerably reduced since the number of possible positions to be encoded is much smaller. Then, we show that for any stationary finite state source, the modified LZ77 code is asymptotically optimal with the convergence rate O(log log M / log M) where M is the size of a sliding window.