A universal upper bound on the performance of the Lempel-Ziv algorithm on maliciously-constructed data
James I. Lathrop, Michael Strauss · 2002
We consider the performance of the Lempel-Ziv (1978) algorithm on finite strings and infinite sequences having unbalanced statistics. We show that such strings and sequences are compressed by the Lempel-Ziv algorithm. We show that the converse does not hold, i.e., that there are sequences with perfectly balanced asymptotic statistics that the Lempel-Ziv algorithm compresses optimally.