Lempel-Ziv: a “one-bit catastrophe” but not a tragedy
Guillaume Lagarde, Sylvain Perifel · Society for Industrial and Applied Mathematics eBooks · 2018
The so-called “one-bit catastrophe” for the compression algorithm LZ’78 asks whether the compression ratio of an infinite word can change when a single bit is added in front of it. We answer positively this open question raised by Lutz and others: we show that there exists an infinite word w such that ρsup(w) = 0 but ρinf (0w) > 0, where ρsup and ρinf are respectively the lim sup and the lim inf of the compression ratios ρ of the prefixes (Theorem 2.1). To that purpose we explore the behaviour of LZ’78 on finite words and show the following results: • There is a constant C > 0 such that, for any finite word w and any letter . Thus, sufficiently compressible words (ρ(w) = o(1/ log |w|)) remain compressible with a letter in front (Theorem 2.2); • The previous result is tight up to a multiplicative constant for any compression ratio ρ(w) = O(1/ log |w|) (Theorem 2.4). In particular, there are infinitely many words w satisfying ρ(w) = O(1/log |w|) but ρ(0w) = Ω(1).