CMM fast context mixing compressor

[toffer]

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.

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?

[Bulat Ziganshin]

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

[Christian]

Do you mean to step over *very* e8/e9? I tried it and it baldy hurts compression.

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.

[toffer]

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

[Bulat Ziganshin]

jmp -2 is endless loop, so offset is relative to the address of next command

[toffer]

Thanks Bulat!

[toffer]

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?!

[Bulat Ziganshin]

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

[toffer]

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

[Stephan Busch]

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

[toffer]

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

[toffer]

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!

[LovePimple]

Thanks Chris!

Mirror: Download

[LovePimple]

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

[LovePimple]

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

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!

[osmanturan]

@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.

[Vacon]

Hello everyone,

Off-Topic: I have passed the mastering/PhD english exam with 72,5 on 100 points

Congrats!

Best regards!

[toffer]

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.

[Nania Francesco]

Tanks Chris! Hi !

[osmanturan]

@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.

[toffer]

@osmanturan

I'll answer this tomorrow or maybe this afternoon. Sorry, i'm busy atm.

[toffer]

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