BCM v0.01 - New BWT+CM-based compressor

[encode]

Well, I decided to release the very first version of my BWT+CM compressor called BCM. No segmenter or filters included. It's still draft and I release it for users of my forum only, so it kind of non-public!

Enjoy!

BTW, during development I've found some CM compression-related improvements, so, it might be that I will continue work on my BALZ file compressor...

[LovePimple]

Thanks Ilia!

[encode]

Any comments, impressions? How it works for you? For example, how this compressor, in your opinion, compared to BALZ?

[nimdamsk]

Made some quick tests... BCM is 2-4 times faster than BBB and compression is sometimes worser, sometimes better. But, newer the less, on my relatively small files GRZip and UHBC mostly beat both BCM and BBB

[LovePimple]

Some timings for ENWIK8 on my AMD Sempron 2400+ machine...


Compressed size: 20.8 MB (21,824,948 bytes)


Compression Time: 451.24 Seconds

00 Days 00 Hours 07 Minutes 31.24 Seconds


Decompression Time: 159.13 Seconds

00 Days 00 Hours 02 Minutes 39.13 Seconds

[LovePimple]

MC SFC test:

A10.jpg > 830,651
AcroRd32.exe > 1,595,953
english.dic > 1,180,338
FlashMX.pdf > 3,761,095
FP.LOG > 557,444
MSO97.DLL > 1,927,126
ohs.doc > 844,340
rafale.bmp > 759,576
vcfiu.hlp > 659,158
world95.txt > 479,001

Total = 12,594,682 bytes

[Nania Francesco]

Have done a good job with BCM but seems anchors slow, needs to work a lot on the speed! Does it also use a conversion MTF?

[encode]

Have done a good job with BCM but seems anchors slow, needs to work a lot on the speed! Does it also use a conversion MTF?

No it has no MTF or other things like DC/IF/WFC...

[Black_Fox]

compression 21 kB/s, decompression 1495 kB/s, total size 13.791.746 bytes

pht.psd took over 20 minutes to sort! (I almost thought about guru meditation, as would Francesco say )

[osmanturan]

Tested on AMD Athlon 64 X2 Dual 4200+ (2.2 GHz), 1 GB RAM, WinXP SP3. Here is the results:

SFC
A10.jpg -> 830,651 (1.105 seconds)
AcroRd32.exe -> 1,595,953 (6.545 seconds)
english.dic -> 1,180,338 (4.382 seconds)
FlashMX.pdf -> 3,761,095 (6.484 seconds)
FP.log -> 557,444 (42.401 seconds)
MSO97.dll -> 1,927,126 (5.069 seconds)
ohs.doc -> 844,340 (33.651 seconds)
rafale.bmp -> 759,576 (5.124 seconds)
vcfiu.hlp -> 659,158 (5.933 seconds)
world95.txt -> 479,001 (4.054 seconds)

ENWIK8
21,824,948 (180.592 seconds)

Note: All tests' timing was measured by AcuTimer.

Do you think ohs.doc is a worst-case example for BWT transform? I have never tested a BWT compressor on SFC.

Could you explain your CM back-end implementation? Kind of approximation or low-order CM or anything else?

[encode]

Do you think ohs.doc is a worst-case example for BWT transform?

Seems to be. But the real worst case is for sure "pht.psd".
Actually, the most (or ALL) BWT compressors have the so called worst case. Even UHBC is really unstable on some kind of data...

Could you explain your CM back-end implementation? Kind of approximation or low-order CM or anything else?

It is low order CM. Some things are simplified to get better speed. We dynamically mix together various models with various contexts, including models with various update speeds. BCM v0.01 has five models and four dynamic mixers...
To get the basic idea what we can mix - check BBB source...

Well, I'm thinking to move to more advanced things like unary coder...

[joerg]

bcm v0.01

requests for different functions - different amount of ram

on a system with 4 gbyte ram:

sorting 460.752 MBytes long time run
encoding 329.548 MBytes short time run
begin sorting 460.552 MBytes
sorting 460.752 MBytes long time run

on a system with only 512 MBytes ram
bcm requests 80 up to 460 MBytes

compression:

sourcefile db.dmp 648.331.264 bytes

balz113 e 33.390.086 bytes 9 min
bcm 31.927.387 bytes 22 min
7zip 35.151.362 bytes 19 min

that means

1. bcm compresses better then balz113
but needs definitively more memory and more time

2. bcm can beat 7zip in compression ratio

Good work !

[pat357]

BCM v0.01 on enwik9 :

timer bcm e enwik9 enwik9_bcm001.bcm
--> 188.432.286 bytes in 1330.501s

System C2 Quad E6600 @2.2 Mhz / 4GB RAM

@encode :
Keep up the good work!
Do you have any plans to implement WFC/DWFC /MTF/Fragmentation in BCM ?

[pat357]

Do you think ohs.doc is a worst-case example for BWT transform? I have never tested a BWT compressor on SFC.

An interesting link to compare different sort algoritmes in "worst case" :
http://www.michael-maniscalco.com/msufsort.htm

(look below at "The Gauntlet (Universal Robustness Corpus)"

[encode]

BCM v0.01 on enwik9 :
Keep up the good work!
Do you have any plans to implement WFC/DWFC /MTF/Fragmentation in BCM ?

No reason to do WFC or other things and especially cheap MTF with my CM, further CM improvements are still possible!
Fragmentation already implemented, but it in some cases it do wrong job - I need more advanced detection, that's why I not included it in the first release...

[encode]

OK, the development of the next BCM in progress...

2 Shelwien:
The catch was in if (abs(p2-p1)>LIMIT)... New version still uses my simple and division-less mixers, but with abs() stuff.

Some testing results, again with no segmentation:

calgary.tar -> 792,883 bytes

world95.txt -> 474,647 bytes

book1 -> 213,132 bytes

Well, I'm onto something with such results...

[Shelwien]

I think its still too much...

1. Do you use forward comparisons for BWT?

2. What about inheritance for higher orders?
(like what I had to do in o2rc to get some effect from order2)

3. What about rangecoder precision? If you're still using
Matt's rc or something like that, then you might be losing
like 2-3k to redundancy.

---------

Also I tested more things with these coders recently

1. A simple weight increment/decrement (depending on p1<p2)
was added in a "else" branch of that limit check.
In the end it allowed to win like 10 bytes, and after a very long
tuning too.

2. Mask lengths for mixer limits were expanded to whole 15 bits -
gained like 200 bytes in o1rc and even less in o2rc with that.

3. The test with remixing the o0 & o1 estimation after mixer
updates and using the new estimations to update the w01
mixer... failed, even though it helped on some other data

---------

Next plans are:

1. Switching to 64-bit bytewise rangecoder, then to 64-bit
bitwise arithmetic coder. Also maybe rising the counter
and mixer precision too.

2. Generating the wr-tables (update tables for Node2i)
instead of using the precalculated ones. Well, I could
just use the other update function, but it contains a division,
and the slower coders are harder to tune.

3. Still haven't tried using a quantized weights in w01 context.

4. Have to think about replacing these fast counters with
"patch counters" working with strings of (bit^(p>0.5)) bits.

5. More detailed mixer/counter initialization; order1 inheritance;
rising the update speed on a sequence of mispredictions; etc etc

---------

Actually it might be useless to mess with a bitwise coder with
its inherent redundancy, but still I'd like to try out at least
some of these things.

[encode]

Shelwien - please check PM!

[Nania Francesco]

BCM in MOC test:
414.721.456 Bytes
COMP. TIME =4.989,256 sec. (Over time limit)
DEC. TIME=395,678 sec.

[encode]

In next version, possibly, I'll reduce block size and/or add a file segmenter, which may and should lead to faster and much faster compression/decompression...

[encode]

I move on...

calgary.tar -> 791,622 bytes

book1 -> 212,844 bytes

world95.txt -> 474,906 bytes

[encode]

calgary.tar -> 791,435 bytes

book1 -> 212,674 bytes

world95.txt -> 474,291 bytes

[encode]

Testing results with various block sizes:

sfc.7z:

1M -> 12,859,246 bytes
2M -> 12,770,368 bytes
3M -> 12,821,424 bytes
4M -> 12,716,255 bytes
5M -> 12,804,151 bytes
6M -> 12,899,078 bytes
7M -> 12,826,038 bytes
8M -> 12,935,605 bytes
16M -> 13,018,028 bytes
32M -> 13,167,873 bytes
64M -> 13,183,156 bytes

So anyways, I think I should keep, say, 8 MB or 16 MB block and do descent file segmentation. Note I have a few additional ideas about good auto-block size.
Well, if you have some experience or ideas about segmentation - please share!

[encode]

BCM v0.02 is here!

[joerg]

bcm v0.02

on a system with 4 gbyte ram:

sorting... request 58.640 kilobytes
encoding... request 42.236 kilobytes

compression:

sourcefile db.dmp 648.331.264 bytes

balz113 e 33.390.086 bytes 9 min
7zip 35.151.362 bytes 19 min
bcm 001 31.927.387 bytes 22 min
bcm 002 31.022.446 bytes 17 min

that means

1. bcm 002 compresses a little bit better then bcm001
and needs only a small amount of memory - wow !

2. bcm beat 7zip in compression ratio

very good work !

what about to implement compression of a whole directory incluive subdirs ?

[Shelwien]

The question was what's better,

const DWORD xmid=x1+(( ((unsigned __int64)(x2-x1))*DWORD(predictor.P()<<16))>>32);

or

const DWORD xmid=x1+(( ((unsigned __int64)(x2-x1))*DWORD(predictor.P()<<15))>>31);

And here's what some compilers generate...

http://shelwien.googlepages.com/mul64test.rar

Of course, IntelC wins
Though even for it I had to rewrite the expression
so that there won't be any ambiguity.

[encode]

what about to implement compression of a whole directory incluive subdirs ?

These days I will decide what kind of project I will work on.
If it will be BCM - I have some plans:
+ Make Linux version
+ Do further CM improvement
+ Add segmenter/filters
+ Add mulltiple files/folders compression

[LovePimple]

BCM v0.02 is here!

Thanks Ilia!

[Black_Fox]

Thanks! Is 0.02 eligible for public table entry or still something more non-public?

compression 21 kB/s, decompression 983 kB/s, total size 13.315.201 bytes
(0.01 = 21 kB/s, 1495 kB/s, 13.791.746)

[encode]

Thanks! Is 0.02 eligible for public table entry or still something more non-public? )

Well, this version is still for forum readers only...
But feel free to add results for both versions!