|Résumé||LZ'78 is a famous and very simple lossless data compression algorithm published by Abraham Lempel and Jacob Ziv in 1978. Although widely used in practise, we know little about its stability. The one-bit catastrophe question, introduced by Jack Lutz in the late 90s, asks whether an infinite word compressible by LZ'78 can become incompressible by adding a single bit in front of it. Our main result is to answer that question positively. We also give tight bounds on the maximal possible variation between the compression ratio of a finite word and its perturbation (when one bit is added in front of it), showing that to get a "catastrophe", the initial word needs already to be close to the threshold of incompressibility.
This is a joint work with Sylvain Perifel. |