Page 6 of 6 FirstFirst ... 456
Results 151 to 172 of 172

Thread: CMM fast context mixing compressor

  1. #151
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by encode
    To avoid decoder problems, each time you find E8/E9 you should advance to 5 bytes forward, even if you not performed actual preprocessing of currend address.
    Do you mean to step over *very* e8/e9? I tried it and it baldy hurts compression.

    Quote Originally Posted by Bulat Ziganshin
    toffer, usual scheme is to translate jumps only in limited range, say from -16m to +16m and map translated jumps to the *same* range. this allows to distinguish between translated and untranslated jumps
    I already restrict the transform the the maximum possible range - a 24 bit signed int. So you can detect e8/e9 xx xx xx 00/ff (both on encoder/deocder side). But this doesnt solve the mentionend problem.

    Or do you mean something different?
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  2. #152
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,593
    Thanks
    801
    Thanked 698 Times in 378 Posts
    it seems that i'm pretty ignorant in this area. i suggest you to look into BranchX86.c from lzma sources - it seems that it solves this problem

  3. #153
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 163 Times in 18 Posts
    Quote Originally Posted by toffer
    Do you mean to step over *very* e8/e9? I tried it and it baldy hurts compression.
    Quote Originally Posted by toffer
    I already restrict the transform the the maximum possible range - a 24 bit signed int. So you can detect e8/e9 xx xx xx 00/ff (both on encoder/deocder side). But this doesnt solve the mentionend problem.
    Then, why not combine the two approaches? Coming across "e8/e9 xx xx xx 00/ff" is very unlikely, if it isnt a jmp/call. So, skipping almost doesnt hurt compression. Additionally, skipping 4 bytes is sufficient, because e8/e9 != 00/ff.

  4. #154
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    I tried the combined approach (this is what i catually meant) and alltogether it hurts compression by around 2-10k (exes, which are around 1mb). I still like my "streaming" approach, since it doesn't require to break data into blocks and the encoding and decoding function are the same expect an offset increment/decrement, which can be solved using a increment variable (+1/-1).

    BTW: does the relative jump address include or exclude the e8/e9 (increment the offset / or leave it) ?
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  5. #155
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,593
    Thanks
    801
    Thanked 698 Times in 378 Posts
    jmp -2 is endless loop, so offset is relative to the address of next command

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

  7. #157
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    I think i found a solution:

    If the encoder encounters a pattern like:

    e8/9 xx xx e8/9
    e8/9 xx e8/9
    e8/9 e8/e9

    It steps to the following e8/9. This method recognizes patterns like the one, which i gave as an example. I'll see, how well it works. So we reject the transform (for the leftmost e8/9), if the difference between the leftmost and the next if smaller than three.

    Bulat, if you would be so kind - what is Igor doing in 7zip? Once i looked into the 7zip sources - they are written with *too much* eyecandy an are not very well commented. I usually think what the hell is going on?!
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  8. #158
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,593
    Thanks
    801
    Thanked 698 Times in 378 Posts
    i don't know altough may be he use the same idea as you. this particulat module is small enough so you can try to understand it

  9. #159
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    On the first look the 7zip sources look similar - but i haven't had enough endurance to understand everything. Igor mask out some stuff (bitmasks, but what exactly?!), but it looks like he counts the distance between to consecutive e8/e9. I implemented the stuff mentioned earlier and it seems to work. Compression ratio is hurt, though (not as bad as my previous tests with a "dumb" method showed).
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  10. #160
    Tester
    Stephan Busch's Avatar
    Join Date
    May 2008
    Location
    Bremen, Germany
    Posts
    876
    Thanks
    474
    Thanked 175 Times in 85 Posts
    Dear Toffer,

    I have added you to the hall of fame because you created CMM.
    Please let me know if you allow it and whether you want to have a photo and/or birthday added.

    Yours,

    Stephan

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

    Thanks for adding me. My birthday is March, 3rd 1986. I'll send a photo this or next week, but i'm busy atm.

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

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

    After playing around with several different x86 transforms i integrated the one with best overall performance into cmm4. Here's a smaller new release containing a filter framework (most of the work) and an implementation for a executable filter.

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

    The improvement is quiet obvious on SFC I might even reach the 10mb "sonic barrier" after applying some tweaks and adding more filters.

    I wonder why Matt didn't include a cmm4 test into his LTCB. The performance on enwik9 is significantly improved since 0.1c.

    To Nania: If you add this one to moc, please correct the version number and memory requirements.

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

  13. #163
    Moderator

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

    Mirror: Download

  14. #164
    Moderator

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

    Test file: ENWIK8

    Test machine: AMD Sempron 2400+, Windows XP SP2.

    Setting: 76


    Compressed size: 19.6 MB (20,569,034 bytes)

    Ratio: 20569032/100000000 bytes (1.65 bpc)
    Speed: 173 kB/s (5619.4 ns/byte)
    Time: 561.94 s

  15. #165
    Moderator

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

    Setting: 46

    A10.jpg > 829,832
    AcroRd32.exe > 1,188,935
    english.dic > 453,648
    FlashMX.pdf > 3,651,244
    FP.LOG > 446,317
    MSO97.DLL > 1,597,197
    ohs.doc > 750,711
    rafale.bmp > 740,481
    vcfiu.hlp > 514,204
    world95.txt > 454,916

    Total = 10,627,485 bytes

    Quote Originally Posted by osmanturan
    Off-Topic: I have passed the mastering/PhD english exam with 72,5 on 100 points 50-55 points are enough for most of universities in my country.
    Congratulations!

  16. #166
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @toffer
    Really good work!

    I want to share what I have found interesting with my neural mixer. Maybe, you have already done like these tests. But, I think you must know

    Currently, I'm not using any SSE or APM stage after mixing stage. Just mixing order 2-1-0 with suffix tree like implementation (not hashed) at order-1 ROLZ literal coding. ROLZ part uses flexible parsing which is same as quad. Whole compression algorithm optimized for 4-byte aligned binary files. I noticed, context selection for neurons is one of the best important thing in my momentum-term based neural mixer. After doing some tests, I have really interesting results:
    - Text compression is really really bad! On SFC test FP.log, I have %200 worse compression when I compare my old literal coder (simple order-1).
    - Binary compression (especially on ISO files) I have really good results which outperforms 7-zip Ultra, rzm 0.07e and RAR Best. For example my compressor compressed ~258 MB Intel C 10 ISO file ~+20 MB better when we compare the other compressors Also, when we compare rzm and 7zip with my coder, rzm and 7zip uses optimal parsing!
    - Calgary corpus compression is not good enough. I think, my coder suffers from text files in TAR version.

    I really interested in SSE/APM stage. Maybe the compression will be better. But, I can't understand what's going on in SSE

    When I have done some other tweaks, I would like to post exact results with a release. I hope, I can complete this task in this week.

    Off-Topic: I have passed the mastering/PhD english exam with 72,5 on 100 points 50-55 points are enough for most of universities in my country.
    BIT Archiver homepage: www.osmanturan.com

  17. #167
    Member Vacon's Avatar
    Join Date
    May 2008
    Location
    Germany
    Posts
    523
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Hello everyone,

    Quote Originally Posted by osmanturan
    Off-Topic: I have passed the mastering/PhD english exam with 72,5 on 100 points
    Congrats!

    Best regards!

  18. #168
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Thanks for testing! When i've finished more filters i'll try to do auto detection, like christian does, since it's far more elegant and maybe more efficient (data segmentation, works for tars too).


    @osmanturan

    Congratulations for your english exam.

    Before beginning a discussion, what do you want to know exactly (despite SSE)?

    BTW: the main reason for me not to include a momentum term is the amount of memory which is heavily realted to a speed decrease due to cache misses (my weight vector completly fits ino a single cache line). I'm however sure, that the compression improvement is notable. If some well placecd prefetch instructions can compensate this, i'll give it a try. But at the moment i'm working on parameter optimization and creating a state machine from a large dataset's empirical distribution.
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  19. #169
    Tester
    Nania Francesco's Avatar
    Join Date
    May 2008
    Location
    Italy
    Posts
    1,583
    Thanks
    234
    Thanked 160 Times in 90 Posts
    Tanks Chris! Hi !

  20. #170
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @vacon: Thanks!
    @toffer: Thanks!
    My question is about SSE implementation. How can I process the neural mixer output with SSE or APM? What's the benefit of this process. I already know this improve compression, but how? My guess is something like that:

    Single neural mixer is a fast learning phase which adapts small local changes. But, adaptation must be a long term on most data files. Because, small local changes do not reflect whole data characteristics. So, in this area SSE enables long-term learning. So, I think a second neural mixer with low learning rate can do this already. If these are true, neural mixer based "long term learning" can beat any previous implementations due to neural network nature. Last thing, another guess is long-term based learning only benefits large files. On small files compression can hurt. Am I totally wrong?

    Also, I would like to share some 2D graphs which based on two variables: learning rate and momentum-term coefficient. I think, these graphs will help us a lot. I hope, I will be able to find some spare time for generating these plots.
    BIT Archiver homepage: www.osmanturan.com

  21. #171
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @osmanturan

    I'll answer this tomorrow or maybe this afternoon. Sorry, i'm busy atm.
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  22. #172
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Actually a NN doesn't learn that quick, since you use gradient descent (which converges slowly). This can be compensated a bit by using some techniques like step size estimation, smoothing, etc... But this can't compete with second order algorithms. By combining several model's predictions you compensate the inaccuracy of some models and the slow learning speed of other models. Suprisingly this mixed prediction is better than the best model's prediction, but life isn't perfect.

    The network itself learns to represent a nonlinear function of it's input data, the complexity of this function is limited by the network structure (so a NN could be approximated by a polynomal). Since the network we use is very simple, we can't describe an ideal input-output mapping.

    Alltogether:
    the models aren't perfect
    the prediction mix isn't perfect

    Now this is the point what SSE does. It maps a prediction and some context to another prediction, so it tries to lern the "ideal" input-output mapping. Now just take a SSE step which only maps a probability to another: SSE(p0) = p1. That is a simple one dimensional function. How do we represent this? You sample this function at the points p0(k)=k/N (which map to p1(k)), where N is the total number of vertices, so you can approximate this mapping. This can be further improved by using interpolation. For speed reasons a simple linear interpolation, which involves the two nearest vertices p0(k), p0(k+1) to the input probability p0. And, of course, you need to update the SSE function; this is simple, since a vertex can be represented by bit model.
    A SSE step p1=SSE(p0) is given by:

    1. find the neares vertices k, k+1 : k = p0/(1/N)
    2. find the distance of p0 to the vertex k : d = p0%(1/N) (reminder)
    3. calculate p1 by interpolation, e.g. linear interpolation: p1 = p0(k)*((1/N-d)/(1/N)) + p0(k+1)*(d/(1/N))
    4. Update the function, e.g. update the involved vertices (like the bit models you use)

    There are several things which you can do to improve this mapping: use more than just one SSE function (select the "active" function by a context ctx). This makes SSE two dimensional: p1=SSE_ctx(p0) => p1 = SSE(p0,ctx). You can also preprocess the input probability, like applying a transform to increase the resolution where it's important (near accurate predictions). You don't need to do this, but you can (have a look at the discussion about SSE with Shelwien).

    I hope this helps.

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

Page 6 of 6 FirstFirst ... 456

Similar Threads

  1. Simple bytewise context mixing demo
    By Shelwien in forum Data Compression
    Replies: 13
    Last Post: 3rd April 2020, 17:04
  2. another (too) fast compressor
    By Cyan in forum Data Compression
    Replies: 139
    Last Post: 6th February 2016, 21:41
  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, 02:44
  5. Fast PPMII+VC Compressor
    By in forum Forum Archive
    Replies: 4
    Last Post: 2nd August 2006, 20: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
  •