BCM v0.04 is here! [!]

[encode]

OK, a new version of BCM is here!

What's new:

• Improved CM back end (Added linear interpolation to the SSE)
• Changed block size to 64 MB
• Some code optimizations
• Some user interface improvements
• Fixed decoder's bug with a fake alert

Quick comparison:

calgary.tar
BCM -> 784,072 bytes
BLIZ -> 790,491 bytes
BBB -> 798,705 bytes
MCOMP -> 800,402 bytes
Original -> 3,152,896 bytes

book1
BCM -> 210,642 bytes
BLIZ -> 212,130 bytes
BBB -> 213,162 bytes
MCOMP -> 217,403 bytes
Original -> 768,771 bytes

world95.txt
BCM -> 469,603 bytes
BLIZ -> 474,891 bytes
MCOMP -> 474,985 bytes
BBB -> 475,408 bytes
Original -> 2,988,578 bytes

[m^2]

BOOKSTAR:
0.04 9171992 ~30
0.03 9262010 27.844

[Shelwien]

Can you add some switches for disabling BWT and postcoder,
or just make a separate executables for that?
If you do, we'd be able to compare your coder to
http://ctxmodel.net/files/ST2rc/ and some others.

[encode]

Can you add some switches for disabling BWT and postcoder,
or just make a separate executables for that?
If you do, we'd be able to compare your coder to
http://ctxmodel.net/files/ST2rc/ and some others.

If disable BWT and postcoder we will get a COPY command!
If I will have some spare minute I'll compile standalone CM back end from BCM, so you'll able to ensure that all your RCs are beaten... But not really sure should I produce such LEGO consturctor kit... At the same time, I described you my CM via ICQ - so you know all the stuff in detail!
All in all, BBB mistakenly uses too much APMs, instead of a good and tuned with each other counters as a main part of the coder.
Your RC lacks of SSE, yep you use dynamic mixing, it is cool, but as you can see, replacing dynamic mixing with static one and adding SSE is better.
Having said, if complete the square adding dynamic mixing or SSE2 with main SSE we will get something crazy, but slow! Yep, I tried to avoid BBB trip - overloaded and heavy duty CM that not really works well at the end. My CM is quite simple, but efficient enough. I may continue adding new bells and whistles to BCM to get even further... But still I want to keep BCM light-weight enough to be used in practice...

[Matt Mahoney]

http://cs.fit.edu/~mmahoney/compression/text.html#1854

[Hahobas]

AMD Athlon 64 3000+ @ 2.2GHZ (single core)
Testing with enwik8

bcm002a - 23,761,415 bytes - compress: 138 sec, decompress: 54 seconds
bcm003 - 22,007,655 bytes - compress 69 sec, decompress: 61 seconds
bcm 004 - 21,450,604 bytes - compress: 76 sec, decompress: 66 seconds

Way to go! Here's a chart.

[LovePimple]

OK, a new version of BCM is here!

What's new:

• Improved CM back end (Added linear interpolation to the SSE)
• Changed block size to 64 MB
• Some code optimizations
• Some user interface improvements
• Fixed decoder's bug with a fake alert

Thanks Ilia!

[m^2]

AMD Athlon 64 3000+ @ 2.2GHZ (single core)
Testing with enwik8

bcm002a - 23,761,415 bytes - compress: 138 sec, decompress: 54 seconds
bcm003 - 22,007,655 bytes - compress 69 sec, decompress: 61 seconds
bcm 004 - 21,450,604 bytes - compress: 76 sec, decompress: 66 seconds

Way to go! Here's a chart.

Why do you start the size chart at 20000000?
That's seriously misleading.

[joerg]

---
..\PGM\bcm003 e db.dmp ..\RESULT\tdbbcm3
bcm v0.03 by ilia muraviev
encoding...
ratio: 0.392 bpb
done
---
..\PGM\bcm004 e db.dmp ..\RESULT\tdbbcm4
bcm v0.04 by ilia muraviev
encoding 65536k block...
encoding 65536k block...
encoding 65536k block...
encoding 65536k block...
encoding 65536k block...
encoding 65536k block...
encoding 65536k block...
encoding 65536k block...
encoding 65536k block...
encoding 43312k block...
ratio: 0.399 bpb
done
---

sorry!

result:

The Testfile db.dmp (Oracle-dump-file) has 648331264 bytes.

bcm003 ratio: 0.392 bpb compress to 31783496 bytes 260 s
bcm004 ratio: 0.399 bpb compress to 32319001 bytes 280 s

the test takes an unexpected turn:

with my testfile -
bcm004 does not better compress then bcm003

---
RINGS v.1.3 (FCM Fast Context Mixing) file compressor. Only for testing
Copyright 2007 by Nania Francesco Antonio (Italy). All rights reserved.

rings13 c compress to 26356464 bytes time= 20.77 s.
---
Matt Mahoney:
rings 1.3 uses 54 MB for compression and 47 MB for decompression
---
---
--- BCM004 - Changed block size to 64 MB ---
---
---
it would be interesting
if we can test the new algorithm with another blocksize
may be 32 MB blocksize / 48 MB blocksize / 256 mb blocksize

[encode]

Well, RINGS is NOT BWT-based compressor!

As example, all BWT-based compressors are failed on english.dic:

english.dic
RINGS v.1.5c -> 566,326 bytes
BCM -> 1,166,789 bytes
BBB -> 1,170,489 bytes
BLIZ -> 1,170,607 bytes
MCOMP -> 1,190,740 bytes
DARK -> 1,192,700 bytes
SBC -> 1,195,254 bytes
Original -> 4,067,439 bytes

It's a proof that RINGS v.1.5c is not a BWT-based file compressor.

The same thing should be at the database compression. So do not compare apples and oranges!
Such performance on such specific data not displays a super compression...

[m^2]

Well, RINGS is NOT BWT-based compressor!

As example, all BWT-based compressors are failed on english.dic:

english.dic
RINGS v.1.5c -> 566,326 bytes
BCM -> 1,166,789 bytes
BBB -> 1,170,489 bytes
BLIZ -> 1,170,607 bytes
MCOMP -> 1,190,740 bytes
DARK -> 1,192,700 bytes
SBC -> 1,195,254 bytes
Original -> 4,067,439 bytes

It's a proof that RINGS v.1.5c is not a BWT-based file compressor.

The same thing should be at the database compression. So do not compare apples and oranges!
Such performance on such specific data not displays a super compression...

So what is it? When you run it, it says "fast context mixing".
http://heartofcomp.altervista.org/ says "bwt+ari".
What's up?

[joerg]

@encode
first i want to say:
thank you for your work!
the new bcm004 is a good compressor for several files and is it fast too

---
Matt Mahoney on http://www.cs.fit.edu/~mmahoney/compression/text.html
---
rings 1.3 uses 54 MB for compression and 47 MB for decompression.

rings 1.4c has an option (1-9) which selects memory usage
Each increment doubles usage
For option 9, compression uses 526 MB and decompression uses 789 MB.
The program uses BWT.
The transformed data is encoded using MTF (move to front),
pre-Huffman coding followed by arithmetic coding.

rings 1.5 was released Apr. 21, 2008.
It improves compression and is symmetric with regard to memory usage.
Options are like 1.4c.
---
rings 1.3 uses method CM
rings 1.4c uses method BWT+...
rings 1.5c uses method BWT+... ???
---
you are right about rings 1.3 it seems to use CM and not BWT

but why do you think - rings 1.5c does not use BWT ?

The good compression of a special file
is a unimpeachable evidence for
"RINGS v.1.5c is not a BWT-based file compressor" ??

i think only Nania Francesco knows how work the rings 1.5c inside ?

best regards

[encode]

I read some posts about RINGS at the old forum. Probably, RINGS uses ST4 or something. ST4 is a "limited order BWT". Nania speaks via translator - it's not a trivial task to understand what he means sometimes. Anyway:
Rings 1.0 - 1.4c use:
Fast BWT->MTF->PRE-HUF->ARI

PRE-HUF is:
PRE-HUF ->
0=bit 0
1=bits 100
2=101
3=1100 etc.

Maybe I should try this PRE-HUF idea? Adding SSE and many contexts...

Anyway, I was really impressed by RINGS myself. And as with Christian's programs one question comes to mind - "How he did that??"

[toffer]

"Pre-Huff" is a very nice feature, since it can improve compression and boosts the coding speed extremely.

With a byte oriented CM output coding (flat decomposition) you *always* have to do 8 coding steps, normally and you have as may distinct symbols as the source emits.

With MTF the number of distinct symbols may be reduced, since a context history is mostly dominated by the last seen symbol(s) 0, 1, 2, ... , thus ~50-60% of the data is a "0" after the MTF stage. If the "0" symbol gets a 1 bit huffman code you can code 50-60% of the data with just one coding step.

Some experience tells me:

P(0) = 0.60 -> 0.74 bit ~ 1 bit (rounded up to be pessimistic)
P(1) = 0.15 -> 2.74 bit ~ 3 bit
P(2) = 0.05 -> 4.32 bit ~ 5 bit

where P(s) is the probability of s (here s is the context rank, which should be similar to the MTF symbol distribution). As you see the symbols 0..2 cover ~80% of the whole data. The average number of coding steps per symbol (for 80% of the data) would be:

1 * 0.6 + 3 * 0.15 + 5 * .05 = 1.3 bit

Your approach uses 8 steps for all of the data. Hence one can see that the post coder can be accelerated by a factor of 4..6 and compression can be improved, too. But that depends on the applied decomposition and data.

[encode]

But by itself MTF may destroy some correlations... Anyway, the idea is worth to implement.

[toffer]

You don't need to use the same alphabet for contexts and coded symbols. So using the original alphabet for contexts and the MTFed alphabet for coding the current symbols you won't loose anything.

[encode]

Well, with my CM this not works for sure...

[JangoFatXL]

Is there any chance for a gui (or at least for a readme which contains all commands...)?

[toffer]

Why shouldn't it work? It's pretty easy, actually...

[encode]

Is there any chance for a gui (or at least for a readme which contains all commands...)?

BCM has just two commands:
e - encode (compress)
d - decode (decompress)



To encode 'book1' to 'book1.bcm':
bcm e book1 book1.bcm

To decode:
bcm d book1.bcm book1

Additionally, you may use the 'Send To' menu with a BAT file.
Create a new TXT file and type:
bcm e %1 %1.bcm

Rename the file to, say, 'bcm.bat'.

Copy this file to:
C:\Users\<User Name>\AppData\Roaming\Microsoft\Windows\SendTo\
(Under Windows Vista)

Copy bcm.exe to:
C:\Windows\

Done!

Well, I have some plans about making BCM Open Source as well as a part of the PIM archiver! But it will be only after I'll finish working on it!

[squxe]

I have some plans about making BCM Open Source as well as a part of the PIM archiver!

Wow! It will be great!

[JangoFatXL]

thx

[nanoflooder]

I'm actually impressed by BCM's performance My previous tests showed NanoZip's domination among BWT compressors, but not this time...

aaz@rover:/media/data$ ls -laS reymont*
-rwxrwxrwx 1 root root 6627202 2009-02-15 01:06 reymont
-rwxrwxrwx 1 root root 1246230 2009-02-15 01:39 reymont.bz2
-rwxrwxrwx 1 root root 1004263 2009-02-15 02:00 reymont.bwt.mcp
-rwxrwxrwx 1 root root 1000560 2009-02-15 01:07 reymont.co.nz
-rwxrwxrwx 1 root root  988205 2009-02-15 01:15 reymont.cO.nz
-rwxrwxrwx 1 root root  983275 2009-02-15 02:31 reymont.bbb
-rwxrwxrwx 1 root root  982045 2009-02-15 01:33 reymont.bcm
-rwxrwxrwx 1 root root  970558 2009-02-15 01:19 reymont.cc.nz

Currently I am stumped to find any everyday BWT compressor (apparently nz -cc doesn't belong to them) to beat BCM at this file

Though it needs some tuning for big files:

aaz@rover:/media/data$ ls -laS wine-1.1.15.*
-rwxrwxrwx 1 root root 111175680 2009-02-15 02:20 wine-1.1.15.tar
-rwxrwxrwx 1 root root  12865441 2009-02-15 02:26 wine-1.1.15.tar.co.m723m.nz
-rwxrwxrwx 1 root root  12830801 2009-02-15 02:23 wine-1.1.15.tar.bcm
-rwxrwxrwx 1 root root  12828612 2009-02-15 02:46 wine-1.1.15.tar.bwt.mcp
-rwxrwxrwx 1 root root  12712151 2009-02-15 02:25 wine-1.1.15.tar.cO.m599m.nz
-rwxrwxrwx 1 root root  12712151 2009-02-15 02:26 wine-1.1.15.tar.cO.m739m.nz
-rwxrwxrwx 1 root root  12606927 2009-02-15 02:46 wine-1.1.15.tar.bbb

I know, BBB took way more than the others to compress, but BCM also lost to mcomp and nz -cO

[encode]

It's important to test BCM with others with the same block size. On binary data, for example, BBB with a smaller block size may beat BCM, but with the same block size may not beat. Mostly BCM is the strongest from all!
BLIZ uses LZP preprocessing that may really help in some cases - pht.psd as example. NanoZip has a heavy preprocessing, additionally to multiple algorithm selection. I beleive that even with '-co' NZ in some cases may choose not its BWT - my test shown that. At the same time BCM has only a simple E8/E9 transformer.
BWT, check out a small example, how NanoZip performs with and without preprocessing. To disable its preprocessing I XORed the test file with 128:

book1:
BCM -> 210,642 bytes
NZ -> 196,190 bytes

XORed book1:
BCM -> 210,745 bytes
NZ -> 214,693 bytes

You may see that BCM has closely the same performance on XORed book1, at the same time, NanoZip showed the REAL performance of its BWT. BCM is MUCH stronger!

Furthermore, v0.04 is not the final version of BCM. I already working on even stronger CM back end - yep it's more complex, but at the same time due to some optimizations and making it more cache efficient I hope that I'll not loose too much processing speed, and probably will make my CM even faster!

[nanoflooder]

BWT, check out a small example, how NanoZip performs with and without preprocessing.

"BWT" - a funny typo there

To disable its preprocessing I XORed the test file with 128:

book1:
BCM -> 210,642 bytes
NZ -> 196,190 bytes

XORed book1:
BCM -> 210,745 bytes
NZ -> 214,693 bytes

You may see that BCM has closely the same performance on XORed book1, at the same time, NanoZip showed the REAL performance of its BWT. BCM is MUCH stronger!

Good idea for testing the algos Though... Come on, this time it's not much stronger, is it Just four kilobytes. But the difference between the presence and abscence of preprocessing in nz is obvious.

Furthermore, v0.04 is not the final version of BCM. I already working on even stronger CM back end - yep it's more complex, but at the same time due to some optimizations and making it more cache efficient I hope that I'll not loose too much processing speed, and probably will make my CM even faster!

This is really important. BCM is quite fast (fast enough to be used in r/l) and powerful indeed, while it doesn't even have any "tweaks" - it's just a compressor, not even an archiver. There's still much room to go and to achieve, I think it might be very very competitive in the future

[Black_Fox]

I XORed the test file with 128:
(...)
XORed book1:
BCM -> 210,745 bytes
NZ -> 214,693 bytes
(...)
NanoZip showed the REAL performance of its BWT

You're lucky that Sami doesn't log on his account anymore, otherwise new flamewar would probably begin

[encode]

You're lucky that Sami doesn't log on his account anymore, otherwise new flamewar would probably begin

It's not a flame, it's just a direct comparison of BWT-based coders.

BTW, Sami said that his BWT is based on QLFC. So, check out some small paper on QLFC:

[m^2]

It's important to test BCM with others with the same block size. On binary data, for example, BBB with a smaller block size may beat BCM, but with the same block size may not beat. Mostly BCM is the strongest from all!
BLIZ uses LZP preprocessing that may really help in some cases - pht.psd as example. NanoZip has a heavy preprocessing, additionally to multiple algorithm selection. I beleive that even with '-co' NZ in some cases may choose not its BWT - my test shown that. At the same time BCM has only a simple E8/E9 transformer.
BWT, check out a small example, how NanoZip performs with and without preprocessing. To disable its preprocessing I XORed the test file with 128:

book1:
BCM -> 210,642 bytes
NZ -> 196,190 bytes

XORed book1:
BCM -> 210,745 bytes
NZ -> 214,693 bytes

You may see that BCM has closely the same performance on XORed book1, at the same time, NanoZip showed the REAL performance of its BWT. BCM is MUCH stronger!

Furthermore, v0.04 is not the final version of BCM. I already working on even stronger CM back end - yep it's more complex, but at the same time due to some optimizations and making it more cache efficient I hope that I'll not loose too much processing speed, and probably will make my CM even faster!

So maybe add LZP too? Or unusual option: REP. I tested it a bit with grzip / ppmd and it works pretty well/ In the end output was usually slightly bigger than with LZP, but REP decompresses faster.

[encode]

LZP may hurt compression in some cases.

The better way is a stronger CM! Currently I'm working really hard on a new CM - analyzing and optimizing each part of a model - this hardcore work may took from a few weeks to a few months...

[m^2]

The better way is a stronger CM!

Not for decompression speeds.
LZ should improve them, stronger CM worsens (heuristic rule).