CMM fast context mixing compressor

[toffer]

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

[Black_Fox1]

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

[LovePimple]

Thanks Chris! Welcome to the forum!

[toffer]

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?

[Matt Mahoney]

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.

[SvenBent]

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

[Christian]

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.

[Stephan Busch]

I hope, Christian, that, when your thesis time is over, you'll remember us and your marvellous CCM

[toffer]

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

[LovePimple]

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

[Christian]

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.

[Matt Mahoney]

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.

[Surfer]

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 )

[toffer]

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!

[encode]

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.

[toffer]

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

[Mike]

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

[Bulat Ziganshin]

I think that it will be interesting for Matt and Bulat

you have guessed right!

[toffer]

Thanks again. I had no success today, maybe tomorrow

[Hahobas]

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

[toffer]

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

[Black_Fox1]

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

[toffer]

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

[LovePimple]

Thanks Chris!

[toffer]

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

[Mike]

@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

[toffer]

Thanks Mike! My fault

[LovePimple]

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!

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.

[Black_Fox1]

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

[LovePimple]

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.