Lempel-Ziv: a "one-bit catastrophe" but not a tragedy

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 $ρ_{s u p} (w) = 0$ but $ρ_{i n f} (0 w) > 0$ , where $ρ_{s u p}$ and $ρ_{i n f}$ are respectively the $lim sup$ and the $lim inf$ of the compression ratios $ρ$ of the prefixes. 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 $a$ , $ρ (a w) \leq C \sqrt{ρ (w) \log ∣ w ∣}$ . Thus, sufficiently compressible words ( $ρ (w) = o (1 / \log ∣ w ∣)$ ) remain compressible with a letter in front;
The previous result is tight up to a multiplicative constant for any compression ratio $ρ (w) = O (1 / \log ∣ w ∣)$ . In particular, there are infinitely many words $w$ satisfying $ρ (w) = O (1 / \log ∣ w ∣)$ but $ρ (0 w) = Ω (1)$ .

There is a constant $C > 0$ such that, for any finite word $w$ and any letter $a$ , $ρ (a w) \leq C \sqrt{ρ (w) \log ∣ w ∣}$ . Thus, sufficiently compressible words ( $ρ (w) = o (1 / \log ∣ w ∣)$ ) remain compressible with a letter in front;
The previous result is tight up to a multiplicative constant for any compression ratio $ρ (w) = O (1 / \log ∣ w ∣)$ . In particular, there are infinitely many words $w$ satisfying $ρ (w) = O (1 / \log ∣ w ∣)$ but $ρ (0 w) = Ω (1)$ .

Lempel-Ziv: a "one-bit catastrophe" but not a tragedy

文献摘要

讨论

讲解博客

AI智能校验

Lempel-Ziv: a "one-bit catastrophe" but not a tragedy

文献摘要

讨论

讲解博客

AI智能校验

Lempel-Ziv: a "one-bit catastrophe" but not a tragedy

文献摘要

讨论

|讲解博客

|AI智能校验

Lempel-Ziv: a "one-bit catastrophe" but not a tragedy

文献摘要

讨论

|讲解博客

|AI智能校验

讲解博客

AI智能校验

讲解博客

AI智能校验