BCM - The ultimate BWT-based file compressor

[Matt Mahoney]

When I wrote an inverse BWT in ZPAQL, I stuffed an extra byte in the BWT for the EOF. Then you can eliminate the (i>=p) everywhere.

[encode]

http://sourceforge.net/projects/bcm/

[Matt Mahoney]

http://mattmahoney.net/dc/silesia.html
http://mattmahoney.net/dc/text.html#1639

Sorry I couldn't test enwik9 with -b1000

[encode]

C:\Test>bcm -b100 -f enwik8
enwik8: 100000000 -> 20792796 in 12.766s

C:\Test>bcm -d -f enwik8.bcm e8
enwik8.bcm: 20792796 -> 100000000 in 11.922s

C:\Test>bcm -b1000 -f enwik9
enwik9: 1000000000 -> 164251284 in 147.229s

C:\Test>bcm -d -f enwik9.bcm e9
enwik9.bcm: 164251284 -> 1000000000 in 142.072s

BTW, the 64-bit build can be slightly faster - I have to remove 32-bit related optimizations - will add a couple of #ifdef _WIN32 in next versions of BCM.

[Matt Mahoney]

Thanks. Updated http://mattmahoney.net/dc/text.html#1639

My webpage was broken yesterday due to uploading to my website not working. It seems to be fixed now.

[xezz]

It is very small improvement for encoding block size and pidx.

[encode]

Thanks, but it's not an improvement - it may really hurt compression in some cases with tiny blocks - I tested this approach many times...
In addition, you are wrong here - p(0.5) for Encoder::Encode is 1<<17, not 32768. To not be mistaken by Counter's scale - the final probability scale is 1<<18 - p+ssep+ssep+ssep
Also, be aware of changing the output format - all public versions of BCM must be compatible now!
The thing I really would love to improve is inverse BWT - many compilers output really inefficient code - it is even slower than actual BWT transform. Only with PGO it becomes faster!

[xezz]

In addition, you are wrong here - p(0.5) for Encoder::Encode is 1<<17, not 32768.

I'm sorry. corrected it.

[encode]

The second and the very important purpose of such slightly redundant size/pidx coding is error detection - since BCM has no CRC or other checksum checking...

[joerg]

bcm-w64 -b1000 source archive

seems to be (under win server 2008 R2) faster and compress better as

bcm-w32 source archive

can this be true ?

i will run further tests

best regards

[encode]

In many cases - the larger block size, the better. And yes, the 64-bit version must be faster. However, with the current inverse BTW, the 32-bit version is faster at decompression.

[joerg]

thank you for your answer.

PGO for further x64-optimization ..
Does it mean that we need a special intel-x64-version and another special AMD-x64-version?

best regards

[Matt Mahoney]

I didn't look at the code, but in zpaq I have 2 versions of the inverse BWT, one for blocks up to 16 MB and one for blocks up to 4 GB. For the smaller blocks, I pack the linked list pointers and the character it points to into a single 32 bit variable. This speeds up the algorithm because there is only one cache miss per character instead of two. (Building the list like this only requires sequential memory access). For larger blocks you could have a 5 byte structure to do this, but since I was writing it in ZPAQL it wouldn't be easy to do.

I think I recall BSC has an inverse BWT that outputs 2 bytes at a time to reduce cache misses even further.

[encode]

ICL's PGO (Profile Guided Optimization) didn't help with a 64-bit compile. Can't say about modern AMD CPUs - I don't have one.

I know about this trick - will test it more carefully. I didn't include it right away because the default block size is 20 MB (To keep the memory usage slightly over 100 MB)

[joerg]

running under win server 2008 R2 (virtual machine AMD processors)

bcm-w64 -b1000 e:backup.dat c:bac-bcm64
e:backup.dat: 54801567744 -> 5349330866 in 35905.593s

bcm-w32 e:backup.dat c:bac-bcm32
e:backup.dat: 54801567744 -> 6670331585 in 18204.265s

for now: bcm-w64 has a good potential!

bcm-w64 compress nearly 20% better then bcm-w32

but in my test
bcm-w64 takes nearly twice as much time as bcm-w32

if bcm-w64 can run so quick as bcm-w32
than it maybe can beat 7zip in efficiency

i will run further tests - best regards

[encode]

As a note, you're comparing 20 MB block BWT with 1000 MB block BWT...
You may use -b2047 or even -b2097151k as well!

[encode]

A memo for myself

BCM - A BWT-based file compressor, v1.01

Usage: bcm [options] infile [outfile]

Options:
  -b#[k] Set block size to # MB or KB (default is 20 MB)
  -d     Decompress
  -f     Force overwrite of output file

[quadro]

Good that the source code is so small, so at least it build real fast and real nice results overall.

At the few tests I done, it seem not to use much above the 5n space, for a specified block size, which is also good point.

(Tested on a netbook: Aspire One Intel(R) Atom(TM) CPU N2600 @ 1.60GHz, 2 cores Ubuntu 64-bit )

./bcm -b100 -f enwik8 enwik8.bcm
enwik8: 100000000 -> 20792796 in 118.390s
C.Time: 116.62 s user, 1.78 s system, 1:59.84 total; Used 98% CPU, memory: 489404 kB

./bcm -d -f enwik8.bcm enwik8.dec
enwik8.bcm: 20792796 -> 100000000 in 94.042s
D.Time: 90.92 s user, 3.13 s system, 1:35.38 total; Used 98% CPU, memory: 489184 kB

[encode]

BCM v1.01 @ GitHub:
https://github.com/encode84/bcm

[hexagone]

Ilya,

BCM is a fantastic combination of speed, code simplicity and compression efficiency.
Thanks for sharing the code.

I adapted it to my project:

https://github.com/flanglet/kanzi/blob/master/java/src/kanzi/entropy/CMPredictor.java
https://github.com/flanglet/kanzi/bl...CMPredictor.go

java -cp kanzi.jar kanzi.app.BlockCompressor -input=enwik8 -output=none -block=100m -transform=bwt -entropy=cm -verbose=1
Encoding ...
Encoding: 26546 ms
Input size: 100000000
Output size: 20792267
Ratio: 0.20792268
Throughput (KB/s): 3678

go run BlockCompressor.go -input=enwik8 -output=none -block=100m -transform=bwt -entropy=cm -verbose=1
Encoding ...
Encoding: 47726 ms
Input size: 100000000
Output size: 20792267
Ratio: 0.207923
Throughput (KB/s): 2046

[encode]

I see some code from BCM here... And I see no project contributors list...
Well, just a quick note on SLOW_RATE/FAST_RATE:
SLOW_RATE is 6 here, fast is 2.

[hexagone]

And I see no project contributors list...
Well, just a quick note on

What do you mean ? Your name is at the top of the file.

Well, just a quick note on SLOW_RATE/FAST_RATE:
SLOW_RATE is 6 here, fast is 2.

Yeah, I renamed the constants at some point and messed up the names. Will change.

[encode]

Uh, I have searched for detailed README with algos description... You have from A to Z compression algos here!

[hexagone]

I am not claiming it is super detailed but you can start with the WIKI: https://github.com/flanglet/kanzi/wiki

[encode]

Updated to BCM v1.02. Sort of a final version that features long awaited optimizations!

https://github.com/encode84/bcm

[Alexander Rhatushnyak]

A makefile or a toCompile.bat would be helpful.

Also, why not (k<<12)-(k==16) instead of (k-(k==16))<<12 in CM() ? Seems more logical, doesn't it?

[encode]

You are right! It's just the SSE initialization I'm using for years (if not decades)!
Collecting ideas for BCM v2.00...

[encode]

Should I release a slightly changed version of BCM, breaking compatibility (BCM is not that widespread I presume)?
Maybe with some extra features you suggest? (CRC32 checking? Higher compression at slower speed? ...?)

[Cyan]

I believe you have no issue with "installed base".

But current BCM source version has a great property : simplicity.
This is a very worthy characteristic, which is worth more than little gains and features.

Now, of course, adding feature / performance while preserving simplicity, this would a great way forward.

[Gonzalo]

Can't you just add the old uncompressor code to the new release? Or make something like SQX, capable to write 2 different versions of the standard, 1.1 and 2.0 I think.