Results 1 to 6 of 6

Thread: PPM with sparse contexts

  1. #1
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts

    Lightbulb PPM with sparse contexts

    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...

  2. #2
    Member
    Join Date
    Feb 2010
    Location
    Nordic
    Posts
    200
    Thanks
    41
    Thanked 36 Times in 12 Posts
    Is 'sparse' a term for 'spatial'?

  3. #3
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    Nope. Read the PAQ papers & source. Sparse means context with gaps. i.e. AB*C, B*C, etc.

  4. #4
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    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.

  5. #5
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts

    Lightbulb

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

  6. #6
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,322
    Thanks
    209
    Thanked 1,001 Times in 526 Posts
    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.

Similar Threads

  1. PPMX v0.05 - new PPM-based compressor
    By encode in forum Data Compression
    Replies: 49
    Last Post: 28th July 2010, 03:47
  2. Poor compression of bit-version of PPM
    By Stefan in forum Data Compression
    Replies: 20
    Last Post: 16th March 2010, 17:58
  3. PPMX - a new PPM encoder
    By encode in forum Data Compression
    Replies: 14
    Last Post: 30th November 2008, 17:03
  4. TURTLE incoming... Fast PPM file compressor.
    By Nania Francesco in forum Forum Archive
    Replies: 104
    Last Post: 8th August 2007, 21:40

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •