Page 2 of 6 FirstFirst 1234 ... LastLast
Results 31 to 60 of 179

Thread: RZM - a dull ROLZ compression engine

  1. #31
    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 toffer
    I wonder how you do that
    The first method which Iused to is static mixing. Now, Im trying to move true neural network (hidden layer, error momentum etc). Current draft version is like that:
    <div class=""jscript""><pre>BitModel order0[256];
    BitModel order1[256][256];
    BitModel order2[256][256][256];
    NeuralMixer mixers[256][256][256];
    ...
    // encoding
    p0 = order0[ord0].GetProb();
    p1 = order1[ord1][ord0].GetProb();
    p2 = order2[ord2][ord1][ord0].GetProb();
    p = mixer[ord2][ord1][ord0].Mix(p0, p1, p2);
    Encode(bit, p);

    order0[ord0].Update(bit);
    order1[ord1][ord0].Update(bit);
    order2[ord2][ord1][ord0].Update(bit);

    mixer[ord2][ord1][ord0].Update();
    ...
    // mixing
    p = ((p0 * w0) + (p1 * w1) + (p2 * w2)) / weightSum;
    ...
    // weight updating
    int target = max(p0, max(p1, p2));

    if (p0 == target)
    w0 += (((UInt16)(~w0)) >> 5);
    else
    w0 -= ((w0) >> 5);

    if (p1 == target)
    w1 += (((UInt16)(~w1)) >> 5);
    else
    w1 -= ((w1) >> 5);

    if (p2 == target)
    w2 += (((UInt16)(~w2)) >> 5);
    else
    w2 -= ((w2) >> 5);

    weightSum = w0 + w1 + w2;
    [/code]

    As you see, this isnt a precise solution. But, its better than use simple order-n model. Old weight updating solution was:
    <div class=""jscript""><pre>if (p0==target)
    w0++;
    else
    w1>>1;
    ...[/code]

    As you see, this one works like semi-stationary update. But, IIRC first code has better compression. I forget why I choose the first code. I have to get some B12 vitamin tablets
    BIT Archiver homepage: www.osmanturan.com

  2. #32
    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 toffer
    gr??e von deutschland nach deutschland
    gr??en von T?rkei nach Deutschland
    BIT Archiver homepage: www.osmanturan.com

  3. #33
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    This seems to be some heuristic, on the first look i don't see a motivation behind this. You handle weights like nonstationary binary counters (see shelwien's post about counters)
    Why not derive an update from coding cost minimization? Or if you want to use a NN, why not just implement it and go? See PAQ as a reference for a NN with a proper chosen activation and output function for the neurons (i think i wouldn't change them). The essential property of the sigmoidal output function is that f'(x) = f(x) ( 1-f(x)), which eliminates division, but requires more table lookups.
    Here's my update (gradient descent):

    p = sum w_i * p_i / ws
    ws = sum w_i

    w_i(k+1) = w_i(k) + alpha * [ p_i - p ] / [ ws *( (not y)-p) ]

    This formula implies that y is the bit to be coded and the p's are probabilities for the next bit to be one. You have to be careful when choosing integer quantization levels and to do proper rounding. Alpha is a constant, you have to choose empirically. You need to find the right range for alpha. This formula gives similar robustness like PAQ6's and for me a drastic improvement in compression (SFC from around 12.3 mb to 11.4, going further using other optimizations)

    BTW: i think you've got too much weight contexts. A minimal weight context should be the coding order. Even in my order 1-6 context mixing compressor, i've just got 64*6 context, far less then you with just order 2.

    If you've coupled SSE, than you can safely leave out order 0.
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  4. #34
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 163 Times in 18 Posts
    Quote Originally Posted by toffer
    BTW: Christian, which is your weighting approach? I have tried several different and found gradient descent / NN (gradient descent with a nonlinear transform) to be very robust (and efficient). The NN method requires no divisions, but needs more table lookups.
    Thats easy. RZM doesnt use any weighting.


    Quote Originally Posted by osmanturan
    Can you share us a psuedo code for making it clear? I think, ilia wonders what is happenning in your parsing, too
    As I dont want to reinvent the wheel, Ive just searched and found a nice post by Bulat. It describes the ideas of OP very well. For ROLZ it isnt any different - only the matches come from a different source.
    Click me

  5. #35
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    I actually didn't mean RZM. I meant ccm.
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  6. #36
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 163 Times in 18 Posts
    I use several approaches (depending on the node of the mixing tree, which ccm uses). But this one you haven't mentioned, I think. It's using counters/probabilty maps. For a small number of models it's really nice. Initialization of the counters is a little problem, though. But knowing which models you're mixing, it's ok.
    Code:
    p1=counter[scale(model0.p1)][scale(model1.p1)].p1

    ps.: gru? aus aachen nach ?berall

  7. #37
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @toffer:
    Thanks a lot for your replies. I'm totally new at compression subject - especially context mixing. When I had decided to implement a CM back-end for my literal coder, I implemented a static mixing. At next step I noticed that weight updating is a kind of learning. So, I digged some neural network papers. At the same time I decided to implement such that idea. I've already known this wasn't a real solution. I just want to make it for motivation. As you see in the code, I try to choose highest probability for any model. Nothing special. But, it gives better compression than simple order-1.

    I'll try your formula. It seems clear enough.

    My real plan about CM back-end is order 0-1-2 mixing with SSE. I hope I can implement it.
    BIT Archiver homepage: www.osmanturan.com

  8. #38
    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 Christian
    p1=counter[scale(model0.p1)][scale(model1.p1)].p1
    I had a discussion with shelwien about something like this. Instead of weighend combining two models output distributions you simply use an adaptive map to learn the output distriution. This is quiet similar to SSE, though (and can be implemented like that). Isnt something like this cache inefficient, since memory accesses are almost random (at least for the cpu)?
    Do you use any optimization technique from these above?

    Das mit den Gr??en war eigentlich an dich gerichtet. So passts aber auch! Ich komm ?brigens aus Erfurt.

    @osmanturan

    You really dont need order 0, when using SSE. Exspecially not, when you use a PAQ-like order 0 SSE map (since the context itself is in fact an order 0 context). I dont know how your knowledge is, but i think you dont need to read papers about this. An understanding of the concepts and math (its not hard) behind NNs is enough. Im sure you wont be able to choose a complex mixing scheme with hidden layers, etc, since you mix every bit, which is quiet expensive. If you dont use a 256-ary binary decomposition of your normal alphabet, something more complex might be worth the effort.
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  9. #39
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    I just ripped off my SSE implementation and tried this (no optimization)... It's really amazing and much faster than i thought... Unfortunately this wasn't in front of my todo list. I got stuck trying other optimization approaches. Thanks a lot, Christian & Shelwien
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  10. #40
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 163 Times in 18 Posts
    Quote Originally Posted by toffer
    I just ripped off my SSE implementation and tried this (no optimization)... Its really amazing and much faster than i thought... Unfortunately this wasnt in front of my todo list. I got stuck trying other optimization approaches. Thanks a lot, Christian & Shelwien
    Yep, its beautiful. Additionally, it learns in a very intuitive way.

  11. #41
    Member
    Join Date
    Jan 2008
    Posts
    33
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @ toffer

    Hi , sorry but I am newbie at context mixing.
    You means you speed it up by replace the sondary symbol estimation with the following method?
    Code:
     
    p1=counter[scale(model0.p1)][scale(model1.p1)].p1
    I don't really understand this formula.
    How to update the two dimensional counter ?

    Thanks in advance.

  12. #42
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 163 Times in 18 Posts
    Quote Originally Posted by toffer
    This is quiet similar to SSE, though (and can be implemented like that). Isnt something like this cache inefficient, since memory accesses are almost random (at least for the cpu)?
    Do you use any optimization technique from these above?
    If you look closer, youll notice the scale(...). With proper scaling the table will be very small and therefore fits easily in any cache. Scaling must not be linear, of course.

  13. #43
    Member
    Join Date
    Jan 2008
    Posts
    33
    Thanks
    0
    Thanked 0 Times in 0 Posts
    I just figure out what the mapping means!!
    Instead of mixing different model's probability, it maps models' probability into another array and count the probability in the new array. really amazing idea.

  14. #44
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @vcore
    Actually this is what SSE does - nothing really new.

    I'm already using nonlinear scale. Some inverse of a sigmoidal function like f(x) = x / sqrt(1-x^2). One could use Matt's stretch, too; since it's just the inverse of another sigmoidal function (the logistic one). My motivation is to increse the qunatisation's resolution, where predictions are significant and to drop, where the predictions are around p=.5. I'm using 24*24 levels (for pa,pb) to scan the combined probability density function p(pa, pb). Do you use interpolation? I do linear interpolation, like with sse.

    The great advantage of this method is, that a weighed combination _ALWAYS_ results in a linear mix of both probabilities distributions. A SSE like method doesn't rely on any mix, it simply learns the mapping . So it's not forced to be a linear mix!
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  15. #45
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @toffer:
    Yes, this new combination is really good and simple. Before trying it, I've played with your descent gradient approach. But, your formula is hard to implement: integer round off, choosing proper alpha value etc. But, christian's approach simpler and better Do we really need order-0 in this kind of mixing? I'm playing with it like that:

    // p=(0..4095]
    pr = counter0[order0.p >> 6][order1.p >> 6].p;
    pr = counter1[pr >> 6][order2.p >> 6].p;

    Currently, I'm trying to write a non-linear scaling function
    BIT Archiver homepage: www.osmanturan.com

  16. #46
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    I would suggest to use interpolation. This gives another boost. I'm working out a 2d function approximation, which uses linear interpolation between adjacent vertices. Even only 1d interpolation (as with my normal sse) gave a nice compression gain.

    Watch out: you do a secondary probability mapping based on your model's outputs (probabilites). If you plan to add another "secondary mapping" after your mixing stage based on a actual order-x context (this is what Matt calls APM) you can drop order 0. This heavily depends on the context you use for this mapping.

    I think one should create a new thread for this, it has nothing to do with Christian's RZM.

    I'm unsure if this mixing approach can be used for combined model's predictions, since the approximated density function might vary up to a certain degree and you can't easily map this varying source to a better output. I have no experience here, just thoughts...
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  17. #47
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,505
    Thanks
    26
    Thanked 136 Times in 104 Posts
    a little on- topic:
    rzm scores very well on sfc tests
    with some simple filters for rafale.bmp and a10.jpg (decomposing to huffman codes and bitstream, then leaving bitstream untouched and compressing huffman codes with rolz) it can blow out many good compressors

  18. #48
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 163 Times in 18 Posts
    Quote Originally Posted by toffer
    I think one should create a new thread for this, it has nothing to do with Christians RZM.
    Yep, thatd be nice. Nonetheless, have fun with this new weapon of bit destruction.


    Quote Originally Posted by donkey7
    rzm scores very well on sfc tests
    with some simple filters for rafale.bmp and a10.jpg (decomposing to huffman codes and bitstream, then leaving bitstream untouched and compressing huffman codes with rolz) it can blow out many good compressors
    I just saw the update of MC. Im very pleased with these results - it beats 7-zip on MFC! Once I add general data filters (e.g. delta) itll become really strong - too bad CCMs filtering is incompatible with RZM. But I leave JPG recompression to others - imo, its too much work with too little effect.

    And heres a new version. This one is a bit stronger again - as always, it depends on the data. Ive improved RZMs syntax. The decompression speed stays untouched because the syntax is still pretty simple. Compression time is a little bit longer, hmmm, maybe not. Damn, I just missed MCs update with this one. Aaaahhhh, Ive got so many ideas and so little time!


    RZM 0.05

  19. #49
    Moderator

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

    Mirror: Download

  20. #50
    Moderator

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

    A10.jpg > 837,661
    AcroRd32.exe > 1,247,740
    english.dic > 673,586
    FlashMX.pdf > 3,685,365
    FP.LOG > 513,292
    MSO97.DLL > 1,686,084
    ohs.doc > 786,198
    rafale.bmp > 940,017
    vcfiu.hlp > 588,110
    world95.txt > 536,988

    Total = 11,495,041 bytes

  21. #51
    Tester
    Nania Francesco's Avatar
    Join Date
    May 2008
    Location
    Italy
    Posts
    1,583
    Thanks
    234
    Thanked 160 Times in 90 Posts
    Enwik8->24.773.064 bytes

  22. #52
    Tester
    Nania Francesco's Avatar
    Join Date
    May 2008
    Location
    Italy
    Posts
    1,583
    Thanks
    234
    Thanked 160 Times in 90 Posts
    For me RZM engine is it is superior to LZMA engine !

  23. #53
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts
    Quote Originally Posted by Nania Francesco Antonio
    Enwik8->24.773.064 bytes
    My result for ENWIK8 is 24,773,072 bytes.

    Quote Originally Posted by Nania Francesco Antonio
    For me RZM engine is it is superior to LZMA engine !
    Its Awesome!

  24. #54
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 163 Times in 18 Posts
    Thanks guys!

    Quote Originally Posted by LovePimple
    My result for ENWIK8 is 24,773,072 bytes.
    The size RZM outputs is a bit smaller than the actual size (hehe... it cheats) because it is printed *before* the last framesize coding.

  25. #55
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts
    Quote Originally Posted by Christian
    The size RZM outputs is a bit smaller than the actual size (hehe... it cheats) because it is printed *before* the last framesize coding.
    I never trust the compressed size displayed by ANY compressor.

  26. #56
    Moderator

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

    Test machine: Intel PIII (Coppermine) @750 MHz, 512 MB RAM, Windows 2000 Pro SP4

    Test File: ENWIK9 (1,000,000,000 bytes)

    Timed with AcuTimer v1.2


    ENWIK9 > 214,284,339 bytes
    Elapsed Time: 02:30:19.562 (9019.562 Seconds)

  27. #57
    Programmer
    Join Date
    Feb 2007
    Location
    Germany
    Posts
    420
    Thanks
    28
    Thanked 163 Times in 18 Posts
    Hi again!

    Here's another improved version - this time it's about compression speed. I redesigned the search logic and beefed it up with more memory (eats 64M more memory). There's still room for further improvements, but it's a good start. I believe, that a compiler with better loop unrolling (aka Intel) will improve speed further, too.
    Of course, string searching can be easily multithreaded - but I'm too lazy for this. Additionally, it would bloat the source, which is already ~20k.

    So, here are some results. Note, that the compression is improved a tiny bit, too. Compression speed of highly compressible data isn't improved much - maybe 3-5%.

    Code:
     
    			0.05		0.06 
    valley_cmb		 7620k (16.1s)	 7572k ( 8.8s)	~1.8x faster 
    SFC (tar'ed)		11198k (39.0s)	11186k (30.8s)	~1.3x faster 
    waveset (UCLC)		37342k (82.2s)	37339k (35.3s)	~2.3x faster 
    seamonkey (zipped)	42291k (83.3s)	42295k (21.9s)	~3.8x faster

    Download RZM 0.06

  28. #58
    Moderator

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

    Mirror: Download

  29. #59
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,505
    Thanks
    26
    Thanked 136 Times in 104 Posts
    Christian
    i wonder if you will make ppm coder someday

  30. #60
    Tester
    Nania Francesco's Avatar
    Join Date
    May 2008
    Location
    Italy
    Posts
    1,583
    Thanks
    234
    Thanked 160 Times in 90 Posts
    INTEL CORE DUO 2 E6600 2GB RAM
    ------------------------------------------------
    SFC Test-> 11.485.144 bytes Comp. 42,984 s. - Dec. 3,875 s.
    ( Rings 1.1 Comp 4,345 - Dec. 7,128 )
    Enwik8-> 24.684.208 Comp. 144,537 s. - Dec. 7,095 (Rings. 1.1 Comp. 8,870 s. - Dec. 15,270 s.)
    My Opinion:
    -Compression: number one for the ROLZ compressor
    -Speed of Compression: Great for a ROLZ compressor - good overall.
    - Speed of Decompression: Very Good;
    - Relationship Size/Decompression: number one - Impressive.
    -To improve of few the speed of decompression I recommend you not to visualize the statistics during the operations (it also of 5-10%)

Page 2 of 6 FirstFirst 1234 ... 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. RZM doesn't like to share cpu
    By SvenBent in forum Data Compression
    Replies: 2
    Last Post: 19th July 2008, 23:35
  3. ROLZ explanation?
    By Trixter in forum Data Compression
    Replies: 5
    Last Post: 10th June 2008, 19:24
  4. RZM compressor
    By encode in forum Data Compression
    Replies: 2
    Last Post: 24th May 2008, 15:59
  5. A small article on ROLZ (Russian)
    By encode in forum Forum Archive
    Replies: 21
    Last Post: 29th April 2007, 16: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
  •