RZM - a dull ROLZ compression engine

[osmanturan]

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;
</pre></div>

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;
...</pre></div>

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

[osmanturan]

gr??e von deutschland nach deutschland

gr??en von T?rkei nach Deutschland

[toffer]

This seems to be some heuristic, on the first look i don&#039;t see a motivation behind this. You handle weights like nonstationary binary counters (see shelwien&#039;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&#039;t change them). The essential property of the sigmoidal output function is that f&#039;(x) = f(x) ( 1-f(x)), which eliminates division, but requires more table lookups.
Here&#039;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&#039;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&#039;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&#039;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&#039;ve just got 64*6 context, far less then you with just order 2.

If you&#039;ve coupled SSE, than you can safely leave out order 0.

[Christian]

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.

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

[toffer]

I actually didn&#039;t mean RZM. I meant ccm.

[Christian]

I use several approaches (depending on the node of the mixing tree, which ccm uses). But this one you haven&#039;t mentioned, I think. It&#039;s using counters/probabilty maps. For a small number of models it&#039;s really nice. Initialization of the counters is a little problem, though. But knowing which models you&#039;re mixing, it&#039;s ok.
<div class="jscript"><pre>p1=counter[scale(model0.p1)][scale(model1.p1)].p1</pre></div>


ps.: gru? aus aachen nach ?berall

[osmanturan]

@toffer:
Thanks a lot for your replies. I&#039;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&#039;ve already known this wasn&#039;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&#039;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.

[toffer]

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.

[toffer]

I just ripped off my SSE implementation and tried this (no optimization)... It&#039;s really amazing and much faster than i thought... Unfortunately this wasn&#039;t in front of my todo list. I got stuck trying other optimization approaches. Thanks a lot, Christian & Shelwien

[Christian]

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.

[vcore]

@ 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?
<div class="jscript"><pre>
p1=counter[scale(model0.p1)][scale(model1.p1)].p1
</pre></div>

I don&#039;t really understand this formula.
How to update the two dimensional counter ?

Thanks in advance.

[Christian]

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.

[vcore]

I just figure out what the mapping means!!
Instead of mixing different model&#039;s probability, it maps models&#039; probability into another array and count the probability in the new array. really amazing idea.

[toffer]

@vcore
Actually this is what SSE does - nothing really new.

I&#039;m already using nonlinear scale. Some inverse of a sigmoidal function like f(x) = x / sqrt(1-x^2). One could use Matt&#039;s stretch, too; since it&#039;s just the inverse of another sigmoidal function (the logistic one). My motivation is to increse the qunatisation&#039;s resolution, where predictions are significant and to drop, where the predictions are around p=.5. I&#039;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&#039;t rely on any mix, it simply learns the mapping . So it&#039;s not forced to be a linear mix!

[osmanturan]

@toffer:
Yes, this new combination is really good and simple. Before trying it, I&#039;ve played with your descent gradient approach. But, your formula is hard to implement: integer round off, choosing proper alpha value etc. But, christian&#039;s approach simpler and better Do we really need order-0 in this kind of mixing? I&#039;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&#039;m trying to write a non-linear scaling function

[toffer]

I would suggest to use interpolation. This gives another boost. I&#039;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&#039;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&#039;s RZM.

I&#039;m unsure if this mixing approach can be used for combined model&#039;s predictions, since the approximated density function might vary up to a certain degree and you can&#039;t easily map this varying source to a better output. I have no experience here, just thoughts...

[Piotr Tarsa]

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

[Christian]

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.

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

[LovePimple]

Awesome! Thanks Chris!

Mirror: Download

[LovePimple]

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

[Nania Francesco]

Enwik8->24.773.064 bytes

[Nania Francesco]

For me RZM engine is it is superior to LZMA engine !

[LovePimple]

Enwik8->24.773.064 bytes

My result for ENWIK8 is 24,773,072 bytes.

For me RZM engine is it is superior to LZMA engine !

Its Awesome!

[Christian]

Thanks guys!

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.

[LovePimple]

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.

[LovePimple]

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)

[Christian]

Hi again!

Here&#039;s another improved version - this time it&#039;s about compression speed. I redesigned the search logic and beefed it up with more memory (eats 64M more memory). There&#039;s still room for further improvements, but it&#039;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&#039;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&#039;t improved much - maybe 3-5%.

<div class="jscript"><pre>
0.05 0.06
valley_cmb 7620k (16.1s) 7572k ( 8.8s) ~1.8x faster
SFC (tar&#039;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
</pre></div>


Download RZM 0.06

[LovePimple]

Thanks Chris!

Mirror: Download

[Piotr Tarsa]

Christian
i wonder if you will make ppm coder someday

[Nania Francesco]

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%)