Page 1 of 6 123 ... LastLast
Results 1 to 30 of 172

Thread: CMM fast context mixing compressor

  1. #1
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Hello everyone!

    I enjoy reading this forum for a while, comp.compression seems to be (brain) dead! Congratulations to lzpm & quad, two nice things

    I'm working on a fast context mixing compressor, which should achieve around 2bpc while maintaining fast operation. i'll release the source code, when i think i did my best and stop development.

    http://freenet-homepage.de/toffer_86/cmm_06092007. zip

    Waiting for tests and feedback!
    Greets
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  2. #2
    Member
    Join Date
    Dec 2006
    Posts
    611
    Thanks
    0
    Thanked 1 Time in 1 Post
    Hi Chris and welcome to the forums!

    Performance on my testset (orig. size 30 309 194) compared to CCM:

    __program______size_______in___out _ speed (kB/s)
    CMM 070906___16 340 731___599 / 591
    CCM 1.23 (-6)__11 974 852___712 / 731

    PSD is compressed quite poorly (6 755 163 -> 3 747 484) although ~33 MB RAM was used during compression... still, nothing's better for compression programs developement than a little bit of competition

  3. #3
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts
    Thanks Chris! Welcome to the forum!

  4. #4
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Thanks for the first reply.

    As i said, there's _A LOT_ of room for improvement. Just bare order 1-5 context mixing (i'm using 16m bit contexts, hashed, 2 bytes each -> 32mb) with fixed weights, no special models, filters, sse, etc. Increasing memory would help, but first i want to improve the main algorithm.

    At the moment I'm working on a simple mechanism to replace 1 to 4 byte phrases by 1 byte codes.

    If I'm able to reduce the original amount of data to say 80% the overall speed will raise to about X/.8 kB/s (X is the original speed), since the context mixer is a lot slower than the phrase substitution. Maybe there's a (small) improvement in compression.

    If this simple approach doesn't work i'll try lzp and use context mixing for literal and match length output.

    Just ideas....

    If Christian reads this: what characteristics does your ccm have compared to mine (see above)? Any suggestions?

    to Matt: could you give me a short explanation about how the paq state representation of bit histories is derived form (non)stationary counters?
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  5. #5
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    Quote Originally Posted by toffer
    to Matt: could you give me a short explanation about how the paq state representation of bit histories is derived form (non)stationary counters?
    In PAQ6 I mapped contexts to bit histories that represented the 0 and 1 counts. For example, if you saw 2 zeros and 2 ones, you would guess that the next bit would be 1 with probability 0.5. But sometimes the data is nonstationary, so the more recent bits are better predictors. So if the history was 0011 you would more likely predict a 1 than a 0. But it depends on the data. What I did in PAQ6 was a compromise. If the 0 count is large and you see a 1, then you increment the 1 count and you also discard some of the 0 count (half of the count above 2, after lots of experimenting) which tends to favor newer data.

    In PAQ7/8 and LPAQ1 I let the program figure out if the data is stationary or not. A state just represents the bit history, say 0011, and that is mapped to a probability by a lookup table (StateMap). After the bit is compressed the table entry is adjusted in the direction of what would have been the correct guess.

    If you use 8 bit states to represent histories then you can only have 256 possible histories. PAQ7/8/LPAQ1 all use the same tables, representing complete histories up to 4 bits. For longer histories, the state represents a count of 0 and 1 bits plus (sometimes) whether the last bit was a 0 or 1 (e.g. 7 zeros, 2 ones, and the most recent bit was 0). If the counts get too large, then it goes to a state with about the same ratio of zeros to ones. For example, if a 1 bit was seen and there was no state for (7, 3), then it might go to (5, 2) instead.

    The actual limits are (41, 0), (40, 1), (12, 2), (5, 3), (4, 4), (3, 5), (2, 12), (1, 40), and (0, 41). The state only includes information about the last bit if the total count is 15 or less, and both counts are not 0. In PAQ7/8 but not LPAQ1 I use randomized updates for large counts to increase the effective range.

    In paq8o.cpp the code to generate the state table is commented out. Maybe you can play with this to improve compression a bit (although I already did a lot of experimenting).

    OK, that was not so short.

  6. #6
    Member
    Join Date
    Sep 2007
    Location
    Denmark
    Posts
    856
    Thanks
    45
    Thanked 104 Times in 82 Posts
    its always nice to se some competition to push the envelope..
    But om not impressed by CMM
    it compressed worse than CCM and grzip2. and was about twice the time to due it compared to CCM.

    well its a good start from the compression ratio side. but it need to get great improvements in speed to be competitive

  7. #7
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 150 Times in 18 Posts
    Quote Originally Posted by toffer
    If Christian reads this: what characteristics does your ccm have compared to mine (see above)? Any suggestions?
    If I recall correct ccm mixes orders 1-6. It does nibble based hashing with simple collision handling. Additionally, it has a match model which is quite similar to that of lpaq1. Besides, it does have some sparse models and models some other stuff implicitly. Further on, you can implement a mechanism to turn models on/off on the fly to improve speed. You should definitely add some probability mapping and dynamic model mixing since plain "naked" models and fixed weights gently tend to leave a lot of bits behind. Some simple data filters can help, too. As a note, if you want to go for speed youll have to decide against compression ratio almost always.

    @all:
    Sorry that Ive been very absent over the last months. Ive had some important exams and now I just started working on my final thesis. So, no time working on compression related things anymore.

  8. #8
    Tester
    Stephan Busch's Avatar
    Join Date
    May 2008
    Location
    Bremen, Germany
    Posts
    872
    Thanks
    457
    Thanked 175 Times in 85 Posts
    I hope, Christian, that, when your thesis time is over, you'll remember us and your marvellous CCM

  9. #9
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Hi again!

    Thanks for your remarks and suggestions.

    I've got an idea how to switch between models, based on coding cost dependent on context and nibble frequency. This is the first thing i'll start to implement and test. Maybe i've finished it tomorrow, my girlfriend is getting on my nerves today ...

    The phrase substition seems to be inefficient, compression is lost (huh:shame, but there is a speed improvement of about 20%. I'll investigate further in the future...

    Btw: Are there any sources to look for concerning sse? I had no success when looking for a paper.... Matt, if i can bother you again? Or anybody else?

    Blackfox: what cpu does your computer have? L1 and L2 cache?

    Greets
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  10. #10
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts
    Quote Originally Posted by toffer
    Blackfox: what cpu does your computer have? L1 and L2 cache?
    Black_Fox uses this processor:

    Athlon 64 X2 3800+ (2 GHz core)

    L1-Cache: 64 + 64 KiB (Data + Instructions), per core

    L2-Cache: 512 KiB fullspeed, per core

    MMX, Extended 3DNow!, SSE, SSE2, SSE3, AMD64, CoolnQuiet, NX Bit

    http://techreport.com/articles.x/8616

  11. #11
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 150 Times in 18 Posts
    Quote Originally Posted by Stephan Busch
    I hope, Christian, that, when your thesis time is over, youll remember us and your marvellous CCM
    I think data compression is quite an interesting topic. Thats the reason why I started ccm in the first place. So, further development of ccm or starting out a new compression related project is probable. Additionally, the scene around here is good company. Two good arguments for coming back.

  12. #12
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    Quote Originally Posted by toffer
    Btw: Are there any sources to look for concerning sse? I had no success when looking for a paper.... Matt, if i can bother you again? Or anybody else?
    Serge Osnach introduced me to SSE in PAQ2. I think it means Secondary Symbol Encoding, but Im not sure. Anyway the idea is to input a next bit probability (after the mixer) and some context and output a new probability. After the prediction the table entry is adjusted to reduce the prediction error. In PAQ7/8 and LPAQ1 I renamed SSE to APM (adaptive probability map).

    In PAQ2 the input probability p was quantized to 64 levels on a nonlinear scale that is more dense around the ends. Later I improved this by quantizing to 32 levels and using interpolation. In LPAQ1 I quantize stretch(p) to 24 levels, where stretch(p) = log(p/(1-p)) (using a lookup table) in the range -8 to 8. The table is initialized so that APM(p, context) = p for all inputs.

    In PAQ7/8 I update the 2 table entries on either side of the interpolated input p by a fixed amount, like 1/256 of the error. In LPAQ1 I update only the nearest entry. Also in LPAQ1 I improved the update by storing a count n along with each output value and updating by error/(n+1.5) up to a maximum n < 1024. (I use a table to avoid slow division). This speeds up adaptation and is a stationary model, since if you get r ones out of n bits, the output is (r+.75)/(n+1.5). This might improve compression in PAQ8O but I havent gotten around to trying it.

    In LPAQ1 the mixer output is adjusted twice using order 0 and a hashed order 1 context by two APMs in series. Each APM output is also averaged with the input with weight 1/4, which seems to improve compression. In PAQ8O there are several APM stages with increasingly long contexts.

    The LPAQ1 APM table packs a 22 bit probability and 10 bit count into one 32-bit table entry. APM is derived from StateMap, which doesnt use interpolation and initializes all probabilities to 1/2. StateMap is used to map bit histories (8 bit states) to predictions.

  13. #13
    Member Surfer's Avatar
    Join Date
    Mar 2009
    Location
    oren
    Posts
    203
    Thanks
    18
    Thanked 7 Times in 1 Post
    Quote Originally Posted by Christian
    Sorry that Ive been very absent over the last months. Ive had some important exams and now I just started working on my final thesis. So, no time working on compression related things anymore.
    May be it will be reason to release sources of ccm ?
    I think that it will be interesting for Matt and Bulat )

  14. #14
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Good morning! (at least in my time zone )

    Thanks again for your answers! I'm confident to complete the model selecting mechanism today.

    Surprisingly the speeds reported by blackfox seem "shocking" to me. Compared to my computer, his machine is high end, i got an opteron 64 running at 1.8ghz. I got around 530kb/s compared to his x2, just achieving 170kb/s more. Could this be the "cache" bottleneck?

    Btw: Christian, good luck for your thesis!
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  15. #15
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Quote Originally Posted by Matt Mahoney
    Serge Osnach introduced me to SSE in PAQ2. I think it means Secondary Symbol Encoding, but Im not sure.
    SSE stands for Secondary Symbol Estimation. It was introduced by Dmitry Shkarin, and described in Russian data compression book called "Metody Szhatiya Dannyh". All my work was inspired by this book, many ideas taken from this book, in other words its a bible of data compression.

  16. #16
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    I'm only able to speak and read english (ok, and german). I've read David Salomon's "Data compression - The complete reference", which lacks things like context mixing and SSE. I was very suprised that this seems to be unkown to the english language area; what a pitty
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  17. #17
    Member
    Join Date
    May 2008
    Location
    France
    Posts
    78
    Thanks
    436
    Thanked 22 Times in 17 Posts
    For SSE, you should read Shkartin's paper entitled "PPM: one step to practicality"
    Link : http://www.compression.ru/download/ppm.html

    One good start is Skibiński's PhD (very concised but with references) : http://www.ii.uni.wroc.pl/~inikep/papers/PhD_thesis.pdf

  18. #18
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,497
    Thanks
    733
    Thanked 659 Times in 354 Posts
    Quote Originally Posted by Surfer
    I think that it will be interesting for Matt and Bulat
    you have guessed right!

  19. #19
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Thanks again. I had no success today, maybe tomorrow
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  20. #20
    Member
    Join Date
    Feb 2009
    Location
    USA
    Posts
    58
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Test System: AMD Athlon 64 3000+ (Venice)

    cmm.exe c enwik8 enwik8.cmm - 24,900,356 Bytes - 2m 17sec
    ccm.exe c enwik8 enwik8.ccm - 22,318,466 Bytes - 1m 37sec

    cmm.exe d enwik8.cmm enwik8 - 2m 23sec
    ccm.exe d enwik8.ccm enwik8 - 1m 40sec

  21. #21
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Good afternoon!

    It took me some time to figure out the right things to improve compression, but (de)compression speed dropped I'm using an lzp-like algorithm:

    * literals are coded using the context mixer (simply the previous version)
    * match lengths are coded using order-2-1 context mixing
    * there are no "flags", since my lzp variant trys to confirm a long context (e.g.8 bytes), false predictions (confirmed context, but match too short) are encoded as length 0 matches
    * lengths are unbounded, if length is between 6 and 20, they are directly outputtet (order-2-1), longer matches are encoded using elias gamma.
    * a 16mb non sliding window is used for simplicity (maybe i'll change it to a few mb gzip like window)

    Speed will be improved in the next release, since i use iostream insted of good old FILE, which has proven to be ill-suited for data compression (compare ifstream.get to fgetc, fgetc_unlocked .... SLOOOOW).
    String comparision is done in a brute force manner, i'll change this to gutman style string matching.

    http://freenet-homepage.de/toffer_86/cmm_17092007. 7z
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  22. #22
    Member
    Join Date
    Dec 2006
    Posts
    611
    Thanks
    0
    Thanked 1 Time in 1 Post
    Thanks Chris! Improves quite well over previous version
    Most visible improvement is in PSD file (2,5MB smaller compared to previous version)... PNG is still inflated by about 6%...
    __program______size_______in___out _ speed (kB/s)
    CCM 1.23 (-6)__11 974 852___712 / 731
    CMM 070906___16 340 731___599 / 591
    CMM 070917___13 421 915___733 / 717

  23. #23
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Already compressed data ("random") will almost always be expanded, since i use non-stationary bit models. When i move on to improve the bit models, this might be corrected (using sse).
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  24. #24
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts
    Thanks Chris!

  25. #25
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Hi!

    Here's an sligthly improved version. As i said i improved string matching and replaced iostream with c-ish io. In addition i tuned some internal parameters and the hashing functions. The LZP length model has been replaced by a faster order-1 model (compression loss is less than 0.1%). The result is improved speed (around 15% on my computer) and compression ratio.

    I would _really_ like to know how to do model switching like Christian did.

    @Mike: i had a short look at the papers, unfortunately the sse paper is in russian btw, the other english ones are very interesting! Thanks anyway

    Does anybody have further ideas how to improve the lzp layer or the context mixer (expect sse and adaptive weighting, i'll be working on it)?

    I'm looking forward to suggestions! Greets

    http://freenet-homepage.de/toffer_86/cmm_18092007.7z

    Btw: What about adding cmm to some benchmarks?! I haven't seen it at Matt's and BlackFox's site
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  26. #26
    Member
    Join Date
    May 2008
    Location
    France
    Posts
    78
    Thanks
    436
    Thanked 22 Times in 17 Posts
    @toffer
    SSE paper is in english (about SSE although it's not explicitly written) :
    http://www.compression.ru/download/articles/ppm/sh karin_2002dcc_ppmii_pdf.rar

  27. #27
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Thanks Mike! My fault
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  28. #28
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts
    Quote Originally Posted by toffer
    Heres an sligthly improved version. As i said i improved string matching and replaced iostream with c-ish io. In addition i tuned some internal parameters and the hashing functions. The LZP length model has been replaced by a faster order-1 model (compression loss is less than 0.1%). The result is improved speed (around 15% on my computer) and compression ratio.
    Thanks Chris!


    Quote Originally Posted by toffer
    Btw: What about adding cmm to some benchmarks?! I havent seen it at Matts and BlackFoxs site
    I think people are waiting until the project is a little more mature. Im sure it wont be very long before it features on everyones benchmarks.

  29. #29
    Member
    Join Date
    Dec 2006
    Posts
    611
    Thanks
    0
    Thanked 1 Time in 1 Post
    Quote Originally Posted by toffer
    Btw: What about adding cmm to some benchmarks?! I havent seen it at Matts and BlackFoxs site
    Well, last update on my benchmark was on June 17th, so you really arent the only one whose work wasnt featured for quite some time

    __program______size_______in___out _ speed (kB/s)
    CCM 1.23 (-6)__11 974 852___712 / 731
    CMM 070906___16 340 731___599 / 591
    CMM 070917___13 421 915___733 / 717
    CMM 070918___13 359 415___761 / 738

  30. #30
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts
    Quick test...

    Test machine: AMD Sempron 2400+, Windows XP SP2

    A10.jpg > 889,895
    AcroRd32.exe > 1,499,693
    english.dic > 634,862
    FlashMX.pdf > 3,932,626
    FP.LOG > 805,187
    MSO97.DLL > 1,846,843
    ohs.doc > 850,321
    rafale.bmp > 792,053
    vcfiu.hlp > 647,942
    world95.txt > 570,729

    Total = 12,470,151 bytes


    ENWIK8 > 23,744,529 bytes

    Compression speed for ENWIK8 was ~300 kB/s.

Page 1 of 6 123 ... LastLast

Similar Threads

  1. another (too) fast compressor
    By Cyan in forum Data Compression
    Replies: 139
    Last Post: 6th February 2016, 21:41
  2. Simple bytewise context mixing demo
    By Shelwien in forum Data Compression
    Replies: 11
    Last Post: 27th January 2010, 04:12
  3. Context mixing
    By Cyan in forum Data Compression
    Replies: 7
    Last Post: 4th December 2009, 19:12
  4. PACKET v.0.01 new fast compressor !
    By Nania Francesco in forum Data Compression
    Replies: 45
    Last Post: 19th June 2008, 01:44
  5. Fast PPMII+VC Compressor
    By in forum Forum Archive
    Replies: 4
    Last Post: 2nd August 2006, 19:17

Posting Permissions

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