Compression of low entropy strings with Lempel-Ziv algorithms

We compare the compression ratio of the Lempel-Ziv algorithms with the empirical entropy of the input string. This approach makes it possible to analyze the performance of these algorithms without any assumption on the input and to obtain worst case results. We show that in this setting the standard definition of optimal compression algorithm is not satisfactory. In fact, although Lempel-Ziv algorithms are optimal according to the standard definition, there exist families of low entropy strings which are not compressed optimally. More precisely, the compression ratio achieved by LZ78 (resp., LZ77) can be much higher than the zeroth order entropy H-0 (resp., the first order entropy H-1). For this reason we introduce the concept of lambda-optimal algorithm. An algorithm is lambda-optimal with respect to H-k if, loosely speaking, its compression ratio is asymptotically bounded by lambda times the kth order empirical entropy H-k. We prove that LZ78 cannot be lambda-optimal with respect to any H-k with k greater than or equal to 0. Then, we describe a new algorithm which combines LZ78 with run length encoding (RLE) and is 3-optimal with respect to H-0. Finally, we prove that LZ77 is 8-optimal with respect to H-0, and that it cannot be lambda-optimal with respect to H-k for any k greater than or equal to 1.