09-12-10 - PPM vs CM

Let me do a quick sketch of how PPM works vs how CM works to try to highlight the actual difference, sort of like I did for Huffman to Arithmetic , but I won't do as good of a job.

PPM :

make a few contexts of previous characters
  order4 = * ((U32 *)(ptr-4));
  etc.. 

look up observed counts from each context :

counts_o4 = lookup_stats( order4 );
counts_o2 = lookup_stats( order2 );
counts_o1 = lookup_stats( order1 );
counts_o0 = lookup_stats( order0 );

estimate escape probability from counts at each context :

esc_o4 = estimate_escape( order4 );
esc_o2 = estimate_escape( order2 );
...

code in order from most likely best to least :

if ( arithmetic_code( (1-esc_o4) * counts_o4 ) ) return; else arithmetic_code( esc_o4 );
exclude counts_o4
if ( arithmetic_code( (1-esc_o2) * counts_o2 ) ) return; else arithmetic_code( esc_o2 );
exclude counts_o2
...

update counts :
counts_o4 += sym;
...

Now let's do context mixing :

CM :

make a few contexts of previous characters
  order4 = * ((U32 *)(ptr-4));
  etc.. 

look up observed counts from each context :

counts_o4 = lookup_stats( order4 );
counts_o2 = lookup_stats( order2 );
counts_o1 = lookup_stats( order1 );
counts_o0 = lookup_stats( order0 );

estimate weights from counts at each context :

w_o4 = estimate_weight( order4 );
w_o2 = estimate_weight( order2 );
...

make blended counts :
counts = w_o4 * counts_o4 + w_o2 * counts_o2 + ...

now code :
arithmetic_code( counts );
...

update counts :
counts_o4 += sym;
...

It should be clear we can put them together :

<FONT COLOR=#9C9C9C>
make a few contexts of previous characters
  order4 = * ((U32 *)(ptr-4));
  etc.. 

look up observed counts from each context :

counts_o4 = lookup_stats( order4 );
counts_o2 = lookup_stats( order2 );
counts_o1 = lookup_stats( order1 );
counts_o0 = lookup_stats( order0 );

<FONT COLOR=#009C00>
if ( CM )
{
    estimate weights from counts at each context :

    w_o4 = estimate_weight( order4 );
    w_o2 = estimate_weight( order2 );
    ...

    make blended counts :
    counts = w_o4 * counts_o4 + w_o2 * counts_o2 + ...

    // now code :
    arithmetic_code( counts );
    ...
}
<FONT COLOR=#0000FF>else PPM
{
    estimate escape probability from counts at each context :

    esc_o4 = estimate_escape( order4 );
    esc_o2 = estimate_escape( order2 );
    ...

    code in order from most likely best to least :

    if ( arithmetic_code( (1-esc_o4) * counts_o4 ) ) return; else arithmetic_code( esc_o4 );
    exclude counts_o4
    if ( arithmetic_code( (1-esc_o2) * counts_o2 ) ) return; else arithmetic_code( esc_o2 );
    exclude counts_o2
    ... 
}

<FONT COLOR=#9C9C9C>

update counts :
counts_o4 += sym;
...



In particular if we do our PPM in a rather inefficient way we can make them very similar :

<FONT COLOR=#9C9C9C>
make a few contexts of previous characters
  order4 = * ((U32 *)(ptr-4));
  etc.. 

look up observed counts from each context :

counts_o4 = lookup_stats( order4 );
counts_o2 = lookup_stats( order2 );
counts_o1 = lookup_stats( order1 );
counts_o0 = lookup_stats( order0 );

accumulate into blended_counts :
blended_counts = 0;

<FONT COLOR=#009C00>
if ( CM )
{
    estimate weights from counts at each context :

    w_o4 = estimate_weight( order4 );
    w_o2 = estimate_weight( order2 );
    ...


}<FONT COLOR=#0000FF>
else PPM
{
    estimate escape probability from counts at each context :

    esc_o4 = estimate_escape( order4 );
    esc_o2 = estimate_escape( order2 );
    ...

    do exclude :
    exclude counts_o4 from counts_o2
    exclude counts_o4,counts_o2 from counts_o1
    ...

    make weights :

    w_o4 = (1 - esc_04);
    w_o2 = esc_04 * (1 - esc_02);
    ...

}

<FONT COLOR=#9C9C9C>

make blended counts :
blended_counts += w_04 * counts_o4;
blended_counts += w_02 * counts_o2;
...

arithmetic_code( blended_counts );

update counts :
counts_o4 += sym;
...




Note that I haven't mentioned whether we are doing binary alphabet or large alphabet or any other practical issues, because it
doesn't affect the algorithm in a theoretical way.



While I'm at it, let me take the chance to mark up the PPM pseudocode with where "modern" PPM differs from "classical" PPM :
(by "modern" I mean 2002/PPMii and by "classical" I mean 1995/"before PPMZ").


PPM :

make a few contexts of previous characters
  order4 = * ((U32 *)(ptr-4));
  etc.. 
<FONT COLOR=#900000>
also make non-continuous contexts like
skip contexts : AxBx
contexts containing only a few top bits from each byte
contexts involving a word dictionary
contexts involving current position in the stream 

look up observed counts from each context :

counts_o4 = lookup_stats( order4 );
counts_o2 = lookup_stats( order2 );
counts_o1 = lookup_stats( order1 );
counts_o0 = lookup_stats( order0 );

<FONT COLOR=#900000>
possibly rescale counts using a "SEE" like operator
eg. use counts as an observation which you then model to predict coding probabilities

estimate escape probability from counts at each context :

esc_o4 = estimate_escape( order4 );
esc_o2 = estimate_escape( order2 );
...
<FONT COLOR=#900000>
secondary estimate escape using something like PPMZ
also not just using current context but also other contexts and side information


code in order from most likely best to least :
<FONT COLOR=#900000>
use LOE to choose best order to start from, not necessarily the largest context
also don't skip down through the full set, rather choose a reduced set


if ( arithmetic_code( (1-esc_o4) * counts_o4 ) ) return; else arithmetic_code( esc_o4 );
exclude counts_o4
if ( arithmetic_code( (1-esc_o2) * counts_o2 ) ) return; else arithmetic_code( esc_o2 );
exclude counts_o2
...

update counts :
counts_o4 += sym;
...
<FONT COLOR=#900000>
do "partial exclusion" like PPMii, do full update down to coded context
  and then reduced update to parents to percolate out information a bit
do "inheritance" like PPMii - novel contexts updated from parents
do "fuzzy updates" - don't just update your context but also neighbors
  which are judged to be similar in some way