Advice in data compression

[Chuckie]

Hello to all,

I am having problems trying to compress data from this file (gv2.txt in .rar in attachment).
It contains only numbers and the best compression that I got was with paq8o8z and the output file was 954 bytes (6184 bytes original).
I was wondering can I compress that file even further, i.e. to go less than 900 bytes and with what compression method/algorithm.
What would you, experts of the compression world, suggest me, a novice in all of this!

Thank you for your time and effort in advance!

Sincerely yours,
Caslav

[Fu Siyuan]

I've learnt that there is no universal good compression model. So it's not a surprise that even if the current 'best algorithm' can't compress it to your satisfied size. I looked into the original file. It contains only thousands of bytes (0x0-0xff) but writes in text. And the difference between successive numbers isn't much. So I believe a simple transform would make it less than 900 bytes.

[Chuckie]

I tried all sort of compression algorithms and paq was the best, and yes the numbers contained in .txt go from 0-255.
I also tried delta coding and I couldn't pass the 900 bytes barrier.

Could you suggest me some simple transforms?
Thank you!

[Cyan]

Maybe you could start transforming source file from text to bytes,
this would make the source file 4x smaller.
Note however that final compressed result is likely to be just a little bit better, and yes, there is a limit to what compressors can do.

[Chuckie]

When I transformed text to bytes I get a file around 1675 bytes...

[Cyan]

When I transformed text to bytes I get a file around 1675 bytes...

you mean, before compression ?

[osmanturan]

I've analyzed the file with MATLAB. The source almost random. Delta filter does not help. Because, the range is increased and standard deviation is still high. Here's some stats:

Text-to-Byte conversion (without whitespaces which is easy to model in our case): 1674 bytes
Max. Sample Value: 244
Min. Sample Value: 44
Max. Range: 200
Mean: 133.1756
Std. Dev.: 46.3860

After Delta Transform:
Max. Sample Value: +168
Min. Sample Value: -168
Max. Range: 336
Mean: 0.1219
Std. Dev: 47.8287

If you can give some more descriptive information about the source model, we can offer something.

[Fu Siyuan]

Maybe you could start transforming source file from text to bytes,

I meant this. Unfortunately, I tried and get far from less than 900 bytes.

[biject.bwts]

When I transformed text to bytes I get a file around 1675 bytes...

I meant this. Unfortunately, I tried and get far from less than 900 bytes.

I don't have the converted file. Assuming you converted bijectively then
you have all the information of the original file.

At this point a farther bijective compression is needed such as ARB255
or BICOM. If this doesn't work you could transform the file more buy
creating a new file from the byte file doing, a BWTS once or twice,
or, a UNBWTS once or twice.

At this point using ARB255 after a series of BWTS's or UNBWTS's
would gain nothing but what ever method you tried on the original
1675 byte file might work or even BICOM which is a bijective
ppm compressor.

Hope this helps small file compression is fun

[osmanturan]

I have tried LPC model fitting via genetic algorithm with MATLAB. The result is same. The source almost random. By assuming that it's an analog signal, I've plotted it's frequency spectrum. Seems, the source itself consists all frequency components This shortly means, it's hard to compress. I really wonder what kind of source are generated this output

[Shelwien]

bwtmix wins
http://www.ctxmodel.net/files/gv2_0.rar

Results
899 - gv2.ari
1674 - gv2.bin
6184 - gv2.txt
1674 - gv2unp.bin
6184 - gv2unp.txt

[Cyan]

The input looks like a sound wav sample.
If that is the case, then even very moderately lossy compression would provide much stronger compression and remain acceptable...

[Edit] nice record Shelwien !

[Shelwien]

Sound? this? Its more easy to see some 2D correlations there,
but I couldn't see any specific row size actually.

000:  09 09 0B 10 0F 10 0E 0F │ 10 11 10 11 12 10 10 10
010:  11 0D 0C 10 0D 0A 0A 0D │ 10 0F 11 10 10 11 11 10
020:  0E 0B 0C 0D 0F 11 12 10 │ 12 12 12 12 12 13 13 12
030:  10 0D 0D 10 12 12 12 11 │ 12 11 11 12 12 12 11 0C
040:  0B 0B 0D 0F 12 12 11 10 │ 0E 05 0A 0C 0D 0D 0E 0D
050:  0E 10 11 11 12 11 12 12 │ 0E 0D 0F 04 03 10 0A 04
060:  05 06 09 11 0F 12 11 11 │ 12 11 0D 02 03 03 04 04
070:  07 10 12 0A 04 07 06 03 │ 05 08 10 0F 11 11 0A 03
080:  09 0B 09 07 0B 0F 0A 0E │ 0D 0E 05 0B 0B 0D 11 12
090:  12 11 08 03 09 09 07 09 │ 0C 12 14 10 0D 08 0C 0E
0A0:  07 05 03 0F 10 11 0D 0E │ 03 06 07 0A 07 0E 07 09
0B0:  06 08 07 0F 0B 0B 12 11 │ 11 11 02 03 06 06 05 05
0C0:  04 03 07 08 10 13 16 10 │ 07 08 0D 05 05 05 07 0A
0D0:  0A 07 03 03 10 10 10 07 │ 08 06 08 0C 04 10 0B 03
0E0:  05 0E 05 0C 02 0D 07 0A │ 0C 0B 0C 08 0E 03 13 05
0F0:  0F 06 09 02 0F 04 09 09 │ 13 0B 11 12 11 02 03 08
100:  07 0C 03 05 10 08 08 0F │ 14 16 14 0C 0C 05 03 0D
110:  10 07 0D 0B 04 02 05 11 │ 10 11 0E 0C 12 10 0E 02
120:  0C 05 0A 08 09 09 0B 0D │ 0F 0B 0B 0D 10 0A 11 0C
130:  13 11 0E 02 02 09 0C 09 │ 0C 0C 0B 0F 16 14 0E 0F
140:  0D 10 14 12 0F 03 02 0E │ 10 11 03 0C 0D 13 0F 03
150:  03 02 0F 0F 0D 15 16 13 │ 15 11 02 03 02 0C 0F 10
160:  10 0E 0D 0E 13 11 04 02 │ 03 0F 10 17 15 16 14 0D
170:  02 02 02 0E 0F 0A 0B 0F │ 0D 13 0E 0B 02 02 09 10
180:  10 0F 10 15 16 16 16 16 │ 13 05 03 03 02 07 11 0F
190:  0F 04 10 17 17 17 02 0A │ 0F 10 03 02 0F 0E 0F 08
1A0:  0E 13 16 0D 11 16 14 15 │ 0E 02 03 03 04 04 0E 0E
1B0:  10 0A 03 0A 08 10 12 14 │ 10 02 0B 0E 12 0D 03 02
1C0:  03 04 10 0E 0F 13 16 17 │ 16 15 13 05 04 03 02 02
1D0:  09 0F 10 10 05 13 07 02 │ 12 08 0A 0F 10 00 04 06
1E0:  09 06 04 03 0E 10 11 11 │ 16 16 10 03 03 02 0C 0F
1F0:  05 10 03 0D 06 05 05 0F │ 10 02 02 07 05 02 02 03
200:  0E 0F 0F 10 11 12 16 16 │ 14 10 02 02 02 02 0E 0E

Also, this is the freq table (starting from 0 aka 44):

{ 1, 1, 55, 71, 
124, 160, 99, 67, 75, 83, 65, 58, 73, 75, 91, 
103, 122, 80, 95, 59, 34, 23, 28, 21,  8,  3 }

[Jan Ondrus]

Sound? this? Its more easy to see some 2D correlations there,
but I couldn't see any specific row size actually.

000:  09 09 0B 10 0F 10 0E 0F │ 10 11 10 11 12 10 10 10
010:  11 0D 0C 10 0D 0A 0A 0D │ 10 0F 11 10 10 11 11 10
020:  0E 0B 0C 0D 0F 11 12 10 │ 12 12 12 12 12 13 13 12
030:  10 0D 0D 10 12 12 12 11 │ 12 11 11 12 12 12 11 0C
040:  0B 0B 0D 0F 12 12 11 10 │ 0E 05 0A 0C 0D 0D 0E 0D
050:  0E 10 11 11 12 11 12 12 │ 0E 0D 0F 04 03 10 0A 04
060:  05 06 09 11 0F 12 11 11 │ 12 11 0D 02 03 03 04 04
070:  07 10 12 0A 04 07 06 03 │ 05 08 10 0F 11 11 0A 03
080:  09 0B 09 07 0B 0F 0A 0E │ 0D 0E 05 0B 0B 0D 11 12
090:  12 11 08 03 09 09 07 09 │ 0C 12 14 10 0D 08 0C 0E
0A0:  07 05 03 0F 10 11 0D 0E │ 03 06 07 0A 07 0E 07 09
0B0:  06 08 07 0F 0B 0B 12 11 │ 11 11 02 03 06 06 05 05
0C0:  04 03 07 08 10 13 16 10 │ 07 08 0D 05 05 05 07 0A
0D0:  0A 07 03 03 10 10 10 07 │ 08 06 08 0C 04 10 0B 03
0E0:  05 0E 05 0C 02 0D 07 0A │ 0C 0B 0C 08 0E 03 13 05
0F0:  0F 06 09 02 0F 04 09 09 │ 13 0B 11 12 11 02 03 08
100:  07 0C 03 05 10 08 08 0F │ 14 16 14 0C 0C 05 03 0D
110:  10 07 0D 0B 04 02 05 11 │ 10 11 0E 0C 12 10 0E 02
120:  0C 05 0A 08 09 09 0B 0D │ 0F 0B 0B 0D 10 0A 11 0C
130:  13 11 0E 02 02 09 0C 09 │ 0C 0C 0B 0F 16 14 0E 0F
140:  0D 10 14 12 0F 03 02 0E │ 10 11 03 0C 0D 13 0F 03
150:  03 02 0F 0F 0D 15 16 13 │ 15 11 02 03 02 0C 0F 10
160:  10 0E 0D 0E 13 11 04 02 │ 03 0F 10 17 15 16 14 0D
170:  02 02 02 0E 0F 0A 0B 0F │ 0D 13 0E 0B 02 02 09 10
180:  10 0F 10 15 16 16 16 16 │ 13 05 03 03 02 07 11 0F
190:  0F 04 10 17 17 17 02 0A │ 0F 10 03 02 0F 0E 0F 08
1A0:  0E 13 16 0D 11 16 14 15 │ 0E 02 03 03 04 04 0E 0E
1B0:  10 0A 03 0A 08 10 12 14 │ 10 02 0B 0E 12 0D 03 02
1C0:  03 04 10 0E 0F 13 16 17 │ 16 15 13 05 04 03 02 02
1D0:  09 0F 10 10 05 13 07 02 │ 12 08 0A 0F 10 00 04 06
1E0:  09 06 04 03 0E 10 11 11 │ 16 16 10 03 03 02 0C 0F
1F0:  05 10 03 0D 06 05 05 0F │ 10 02 02 07 05 02 02 03
200:  0E 0F 0F 10 11 12 16 16 │ 14 10 02 02 02 02 0E 0E

Also, this is the freq table (starting from 0 aka 44):

{ 1, 1, 55, 71, 
124, 160, 99, 67, 75, 83, 65, 58, 73, 75, 91, 
103, 122, 80, 95, 59, 34, 23, 28, 21,  8,  3 }

[biject.bwts]

bwtmix wins
http://www.ctxmodel.net/files/gv2_0.rar

Results
899 - gv2.ari
1674 - gv2.bin
6184 - gv2.txt
1674 - gv2unp.bin
6184 - gv2unp.txt

dropping in the old BWTMIX I used as a starting code I
get
903
replacing that one with BWTS in stead of BWT
using bmixbwts I get
898 which is better

[Chuckie]

Guys, thank you, THANK YOU VERY VEEEE...EERY MUCH...

When I saw 899 bytes I couldn't believe my eyes.
Shelwien, I appreciate your effort very much, thank you!

I am satisfied with this result, but my "boss" wants me to use paq8, alas.
So does anybody know a decent paq8 to reach the result of bwtmix?!

I tred paq8o8z with gv2.bin and got around 934 bytes.
Used FrontPAQ (no source code) and got 913 bytes...



Thx again and I am sorry we ain't close so I can buy you guys a beer or two... (if there is another way I can return the favor...)

[willvarfar]

Often when comparing compressors you include the size of the decompressor too - the footprint if you like.

Is the footprint of the (de)compressor important?

[osmanturan]

AFAIR, ZPAQ has a BWT config file which have a potential to reach that barrier if you really want to stick PAQ series. You may want to look at it.

[ddfox]

I can't download from
http://www.ctxmodel.net/files/gv2_0.rar
Can somebody attach the file in the post?

[Shelwien]

...

[ddfox]

...

thanks!

[Sportman]

You can compare different archivers with your file as text:

http://www.metacompressor.com/uploads.aspx?testfile=gv2
http://www.metacompressor.com/top.aspx?testfile=gv2

Or values as Int8 binary:

http://www.metacompressor.com/upload...?testfile=gv2b
http://www.metacompressor.com/top.aspx?testfile=gv2b

Or values divided by 4, minus 9, divided by 2, minus 1 as Int8 binary:

http://www.metacompressor.com/upload...?testfile=gv2c
http://www.metacompressor.com/top.aspx?testfile=gv2c

[Shelwien]

> When I saw 899 bytes I couldn't believe my eyes.

Actually its possible to further improve it, like
- remove 44 and 52 from "alphabet" and store their offsets instead
(they occur only once)
- reorder the values (preferably, separately for BWT and bitwise coding)
- skip coding of high 3 bits (preferably, also mask out other unused codes)

> I am satisfied with this result, but my "boss" wants me to use paq8, alas.

With paq8 all points above apply, and also you can
- use my binary transform from gv2_0.rar instead of plain ascii to binary
- remove the paq8 archive header (its like 30 bytes)
- disable unapplicable models (like text,images)

But in general paq8 is a bad idea here - similar or better results can
be reached with a tuned order0 coder, so all the paq8's complexity
doesn't make any sense.

> So does anybody know a decent paq8 to reach the result of bwtmix?!

The file is too small, so redundancy (like headers, rc flush overhead,
slow learning rate) is very noticeable with paq8.
And tuning paq8 to specific case is hard and probably unreasonable
if there're actually more data like that.
But even then something different, like m1, makes more sense than paq.

> I tred paq8o8z with gv2.bin and got around 934 bytes.
> Used FrontPAQ (no source code) and got 913 bytes...

That's because of headers probably.
Anyway, you can try all the versions there http://paq8.hys.cz/ http://dhost.info/paq8/
also older at (since paq1; they might show better results actually)
http://cs.fit.edu/~mmahoney/compression/#paq or
http://mattmahoney.net/dc/#paq
with all compression levels on both binary files (direct and (x-44)/8)
and find the best result, after cutting out the archive header.

But actually this approach is really wrong :)

[Shelwien]

As an example, http://nishi.dreamhosters.com/u/gv2_1.rar
858 bytes. Its just the postcoder from bwtmix now, without BWT,
with some tweaks. I'd post the source if anybody wants that,
but its not really useful imho.
Details:
-1 5-bit coding
-1 extra check for >=26
-1 redundant rc cache byte removed
-2 rc flush optimized
-4 file size field removed (hardcoded 1674)
-26 tuning of model's parameters

But anyway, all of this doesn't make sense really.
Improving compression by 5% at 1k scale doesn't mean
that there'd be the same improvement at 1M scale
(in fact, likely the reverse, because tuning for small files
tends to oversimplify the models).
I guess, it might be still applicable if there's random access
to small independently compressed records or something,
but again, in that case there're some better methods.

[Bulat Ziganshin]

just store it inside decoder

[Shelwien]

Most of modification applied are still generic and would work for any
samples of that kind.

[Skymmer]

Chuckie, if you still want some PAQ8 as final touch for your file then you can use the following chain:
gv2.txt -> 1.exe -> gv2.bin -> rename to 0 -> paq8kx_v7 -8 0 -> 899 bytes
Actually you can use any level in this situation.

[Chuckie]

As an example, http://nishi.dreamhosters.com/u/gv2_1.rar
858 bytes. Its just the postcoder from bwtmix now, without BWT,
with some tweaks. I'd post the source if anybody wants that,
but its not really useful imho.
Details:
-1 5-bit coding
-1 extra check for >=26
-1 redundant rc cache byte removed
-2 rc flush optimized
-4 file size field removed (hardcoded 1674)
-26 tuning of model's parameters

But anyway, all of this doesn't make sense really.
Improving compression by 5% at 1k scale doesn't mean
that there'd be the same improvement at 1M scale
(in fact, likely the reverse, because tuning for small files
tends to oversimplify the models).
I guess, it might be still applicable if there's random access
to small independently compressed records or something,
but again, in that case there're some better methods.

I'd like the source code please... If nobody wants it send it to my mail: clivada@gmail.com thx

Wonderful work!!

Thank you for your addiotional post for paq8.

[Chuckie]

Chuckie, if you still want some PAQ8 as final touch for your file then you can use the following chain:
gv2.txt -> 1.exe -> gv2.bin -> rename to 0 -> paq8kx_v7 -8 0 -> 899 bytes
Actually you can use any level in this situation.

I can't believe just by renaming gv2.bin -> 0 the file is 6 bytes smaller... o_0
Some would say: "LOL!"

[Shelwien]

> I'd like the source code please...

Well, this (still 85: http://nishi.dreamhosters.com/u/gv2_2.rar

Though original bwtmix postcoders at http://ctxmodel.net/files/mix_test/mix_test_v9.rar
seem to make 890-891 as is.

> I can't believe just by renaming gv2.bin -> 0 the file is 6 bytes smaller... o_0

There's nothing surprising really, and I already mentioned it a few times.
Most paq archives have a header like this:
(except for paq8px where its compressed too)

00000000:  70 61 71 38 70 20 2D 36 │ 0D 0A 31 36 37 34 09 67   paq8p -6  1674 g
00000010:  76 32 2E 62 69 6E 0D 0A │ 1A FB 65 F6 F5 F9 3B C6   v2.bin  √eЎї∙;╞
00000020:  20 F3 2C 49 0F 22 E9 D7 │ B1 85 D2 F8 2C 41 38 EB    є,I"щ╫▒Е╥?,A8ы
00000030:  15 E8 54 78 A0 91 AA FD │ DB 9F E8 FC 3B 85 17 E3   шTxаСк?█Яш№;Еу

And this header can be safely excluded from your counts... (up to 1A)
or actually removed by hacking the paq8 source.