Page 1 of 2 12 LastLast
Results 1 to 30 of 41

Thread: xp a rolz compressor

  1. #1
    Member
    Join Date
    Sep 2010
    Location
    ind
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Smile xp a rolz compressor

    Looking at LTCB and reading a few things on ROLZ ,
    Attached is my implemention of the gathered ideas.

    Thanks everyone
    Attached Files Attached Files

  2. #2
    Member
    Join Date
    Oct 2010
    Location
    Germany
    Posts
    275
    Thanks
    6
    Thanked 23 Times in 16 Posts
    Your compressor is very fast but not very good. What is the aim of this project?
    I compared it to other ROLZ implementions.

    Code:
    3.152.896 calgary.tar
      956.563 xp c9
      870.948 balz 1.15 ex
      784.683 rzm 0.07h

  3. #3
    Member
    Join Date
    Sep 2010
    Location
    ind
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts
    This is my first implementation of a rolz compressor, my intention is to learn while i develop this compressor.
    the algorithm has a 1MB window with 1k rolz offset per previous byte. my first aim was to defeat zip and now i want to improve this algorithm. Please give me some ideas on how to make it better.

    Thanks for your comments sebastian

  4. #4
    Member
    Join Date
    Oct 2010
    Location
    Germany
    Posts
    275
    Thanks
    6
    Thanked 23 Times in 16 Posts
    To pass balz (which sources are available) you've to add some context modelling techniques.

    So instead of encode(val) you do something like encode[context](val)
    where context could be a part of the history of the modelled subsource.
    (these are in fact conditional probabilities)

    Great improvements can be done by (sub-)optimal parsing.
    Instead of taking the longest match at a position you search for a better match at positions which are covered by the first match.

    This idea can be extended. You first do a longest-match-search at every position and assign every position a cost for encoding the token. This is a non-cyclic graph.
    Then you find the shortest path in this graph to build the optimal sequence of literals and matches. The big problem is assigning cost-values if you use an adaptive encoding for the tokens.

  5. #5
    Member
    Join Date
    Sep 2010
    Location
    ind
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts
    I would like to add that balz uses 60MB+ where as xp uses ~3MB
    One of my intentions is to reach compression near cabarc since it is lz77 with less memory
    below is slightly improved version of xp , with little bigger window
    xp now has only 3 level 0,1,2 where 0 is default
    Attached Files Attached Files

  6. #6
    Member
    Join Date
    Sep 2010
    Location
    ind
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Thanks for tips sebastian
    I will take a look at balz source.
    xp does simple parsing based few bytes look ahead and decides to reduce the current match length if it finds a longer matches at next few bytes, these are adjusted by the level option. I dont understand how to assign cost values to a match as i am using adaptive coding for literals and matches.
    Thanks

  7. #7
    Member
    Join Date
    Oct 2010
    Location
    Germany
    Posts
    275
    Thanks
    6
    Thanked 23 Times in 16 Posts
    Compression is slightly improved

    Code:
    3.152.896 calgary.tar
      956.563 xp c9 (old)
      939.813 xp c2 
      870.948 balz 1.15 ex
      784.683 rzm 0.07h
    I dont understand how to assign cost values to a match as i am using adaptive coding for literals and matches.
    There are numerous ways to do this. First you assign constants to match and literal costs based on some testset. This works better than expected.
    The next step would be to use some tables to collect the average coding cost of different literals and matches, because an 'A' might need fewer bits than a 'Z'.

    So you collect the matches and store them in a table. If the table is full, or if you encountered a literal, as every path has to go through it, you can stop filling the table.
    Assign cost values based on past encodings. Find the shortest path. Encode this path and update the cost tables.

    There is another approach but my language is too limited to describe it simple

    Secondly you should increase the table-size to 2^15 or 2^16 because 1k is too small if you update the table at every position.

  8. #8
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    According to your description, you are using order-1 ROLZ match finder. For speed (but less compression), you can use order-2 (i.e. use previous 2-bytes as ROLZ match finder context instead of only previous byte). By doing this, you can reduce ROLZ search depth dramatically (i.e. even 64 is enough). You can also try skipping "already matched data" for updating ROLZ hash table. It also boosts both compression and decompression speed. But, keep in mind, with range coding, ROLZ typically bounded around ~10-15 MB/sec decompression speed. If you need more speed (which makes sense if you chose LZ77 class compression), you may consider pure LZ77 implementation.

    BTW, near-optimal parsing is another story, I think you should focus on modeling first. Because, optimal-parsing boosts "only" your modeling. There are several ideas about optimal parsing for LZ77 in this forum. You can find by searching threads. Keep in mind, ROLZ's optimal parsing is more tricky because of ROLZ hash table. I think, order-2 ROLZ match finder with 2 bytes look-ahead is usually enough.
    BIT Archiver homepage: www.osmanturan.com

  9. #9
    Member
    Join Date
    Oct 2010
    Location
    Germany
    Posts
    275
    Thanks
    6
    Thanked 23 Times in 16 Posts
    Quote Originally Posted by osmanturan View Post
    Keep in mind, ROLZ's optimal parsing is more tricky because of ROLZ hash table.
    If you update the offset-table at every window position this is not the case. I've written an LZ77 Encoder with optimal parsing.
    To plug ROLZ into it, I only needed to replace the "FindLongestMatch" function - and it's all working as expected.

  10. #10
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Sebastian View Post
    If you update the offset-table at every window position this is not the case. I've written an LZ77 Encoder with optimal parsing.
    To plug ROLZ into it, I only needed to replace the "FindLongestMatch" function - and it's all working as expected.
    Despite being seen unaware of this, I actually do aware of it I think, spending optimal parsing efforts on pure LZ77 makes much more sense.
    BIT Archiver homepage: www.osmanturan.com

  11. #11
    Member
    Join Date
    Oct 2010
    Location
    Germany
    Posts
    275
    Thanks
    6
    Thanked 23 Times in 16 Posts
    Quote Originally Posted by osmanturan View Post
    I think, spending optimal parsing efforts on pure LZ77 makes much more sense.
    Why? The same limitations of suboptimal parsing apply to ROLZ too. The effect might be a little higher on LZ77 because of larger distances and you have to take more care on literal-coding in ROLZ but the latter gives generally better compression on most files. RZM is a good example for it, as I'm trying hard to beat it. Sadly I removed the code in my encoder which uses greedy parsing, so this is the only comparison I have. You see, even for LZ77 and especially text-files the effect is small as long as you don't put too much effort in parsing.

    Code:
    compression of book1 (768.771 bytes)
    267.783 bytes: (lazy matching with max-dist: 4 bytes, matching took 3s)
    262.058 bytes: (optimal matching using constant costs for match/literal, matching took 5s)
    


    Doing o2 on literals and better parsing dropped this to about 253.xxx but doing ROLZ with the exact same entropy encoding stage (which is optimized on LZ77) gets instantly 244.xxx
    Last edited by Sebastian; 17th November 2010 at 22:53.

  12. #12
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    With ROLZ, you are almost bounded with offset-table (by considering speed). Because, you have to rebuild the table on decompression too and thus slows down the decompression speed. IMO, ROLZ has a benefit for finding matches quickly rather than achiving really good compression ratios. And optimal parsing is just for gaining better compression ratio. So, as a result, putting LZ77 among optimal parsing is much better choice IMO.

    I think, ROLZ is suited when we are dealing with very weak modeling (such as byte codes or semi-adaptive huffman codes). Because, implicit match position to ROLZ offset translation reduces symbol ranges and thus gains compression ratio.

    As a conclusion in my mind, I love LZMA like implementations (which is LZ77+optimal parsing) are suited for mid-range compression with fast decompression, and SLUG X like implementations (which is ROLZ + semi-adaptive huffman) is suited for very fast but weak compression (faster-than-HDD class compressors).

    Seems you are taking wrong. These are just my opinions One can use optimal parsing among ROLZ for better compression But, IMO, optimal parsing among LZ77 has more rooms for further compression (not to mentioned about decompression speed).
    BIT Archiver homepage: www.osmanturan.com

  13. #13
    Member
    Join Date
    Oct 2010
    Location
    Germany
    Posts
    275
    Thanks
    6
    Thanked 23 Times in 16 Posts
    Quote Originally Posted by osmanturan View Post
    Because, you have to rebuild the table on decompression too and thus slows down the decompression speed.
    You only have to overwrite the current table-position. Don't do something like in BALZ 1.15
    where the whole table is shifted if you can do it cyclic. You could do this even faster with a rolling buffer.

    This is pretty self-explanatory I think
    Code:
    void cROLZ::AddCurPos()
    {
      const int wpos=Window->GetWinPos();
      tbucket *bkt=&table[Window->GetChPos(wpos-1)];
      bkt->data[bkt->idx]=wpos;
      bkt->idx = (bkt->idx + 1) & tbl_mask;
    }
    I wouldn't call this "building" in any way.

    But then I am no programmer, and only interested in maximum compression archivable with a specific algorithm.
    Thus if you are able to design a pure (low order literal) LZ77-Coder that hits 800kb on calgary.tar I'm unworthy because I can not

    Sure there are situations where LZ77 is better, especially long distance matches are a problem for ROLZ but there are also cases where LZ77 totally fails, like "FP.log".

    Just look at this table to see what I mean (same parsing and ad-hoc entropy encoding for both)
    Code:
              LZ77     ROLZ
    bib     29.206   27.574
    book1  253.667  244.882
    book2  167.461  159.652
    geo     55.629   55.609 (parser eliminates nearly all matches)
    news   115.051  112.234
    obj1     9.301    9.489
    obj2    66.266   67.526
    paper1  16.584   16.057
    paper2  26.199   25.059
    pic     42.138   45.691
    progc   12.155   11.928
    progl   14.519   13.895
    progp   10.003    9.758
    trans   16.241   15.430
    Last edited by Sebastian; 18th November 2010 at 01:40.

  14. #14
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Sebastian View Post
    You only have to overwrite the current table-position. Don't do something like in BALZ 1.15
    where the whole table is shifted if you can do it cyclic. You could do this even faster with a rolling buffer.

    This is pretty self-explanatory I think
    Code:
    void cROLZ::AddCurPos()
    {
      const int wpos=Window->GetWinPos();
      tbucket *bkt=&table[Window->GetChPos(wpos-1)];
      bkt->data[bkt->idx]=wpos;
      bkt->idx = (bkt->idx + 1) & tbl_mask;
    }
    I wouldn't call this "building" in any way.
    Well... I'm very well aware of cyclic buffers Sorry for using a misappropriate word. It should be maintenance or update. In both cases where it's rebuild completely by shifting or cycling, it requires extra memory accesses. And all of people in this forum who capable of writing any class of compressor try to avoid increasing memory accesses because of speed concern

    Quote Originally Posted by Sebastian View Post
    But then I am no programmer, and only interested in maximum compression archivable with a specific algorithm.
    Thus if you are able to design a pure (low order literal) LZ77-Coder that hits 800kb on calgary.tar I'm unworthy because I can not
    Well, I'm not challenging any one At least I need more free time to do such things Unfortunately, I don't

    Quote Originally Posted by Sebastian View Post
    Sure there are situations where LZ77 is better, especially long distance matches are a problem for ROLZ but there are also cases where LZ77 totally fails, like "FP.log".
    BTW, IIRC, Christian claimed that he found a way to deal with distant matches in his RZM. Maybe, you can find a way to doing this for beating RZM (you stated it is your goal for your ROLZ, right?)

    Quote Originally Posted by Sebastian View Post
    Just look at this table to see what I mean (same parsing and ad-hoc entropy encoding for both)
    Code:
              LZ77     ROLZ
    bib     29.206   27.574
    book1  253.667  244.882
    book2  167.461  159.652
    geo     55.629   55.609 (parser eliminates nearly all matches)
    news   115.051  112.234
    obj1     9.301    9.489
    obj2    66.266   67.526
    paper1  16.584   16.057
    paper2  26.199   25.059
    pic     42.138   45.691
    progc   12.155   11.928
    progl   14.519   13.895
    progp   10.003    9.758
    trans   16.241   15.430
    If we are talking about LZ class compressor (including ROLZ), I think, it's better to include timing on benchmark. BTW, this differences are caused by distance modeling differences between LZ and ROLZ IMO. Seems you are using order-1 match finder for ROLZ. What about LZ match finder? Or maybe further details for both - LZ and ROLZ (including modeling of each LZ/ROLZ symbols).
    BIT Archiver homepage: www.osmanturan.com

  15. #15
    Member
    Join Date
    Oct 2010
    Location
    Germany
    Posts
    275
    Thanks
    6
    Thanked 23 Times in 16 Posts
    Ok I'm not the TS and this is going off-topic imo, so lets stop here as I will provide more informations+source when I have the time.

    Quote Originally Posted by osmanturan View Post
    If we are talking about LZ class compressor (including ROLZ), I think, it's better to include timing on benchmark.
    Seems that I'm the only person here not interested in (compression-)speed.

    BTW, this differences are caused by distance modeling differences between LZ and ROLZ IMO. Seems you are using order-1 match finder for ROLZ. What about LZ match finder? Or maybe further details for both - LZ and ROLZ (including modeling of each LZ/ROLZ symbols).
    There is exactly no! difference in modelling the tokens. I made an LZ77 coder and added ROLZ ad-hoc because it fitted nicely in my class structure. With propper coding of bucket numbers the ROLZ results should be even better. Now the buckets are encoded as a LZ77-distance.

  16. #16
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Sebastian View Post
    Ok I'm not the TS and...
    Well, what is it???
    Quote Originally Posted by Sebastian View Post
    ...this is going off-topic imo, so lets stop here as I will provide more informations+source when I have the time.
    Ok. Whatever you like.
    Quote Originally Posted by Sebastian View Post
    Seems that I'm the only person here not interested in (compression-)speed.
    Most of people in here, considers speed if the compressor is a LZ class compressor. If you are going to play for Hutter-Prize, then I wouldn't ask any speed statistics
    Quote Originally Posted by Sebastian View Post
    There is exactly no! difference in modelling the tokens. I made an LZ77 coder and added ROLZ ad-hoc because it fitted nicely in my class structure. With propper coding of bucket numbers the ROLZ results should be even better. Now the buckets are encoded as a LZ77-distance.
    Well, seems again there is a misunderstanding. Modeling can be same for both ROLZ offset-index and LZ77 match position. But, code-lengths would be shorten for ROLZ case even same modeling was used. Because, as you already know, ROLZ offset-indicies have narrower range comparing to LZ77 match distance. I was talking about this difference.
    BIT Archiver homepage: www.osmanturan.com

  17. #17
    Member
    Join Date
    Oct 2010
    Location
    Germany
    Posts
    275
    Thanks
    6
    Thanked 23 Times in 16 Posts
    Quote Originally Posted by osmanturan View Post
    Well, what is it???
    Thread-Starter

    Well, seems again there is a misunderstanding. Modeling can be same for both ROLZ offset-index and LZ77 match position. But, code-lengths would be shorten for ROLZ case even same modeling was used. Because, as you already know, ROLZ offset-indicies have narrower range comparing to LZ77 match distance. I was talking about this difference.
    You explicit stated "this differences are caused by distance modeling differences" so it's at least no misunderstanding on my side
    But sure you're right. ROLZ have narrower offset range but depend on prefix context which does not work very good on binary files.

  18. #18
    Member
    Join Date
    Sep 2010
    Location
    ind
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts

    xp with rolz2

    yes i am using a o1 rolz and now implemented rolz2 and reduced search from 1k to 256.
    also the level option is used to select the amount of lookahead,(no cost related stuff , it is only checking for longer length of match) the table is updated only on match boundaries , do you think its better to update withing the matches also and any more suggestions?

    the literals and offset/length are encoded as follows, i tried few ways and this suited best as described below.
    one array of stats for literals + offset(3bits) + length(3bits) ,
    one array for offsets this is used if offset exceed 3bits
    one array for length and this is used if length exceed 3bits
    Do you suggest anything better here ?

    i wish to improve compression as much as possible before thinking about speed as this is more of a learning project for me. How can this be improved ?

    attached rolz2 xp
    Attached Files Attached Files

  19. #19
    Member
    Join Date
    Oct 2010
    Location
    Germany
    Posts
    275
    Thanks
    6
    Thanked 23 Times in 16 Posts
    A little better, but I think you're limited with 2-byte ROLZ


    Code:
              LZ77     ROLZ      RZM     BALZ    XP c2
    bib     29.206   27.574   29.158   31.127   33.557
    book1  253.667  244.882  246.858  269.339  280.459
    book2  167.461  159.652  161.100  174.908  183.671
    geo     55.629   55.609   53.776   61.698   69.695 
    news   115.051  112.234  115.152  122.148  129.345
    obj1     9.301    9.489   10.170   11.542   11.195
    obj2    66.266   67.526   64.016   76.230   85.053
    paper1  16.584   16.057   17.344   18.691   18.755
    paper2  26.199   25.059   26.700   28.450   28.923
    pic     42.138   45.691   40.540   51.583   53.644
    progc   12.155   11.928   12.797   14.097   13.884
    progl   14.519   13.895   14.753   15.868   16.205
    progp   10.003    9.758   10.487   11.736   11.627
    trans   16.241   15.430   16.339   17.984   19.003
           834.420  814.784  819.190  905.401  955.016
    do you think its better to update withing the matches also and any more suggestions?
    Updating the table on match boundaries lets you use a small table thus reducing the range for offsets. On the other side optimal parsing is much harder to implement.
    It's a choice you've to make.

    one array of stats for literals + offset(3bits) + length(3bits) ,
    one array for offsets this is used if offset exceed 3bits
    one array for length and this is used if length exceed 3bits
    Do you suggest anything better here ?
    I don't really understand. What are stats in this context? Counters for symbol propabilities?
    Do you encode on a binary alphabet (as in BALZ)? First try order1 literal encoding, this gives a good boost on the text files, so you should be able to hit ~270k on book1.

    i wish to improve compression as much as possible before thinking about speed as this is more of a learning project for me. How can this be improved ?
    As already mentioned. Better parsing. Better symbol encoding. That's all the difference. Look again at BALZ and see how it's done properly.
    Unless you let us know some of the internals or let us look into the source more help is not really possible.

    Also "compression as much as possible" is the wrong idea because LZ-based compressors have the property of fast decoding. That means you could implement an optimal parser
    and add a high order PPM/CM model as literal stage. A good parser will eliminate nearly all matches and use the context model instead. But then you loose the nice property of high asymmetry.
    If you're looking for maximum compression use another algorithm as PPM/CM instead.
    Last edited by Sebastian; 18th November 2010 at 12:36.

  20. #20
    Member
    Join Date
    Sep 2010
    Location
    ind
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts
    >>but I think you're limited with 2-byte ROLZ
    Do you mean 3 byte rolz would be better ?

    >>I don't really understand. What are stats in this context? Counters for symbol propabilities?

    Do you encode on a binary alphabet (as in BALZ)? First try order1 literal encoding
    yes those are symbol frequencies and it is range coded (not using binary counters like balz)
    I will try to explain the encoding in more detail
    i have 3 tables of frequencies
    frq1 is 321 size with 256(literals)+1(eof)+64(3bit offset/3 bit length)
    frq2 is 256 offset frequencies table
    frq3 is 256 length frequencies table
    when a literal is being output frq1 is used to code it
    if a match is found frq1 is used to code it. but if the offset is more then 3 bits it uses the frq2 to encode the larger offset
    and if the length is more then 3 it uses frq3 to encode the length.
    example if match offset/len = 2,3 , this needs only frq1
    if offset/len = 120,2 this uses frq1 to code 7,2 and frq2 to code (120-7)
    if offset/len = 2,50 this uses frq1 to code 2,7 and frq3 to code (50-7)
    if offset/len = 210,40 then frq1 codes 7,7 and frq2 codes (210-7) and frq3 codes (40-7)
    (to be exact it is 257+(7<<3)+7 coded from frq1 and so on ...)
    You can say this is similar to the way lzx codes its literal , matches from an old paper that i read.

    >> Do you have source for the lz77 and rolz used in the comparision table ?

    I am very curious to know how they achieve such good results

    thank you very much once again
    Last edited by pmcontext; 18th November 2010 at 14:54.

  21. #21
    Member
    Join Date
    Oct 2010
    Location
    Germany
    Posts
    275
    Thanks
    6
    Thanked 23 Times in 16 Posts
    Quote Originally Posted by pmcontext View Post
    >>but I think you're limited with 2-byte ROLZ
    Do you mean 3 byte rolz would be better ?


    I think 1 byte ROLZ is just good enough.

    yes those are symbol frequencies and it is range coded (not using binary counters like balz)


    Try to use a binary decomposition because it's easier to get good results with it. Otherwise you really need secondary escape estimation for higher order modelling.

    I will try to explain the encoding in more detail
    i have 3 tables of frequencies
    frq1 is 321 size with 256(literals)+1(eof)+64(3bit offset/3 bit length)
    frq2 is 256 offset frequencies table
    frq3 is 256 length frequencies table
    when a literal is being output frq1 is used to code it
    if a match is found frq1 is used to code it. but if the offset is more then 3 bits it uses the frq2 to encode the larger offset
    and if the length is more then 3 it uses frq3 to encode the length.
    example if match offset/len = 2,3 , this needs only frq1
    if offset/len = 120,2 this uses frq1 to code 7,2 and frq2 to code (120-7)
    if offset/len = 2,50 this uses frq1 to code 2,7 and frq3 to code (50-7)
    if offset/len = 210,40 then frq1 codes 7,7 and frq2 codes (210-7) and frq3 codes (40-7)
    (to be exact it is 257+(7<<3)+7 coded from frq1 and so on ...)
    So you're doing straight order0 symbol encoding. Also using the literal-table
    to encode the match/literal-flags is not a good choice imo. Gain is always possible if you seperate different probability distributions and use a specific model. One model for flags, one for lens and one for positions with specific contexts.

    Do you have source for the lz77 and rolz used in the comparision table
    I am very curious to know how they achieve such good results


    Yes I have the source, because I coded them. The symbol models are not very good and more like cracking a nut with a sledge-hammer
    But again nothing special. Flags, lens and offsets are encoded with some small context (last byte is suitable for ROLZ but I didn't tested that yet).
    Offsets use the quantised matchlen as context. Literals are encoded using a mixed o2-o1-o0-model. As I'm doing heavier stuff than RZM there's much to do.


  22. #22
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,612
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Quote Originally Posted by Sebastian View Post
    Code:
              LZ77     ROLZ      RZM     BALZ    XP c2
    bib     29.206   27.574   29.158   31.127   33.557
    book1  253.667  244.882  246.858  269.339  280.459
    book2  167.461  159.652  161.100  174.908  183.671
    geo     55.629   55.609   53.776   61.698   69.695 
    news   115.051  112.234  115.152  122.148  129.345
    obj1     9.301    9.489   10.170   11.542   11.195
    obj2    66.266   67.526   64.016   76.230   85.053
    paper1  16.584   16.057   17.344   18.691   18.755
    paper2  26.199   25.059   26.700   28.450   28.923
    pic     42.138   45.691   40.540   51.583   53.644
    progc   12.155   11.928   12.797   14.097   13.884
    progl   14.519   13.895   14.753   15.868   16.205
    progp   10.003    9.758   10.487   11.736   11.627
    trans   16.241   15.430   16.339   17.984   19.003
           834.420  814.784  819.190  905.401  955.016
    Beating RZM is a remarkable feat, could you post compression / decompression times?

  23. #23
    Member
    Join Date
    Oct 2010
    Location
    Germany
    Posts
    275
    Thanks
    6
    Thanked 23 Times in 16 Posts
    It's slower, because I use heavier modelling. When I use o1-literal I am still a large enough gap behind. Also I don't see where I am beating RZM.
    Single file calgary compression favors models which are stationary. Look at pic and obj2 to see the fail.

    The question is where to stop? I had a literal model which gave me 53k on geo too. I could add more and more mixing and submodels just to "show off".

  24. #24
    Member
    Join Date
    Sep 2010
    Location
    ind
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @Sebastian

    1)
    Looking at the comparision table i notice your lz77 is doing worse then rolz , why is that ? i thought lz77 with good parsing can do better then rolz or am i wrong.

    2) Is your implementation of lz77 and rolz opensource ? if yes can you send me a copy or upload it anywhere (my email pmcontext AT gmail) . I would like to learn how you have implemented them.

    3) i have done ppmc type of compressor but when i looked at ppmd it was too complex for me. what is secondry escape estimation and how to implement it? and what is inheritence and how to do it ? looking at the source i cant understand this. any help here please ? i might use an order2 ppm as backend if i can understand these ideas

    Thanks a lot for your time
    Last edited by pmcontext; 19th November 2010 at 09:29.

  25. #25
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    > i thought lz77 with good parsing can do better then rolz or am i wrong.

    lz77 can encode any offset in the window, and rolz has limited offsets
    per context, thus lz77 has to encode a few more bits per match offset -
    so certainly there's more redundancy.

    > 3) i have done ppmc type of compressor but when i looked at ppmd it
    > was too complex for me.

    Did you look at original ppmd or ppmd_sh?

    http://ctxmodel.net/files/PPMd/ppmd_Jr1_sh8.rar
    file_process.inc - ProcessFile() with file (de)compression loop
    ppmd_byte.inc - ProcessByte() = byte (de)compression function
    ppmd_proc0.inc - handler for contexts with single symbol (+escape = binary)
    ppmd_proc1.inc - handler for maxorder with multiple symbols ("nonmasked")
    ppmd_proc2.inc - handler for other contexts ("masked")

    Although, I guess, you have to understand how bytewise arithmetic coding
    works, its considerably different from bitwise coding.
    But overall, imho ppmd's main loop is pretty clear and actually very
    typical for any PPM - counter storage and probability estimation can vary,
    but ProcessByte() structure just has to be like that.
    For example, context type handlers can be merged, but it would hurt
    compression, because having special cases with different update
    (etc) parameters is what improves it.

    There's Mark Nelson's comp2 btw:
    http://ctxmodel.net/files/PPMd/nelson_comp2.rar
    ppmd readme says:
    > [2] Very descriptive M.R.Nelson's COMP-2 program (PPMd is based on it).
    > COMP-2 is in http://www.compression.ru/download/articles/ppm/
    > nelson_1991_ddj_arithmetic_modeling_html.rar

    But I'm certain that ppmd (or ppmd_sh at least) is much more readable.

    > what is secondry escape estimation and how to implement it?

    Well, the idea is to estimate escape probabilities across contexts -
    there's not enough information to predict escape in new contexts,
    but you can use statistics from multiple new contexts etc.
    Anyway, I thought that you understand how SSE works? So, its called
    SEE when applied to escapes .

    > and what is inheritence and how to do it ?

    You understand how a CM with full mixing works, right?
    So, imagine that we invented a way to update mixed probabilities
    instead of usual counters
    (there's nothing special though - suppose you have
    p = p1 + (p2-p1)*w, and counter updates are
    p1' = p1*(1-r)+bit*r
    p2' = p2*(1-r)+bit*r
    Thus
    p' = p1*(1-r)*(1-w) + p2*(1-r)*w + bit*r = p*(1-r) + bit*r
    So you can replace a static mix of two such counters with a single counter)
    This basically means that we can turn a CM with static mixing into PPM
    by maintaining a mixed probability of current and lower orders in each context.

    But then there's an exception - when you add a new context, you have to
    initialize the probability for it, so that there'd be a correct mixed
    value:
    pmix_init = p_init + (p-p_init)*w
    Where p_init is your initial probability estimation for this specific
    context (eg. 0.5) and p is the lower order mix.

    Also in PPM there's an additional optimization with escapes.
    Escape means "any of symbols not encountered in current context",
    and it should have the corresponding probability (sum of probabilities
    of these symbols).
    I mean, in a dumb implementation, you can have all symbols defined
    in all contexts, then to compute the escape probability, you'd have
    to sum all the probabilities of "unknown" symbols in current context.
    So its a memory+speed optimization, but because of that you also
    have to be careful with escape probability when adding a new symbol
    to a context - the previous (before update) new symbol's probability
    has to be subtracted from escape probability (because that's where
    that symbol was hiding before).

    So this kind of initialization of new symbols in PPM contexts is
    called "inheritance", because instead of starting with fixed prediction,
    the context "inherits" the probability from lower order.

    > i might use an order2 ppm as backend if i can understand these ideas

    Imho that's a weird idea - at o2 you won't gain so much from replacing
    mixing with PPM... actually always updating 3 counters would be likely
    faster than updating only the highest order, but having to mess with
    escape, masking etc. Also to enable this kind of "mixed probability caching",
    you have to sacrifice adaptive mixing weights and uneven counters updates -
    its not worth the trouble I think.

  26. #26
    Member
    Join Date
    Sep 2010
    Location
    ind
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Hi
    Modified the output to o1
    compression has improved a little

    book1 268993

    Thank you very much for the detailed replies and your time
    Attached Files Attached Files
    Last edited by pmcontext; 19th November 2010 at 21:52.

  27. #27
    Tester

    Join Date
    May 2008
    Location
    St-Petersburg, Russia
    Posts
    182
    Thanks
    3
    Thanked 0 Times in 0 Posts
    version 21:45 has crc errors after decompression on my files...

  28. #28
    Member
    Join Date
    Sep 2010
    Location
    ind
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts
    version 21:45 ? what is this
    i will test this some more
    Last edited by pmcontext; 20th November 2010 at 06:22.

  29. #29
    Member
    Join Date
    Sep 2010
    Location
    ind
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Hi
    Thank you for heads up on the bug. it is fixed now.
    the problem was in the wrong context for encoding eof.
    after adding 2byte rolz , i didnt realise that was taking up 67 MB
    went back to 1byte rolz this uses around 8 MB.

    Thanks
    Attached Files Attached Files

  30. #30
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Can you specify a version number within rar file name? We have too many xp.rar files here!

Page 1 of 2 12 LastLast

Similar Threads

  1. BALZ - An Open-Source ROLZ-based compressor
    By encode in forum Data Compression
    Replies: 60
    Last Post: 6th March 2015, 17:47
  2. ROLZ explanation?
    By Trixter in forum Data Compression
    Replies: 5
    Last Post: 10th June 2008, 18:24
  3. RZM - a dull ROLZ compression engine
    By Christian in forum Forum Archive
    Replies: 178
    Last Post: 1st May 2008, 21:26
  4. A small article on ROLZ (Russian)
    By encode in forum Forum Archive
    Replies: 21
    Last Post: 29th April 2007, 15:18

Posting Permissions

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