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., L277) can be much higher than the zeroth order entropy H₀ (resp., the first order entropy H₁). For this reason we introduce the concept of λ-optimal algorithm. An algorithm is λ-optimal with respect to H_k if, loosely speaking, its compression ratio is asymptotically bounded by λ times the kth order empirical entropy H_k. We prove that LZ78 cannot be λ-optimal with respect to any H_k with k ≥ 0. Then, we describe a new algorithm which combines LZ78 with run length encoding (RLE) and is 3-optimal with respect to H₀. Finally, we prove that LZ77 is 8-optimal with respect to H₀, and that it cannot be λ-optimal with respect to H_k for any k ≥ 1.