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,954
    Thanks
    359
    Thanked 332 Times in 131 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:

    Contextrafale.bmpbutterfly4.bmphellsky2.tgaenglish.dicacrord32.execalgary.tarbook1
    Regular77572662128326897267921861666736825551220761
    Sparse - x.x77045253674996517008000841739660845628227254
    Sparse - xx.77774253258006522718189661721026863233236659
    Sparse - xx.x76248364189796623968046331684328843246231250
    Analog - f877283951615096525248114571695642852266232490

    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,954
    Thanks
    359
    Thanked 332 Times in 131 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 778 Times in 485 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,954
    Thanks
    359
    Thanked 332 Times in 131 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,134
    Thanks
    179
    Thanked 921 Times in 469 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, 02:47
  2. Poor compression of bit-version of PPM
    By Stefan in forum Data Compression
    Replies: 20
    Last Post: 16th March 2010, 16: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, 20: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
  •