Results 1 to 9 of 9

Thread: question about stationary and nonstationary

  1. #1
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    i've looked at http://www.cs.fit.edu/~mmahoney/compression/ . and i have a question: what's the difference between stationary and nonstationary? for example stationary and nonstationary order- 0 models or stationary and nonstationary ppm models.

    are nonstationary models characterized by limited history or by predicting bits one- by- one instead of coding entire byte at once?

    for example i have an idea of creating order- 2 model for my tarsalzp which will have a limit of, say, 50 symbols per context (instead of full 256) and, to avoid clogging the context, old symbols (ie. that haven't appeared in last, say, 100, occurences of that context) will be kicked out. will be that model stationary or nonstationary?

    i'm expecting answer from matt, 'cause i think he's expert in that field

  2. #2
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,505
    Thanks
    741
    Thanked 665 Times in 359 Posts
    the answer is simple: in stat. model all symbols has equal weight, in non-stat. recent symbols are "heavier". f.e. lz77 is non-stat model while lzw is stationary

  3. #3
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    so how to determine if 'my' order- 2 coder is stationary or not?

    and why fpaq isn't non- stationary? after all, it does rescaling periodically, so old symbols have lower weight.

  4. #4
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,982
    Thanks
    377
    Thanked 351 Times in 139 Posts
    Read the paper about PAQ1:
    http://www.cs.fit.edu/~mmahoney/compression/paq1.p df

    The C++ code:

    n[0]; // - count of 0s
    n[1]; // - count of 1s

    // stationary model update:

    if (++n[y] >= 255) { // if limit reached
    n[0] >>= 1; // halve both counts
    n[1] >>= 1;
    }

    // non stationary model update

    if (n[y] < 255) n[y]++; // increment count for current bit

    if (n[1 - y] > 2) // if count of an opposite bit is large enough,
    (n[1 - y] /= 2) += 1; // halve it

    // in other words, each time we update model statistics, we increase count of current bit, and discard old statistics by halving an opposite count.

    Hope this helps.


  5. #5
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    thanks. it helps

    especially that sentence from paper you mentioned:
    These are both
    stationary models, in the sense that the statistics used to estimate the probability (and therefore the code length) of a
    symbol are independent of the age of the training data.
    similar meaning to bulats answer but more precise

  6. #6
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,505
    Thanks
    741
    Thanked 665 Times in 359 Posts
    Quote Originally Posted by donkey7
    similar meaning to bulats answer but more precise
    i forget that i learnt these terms from this paper

    btw, look also at PPMD paper where Dmitry said about stat. model of ppmd and non-stat model of ppmostr

  7. #7
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    can you give me a link to that paper if it's in english? i have one paper from sharin's site ( http://compression.graphicon.ru/download/articles/ ppm/shkarin_2002dcc_ppmii_pdf.rar ), it's in english but it's outdated and it doesn't say anything about stationary and non- stationary models.

  8. #8
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,505
    Thanks
    741
    Thanked 665 Times in 359 Posts
    i don't have anything else. i reread this paper and now see that i misinterpredted differences between ppmd and ppmonstr

    (his russian paper written in 2001 and probably doesn't contain any more infoprmation)

  9. #9
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    what a pity... but ok

    do you know if ppmonstr is stationary or not? ppmonstr uses 0.5 mb more memory than baseline ppmd, so maybe that 0.5 mb contains some non- stationary model?

    (after some thinking)
    hmm, maybe it's stationary. i looked at squeeze chart and saw that it does badly on cd image which i guess is non- stationary data. lzp powered programs such as tarsalzp or turtle performs better than ppmonstr on that type of data - and lzp is a very non- stationary model.

Similar Threads

  1. LZC Question
    By moisesmcardona in forum Data Compression
    Replies: 3
    Last Post: 16th August 2009, 23:33
  2. RVLC Question
    By pessen in forum Data Compression
    Replies: 3
    Last Post: 11th July 2009, 04:29
  3. Noob question about dictionary size (and about rep)
    By SvenBent in forum Data Compression
    Replies: 1
    Last Post: 23rd January 2009, 01:35
  4. Dictionary to Archive Size Question
    By GipFace in forum Data Compression
    Replies: 6
    Last Post: 21st January 2009, 18:03
  5. Random Data Question.
    By Tribune in forum Data Compression
    Replies: 7
    Last Post: 13th June 2008, 20:30

Posting Permissions

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