A Normal Sequence Compressed by PPM${}^{\ast }$ but not by Lempel-Ziv 78

Abstract

In this paper we compare the difference in performance of two of the Prediction by Partial Matching (PPM) family of compressors (PPM${}^{\ast }$ and the original Bounded PPM algorithm) and the Lempel-Ziv 78 (LZ) algorithm. We construct an infinite binary sequence whose worst-case compression ratio for PPM${}^{\ast }$ is $0$, while Bounded PPM's and LZ's best-case compression ratios are at least $1/2$ and $1$ respectively. This sequence is an enumeration of all binary strings in order of length, i.e. all strings of length $1$ followed by all strings of length $2$ and so on. It is therefore normal, and is built using repetitions of de Bruijn strings of increasing order

Cited by in corpus (1)

• Normal Sequences with Non-Maximal Automatic Complexity