Results 1 to 3 of 3

Thread: Idea: Smoothed probability

  1. #1
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts

    Idea: Smoothed probability

    With fpaq0p-like probability updates the weigths form a geometric sequence. This is generally desirable, but this poses a new problem. Consider such sequence:
    0000000100000000100000

    After bit 1 the probability of 1 will drastically go up and then next few 0's will be coded with much longes codes than the 0's right before next 1.

    My solution is to make smoothed counters by appending a bit history to a probability, ie instead of keeping an int value describing weighted probability of the history up to current point, we have a pair of (recent bit history trimmed to last N-bits, wegithed probability of the history up to the point where the bit history from the first tuple value begins). Additionally there could be a table that maps a bit history from that pair to a pair (weight of delayed probability, probabilty computed from the trimmed bit history). When updating, the current bit will be shifted in the trimmed bit history and the bit that was shifted out of the trimmed bit history will be used to update the delayed probability.

    What do you think?

    PS:
    Direct bit histories could be replaced with other types of states provided that a state corresponds exactly to some (trimmed or not) bit history, so we can update the delayed probability by checking which bits are shifted out from the new state.
    Last edited by Piotr Tarsa; 19th February 2013 at 19:27.

  2. #2
    Member
    Join Date
    Sep 2008
    Location
    France
    Posts
    856
    Thanks
    447
    Thanked 254 Times in 103 Posts
    Are you looking for State Machine ?

  3. #3
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,471
    Thanks
    26
    Thanked 120 Times in 94 Posts
    Actually, I had state machines in mind when writing this, but this is about counters. Even if you use indirect modelling you end up somewhere with counters. Ie you have to map the state to probability, no matter what you do in the meantime.

    A counter can be represented as a pair of counts (n0, n1) just like Jean-Marie Barone is doing in his SMAC (IIRC) or you can use fpaq0p-like counters (ie fixed update rate) or LPAQ-like counters (ie slowing down update rate). Pairs of counts are relatively immune to the oscillation problem I've described in first post, but they have other problems (eg the update rate doesn't converge if we're doing rescaling regularly). Usually people use fpaq0p-like or LPAQ-like counters and they are prone to the problem I've described above.

    LPAQ1-like counters update rate converges to some fixed rate after reaching a limit, becoming a fpaq0p-like counters, so I've analyzed the fpaq0p-like counters only.

Similar Threads

  1. Probability estimation
    By Shelwien in forum Data Compression
    Replies: 23
    Last Post: 13th April 2012, 20:49
  2. Probability estimation for near-empty contexts
    By Shelwien in forum Data Compression
    Replies: 0
    Last Post: 15th September 2010, 00:26
  3. Compression idea: Base conversion
    By Nightgunner5 in forum Data Compression
    Replies: 8
    Last Post: 30th October 2009, 07:58
  4. New Idea for Hybrid 7-Zip Archiver
    By DeathTheSheep in forum Data Compression
    Replies: 22
    Last Post: 30th December 2008, 22:57
  5. SSE, TSE & higher symbol probability estimations
    By Dmitry Shkarin in forum Forum Archive
    Replies: 4
    Last Post: 6th March 2008, 19:47

Posting Permissions

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