论文标题
由PPM $^*$压缩的正常序列，但不是Lempel-Ziv 78
A Normal Sequence Compressed by PPM$^*$ but not by Lempel-Ziv 78
论文作者
论文摘要
在本文中，我们比较了通过部分匹配（PPM）压缩机家族（PPM $^*$和原始有限PPM算法）和LEMPEL-ZIV 78（lz）算法的两个预测性能差异。我们构建了一个无限的二进制序列，其最差的PPM $^*$的最差压缩比为$ 0 $，而有限的PPM和LZ的最佳案例压缩比分别为$ 1/2 $和$ 1 $。此序列是所有二进制字符串按长度顺序列举的列举，即所有长度$ 1 $的字符串随后是所有长度$ 2 $的字符串，依此类推。因此是正常的
In this paper we compare the difference in performance of two of the Prediction by Partial Matching (PPM) family of compressors (PPM$^*$ 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$^*$ 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
