skip contexts (e.g., AxBx)

[Paul W.]

I'm interested in what Charles Bloom calls "skip contexts," but when I search for that term, I only get a few hits, and they're to his rants.

What I'm talking about is matching things where you skip a symbol, e.g., AxBx may predict Cx.

Bloom says "skip contexts" are common in the top compressors... is there different terminology I should be searching for to find discussions of this sort of thing?

[Piotr Tarsa]

Matt calls it sparse models/ sparse contexts.

[Paul W.]

Ah, OK... I thought "sparse contexts" was something very different. (With Markovish contexts of a given order often not making predictions due to lack of stats?)

(Oh, now I search and find encode saying they're also called "binary" contexts... go figure.)

Anyhow, thanks!

[Piotr Tarsa]

IIRC I first saw the term 'binary context' when reading PPMII paper by Dmitry Shkarin and it meant contexts in which only one symbol was seen. It doesn't necessarily mean those contexts lack enough stats - it could be just that there's only one symbol seen in that context, eg "compres" context can be binary because the only valid next symbol is "s", unless you're compressing something that isn't valid English text.

Binary context is a concept present in bytewise compressors. In bitwise ones there's usually (? I'm not sure) no such distinction.