State of PPM and Shkarin's PPMII algorithm

[SolidComp]

Hi all – What's the situation with PPM in comparison to other approaches, in terms of ratio, complexity, and speed tradeoffs? I don't see a PPM or PPMII thread here, and I'm curious to learn more about it. Which codecs are using PPM?

Also, what happened with Dmitry Shkarin's PPMII algorithm? I was intrigued by this passage in Steinruecken's 2014 thesis (PDF) on lossless data compression:

Shkarin (2001a) published a finite-depth algorithm named PPMII (PPM with information inheritance), which uses custom probability estimation and update rules that were manually optimised for good compression and speedy computation. As of 2014, the results produced by PPMII are still state of the art and unbeaten by any other known PPM variant.

How does PPMII compare to other, non-PPM approaches? (I didn't realize until now that PPMd is also Shkarin's.)

(That thesis also references a 1998 paper by Charles Bloom (PDF) that focuses on PPM. I haven't read it yet.)

Thanks.

[Shelwien]

> Hi all – What's the situation with PPM in comparison to other approaches,

PPM can be viewed as an ultimate version of ROLZ with unary length coding (known as escape coding).

> I don't see a PPM or PPMII thread here, and I'm curious to learn more about it.

Well, you can read this: https://marknelson.us/posts/1991/02/...ion.html#part2
or this: http://mattmahoney.net/dc/dce.html#Section_422

The main characteristic of PPM is escape coding used to combine predictions of multiple predictors.
It would be CM, if we'd use same predictors with logistic mixing.

> Which codecs are using PPM?

The only useful one is PPMd and derivatives (ppmonstr,PPMs, durilca*).

However there're many independent implementations of PPM, you can look for them on LTCB.
Even @encode has 2-3 implementations, eg. http://mattmahoney.net/dc/text.html#1936

> in terms of ratio, complexity, and speed tradeoffs?

Ratio is 5-10% higher than LZMA, which in turn is 10% higher than zstd.

PPMd doesn't implement parsing optimization, so its encoding speed can reach ~20MB/s or so (mostly in PPMs),
but decoding is symmetric, thus its speed is the same (or a little less).

The speed is mostly determined by memory latency (L3 or RAM), so there's not much to improve
on current cpu architectures, although 20 years ago it could compete with LZs in speed too -
but relative memory latency became much higher since then (comparing to cpu speed).

Also PPM has some common properties with BWT-based compression methods (ratio etc),
while BWT provides more options for speed optimizations, so PPM is not very popular lately.

> Also, what happened with Dmitry Shkarin's PPMII algorithm?

You can access most of its versions here: https://compression.ru/ds/
Also Shkarin participated in GDC-2020, so there're new builds of all his codecs
(very little difference from previous releases).

> How does PPMII compare to other, non-PPM approaches?

Ratio-wise, CM is significantly better.

Also, PPMd is beaten by BWT codecs in both speed and ratio,
while ppmonstr is not open-source and much slower anyway
(similar to CM in ratio and speed).

However PPM has benefits in small-block compression, since
table-based algorithms (ROLZ,BWT,CM) waste some time on
table initialization, while PPM can just reset the memory pool pointer.

[Gonzalo]

Also, PPMd is beaten by BWT codecs in both speed and ratio,

... which ones for example?

[Shelwien]

Most I guess?
Ratio-wise its not so simple, as BWT has more problems with local adaptation,
also PPM results on binary files can be improved with sparse models etc,
while its not really possible for BWT.
But sparse models are only available in ppmonstr, while ppmd is pretty similar to plain BWT.

21,388,296 33.473s 34.148s // ppmd -o10 -m256 -r1
22,325,416 19.387s 19.849s // ppmd -o10 -m256 -r0

27,343,261 12.084s 13.082s // ppms -o8

21,688,998 12.937s  8.294s // bsc -b51 -m0 -cp -e2 -p -t -T (256MB memory usage)
21,835,062 11.412s  6.656s // bsc -b51 -m0 -cp -e1 -p -t -T (faster entropy model)
21,820,628 11.600s  6.734s // bsc -b51 -m0 -cp -e1 -t -T (preproc enabled)

21,323,232 14.400s 15.763s // bcm 2.00a3 c51r

Maniscalco's and Lucas' works are probably better than old bsc,
but would likely require more preparation work for fair comparison.

[SolidComp]

> in terms of ratio, complexity, and speed tradeoffs?

Ratio is 5-10% higher than LZMA, which in turn is 10% higher than zstd.

What direction is a "higher" ratio pointing here? PPMd compresses more than LZMA, which compresses more than Zstd?

[Gonzalo]

Most I guess?
Ratio-wise its not so simple, as BWT has more problems with local adaptation,
also PPM results on binary files can be improved with sparse models etc,
while its not really possible for BWT.
But sparse models are only available in ppmonstr, while ppmd is pretty similar to plain BWT.

21,388,296 33.473s 34.148s // ppmd -o10 -m256 -r1
22,325,416 19.387s 19.849s // ppmd -o10 -m256 -r0

27,343,261 12.084s 13.082s // ppms -o8

21,688,998 12.937s  8.294s // bsc -b51 -m0 -cp -e2 -p -t -T (256MB memory usage)
21,835,062 11.412s  6.656s // bsc -b51 -m0 -cp -e1 -p -t -T (faster entropy model)
21,820,628 11.600s  6.734s // bsc -b51 -m0 -cp -e1 -t -T (preproc enabled)

21,323,232 14.400s 15.763s // bcm 2.00a3 c51r

Maniscalco's and Lucas' works are probably better than old bsc,
but would likely require more preparation work for fair comparison.

hmm... I find these results odd since in my computer ppmd is usually faster than bsc and bcm. I use Bulat's fazip with default options, which are -o10 -m48.
But even when I run exactly the same test as you I get different results.
BTW, what is the file? enwik8? I just took a json I have lying around, but the result is representative of what I see every day. I have a script that compares similar compressors and I run it pretty frequently.


The last command is how I usually run bsc

[Shelwien]

@SolidComp:

> What direction is a "higher" ratio pointing here? PPMd compresses more than LZMA, which compresses more than Zstd?

Yes. https://en.wikipedia.org/wiki/Data_c...tio#Definition

@Gonzalo:

Too many long matches, which is bad for BWT sort (too many redundant operations)
and good for PPMd (which keeps encoding whole bytes in maxorder context, while bsc is bitwise).
Your test also shows that enabled LZP preprocessing fixes that problem and provides 18.5% higher ratio.
Its likely that -b51 instead of -b1000 in 2nd bsc example would improve speed,
while the ratio would remain higher than ppmd's.
(51 is 256/5, where 5N is BWT memory usage; to match ppmd's -m256)

In any case, BWT has conceptual advantages for speed optimization,
as its batch processing vs incremental, plus there's a lot of entropy coding options
for speed/ratio tradeoffs.