Compression of Low Entropy Strings with Lempel--Ziv Algorithms
S. Rao Kosaraju, Giovanni Manzini · SIAM Journal on Computing · 2000
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\geq 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\geq 1$.