PPM with sparse contexts

[encode]

I wrote a dummy PPM that is able to deal with sparse contexts, just for experiments. You know that PAQ series compressors have a sparse model that improves compression on binary files, but it's CM and what about PPM? Previously, RKUC file compressor by Malcolm Taylor that is based on PPM have so called binary contexts - that is our sparse contexts in author terminology. Dunno how Malcolm exactly integrated that sparse stuff into PPM. Anyway, I have my own idea about that, and here is a test results:

No code has to be inserted here.

As you may see, sparse model helps on images but really hurts on other data types...

[willvarfar]

Is 'sparse' a term for 'spatial'?

[encode]

Nope. Read the PAQ papers & source. Sparse means context with gaps. i.e. AB*C, B*C, etc.

[Matt Mahoney]

For BMP files you could use x..x..
For more other files it looks like you need to figure out how to mix sparse contexts with regular contexts.

[encode]

I guess, if I would mix predictions, it would be CM, not PPM...

[Shelwien]

Afaik the PPM idea is to have the submodels ordered from most efficient to least.
Each order ideally should be able to perfectly (as far as it possible for given model)
encode >=50% of symbols passed to it (otherwise it kinda makes sense to process
the >50% alternative first, and minimize the escape coding overhead).

However, sparse models aren't really compatible with that - even for their best
data, they usually collect a lot of noise, and don't ever give near-perfect predictions.
So imho sparse models won't do any good when used directly as PPM orders.

Still, sparse model statistics sometimes can improve other predictions, so they
can be useful in mixed predictions.
For example, ppmonstr has some sparse submodels. Their predictions are
used in the SSE contexts there.