Name
Abstract | ||
|---|---|---|
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 [EQUATION]. 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).
|
Year | DOI | Venue |
|---|---|---|
2018 | 10.5555/3174304.3175402 | SODA '18: Symposium on Discrete Algorithms
New Orleans
Louisiana
January, 2018 |
DocType | Volume | ISBN |
Conference | abs/1707.04312 | 978-1-61197-503-1 |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guillaume Lagarde | 1 | 0 | 0.68 |
| Sylvain Perifel | 2 | 0 | 0.34 |