PAQ8K

[LovePimple]

Bill Pettis has released PAQ8K2. No source code ATM.

http://ilovemyking.googlepages.com/paq8k2.zip

[Darek]

Hi!
paq8k2 version is dramaticly slow, and compression ratio is lower than paq8k. In average for my testbed compression is worse about 11%. Compression ratio is worse especially in high redundant files (up to 30%), but for low redundant (especially one case in my testbed) compression ratio could be better than paq8k and any other compressor I've been tested before.
It looks like BMP, JPG and database recognition is turned off in this version.

Detailed results. Option -5.

paq8k paq8k2 diff
0.WAV 1 413 489 1 443 986 2.2%
1.BMP 298 499 320 735 7.4%
A.TIF 859 192 902 019 5.0%
B.TGA 809 619 851 442 5.2%
C.TIF 334 877 354 255 5.8%
D.TGA 308 798 319 290 3.4%
E.TIF 498 951 497 243 -0.3%
F.JPG 95 320 110 981 16.4%
G.EXE 1 368 842 1 380 877 0.9%
H.EXE 474 979 503 174 5.9%
I.EXE 212 388 221 842 4.5%
J.EXE 42 971 43 315 0.8%
K.WAD 2 607 760 3 382 267 29.7%
L.PAK 2 810 948 3 131 021 11.4%
M.DBF 53 432 81 538 52.6%
N.ADX 85 161 92 218 8.3%
O.APR 3 882 4 353 12.1%
P.FM3 1 021 1 351 32.3%
Q.WK3 198 415 216 650 9.2%
R.DOC 28 690 31 424 9.5%
S.DOC 25 330 28 506 12.5%
T.DOC 18 097 20 037 10.7%
U.DOC 8 499 9 289 9.3%
V.DOC 18 014 20 110 11.6%
W.DOC 12 951 14 155 9.3%
X.DOC 10 882 11 774 8.2%
Y.CFG 349 399 14.3%
Z.MSG 214 225 5.1%
TOTAL 12 601 570 13 994 476 11.1%

Darek

[LovePimple]

PAQ8K2 tested by Matt.

http://www.cs.fit.edu/~mmahoney/compression/uiq/


The source code has also been released.

http://ilovemyking.googlepages.com/paq8k2_src.zip

[Matt Mahoney]

Don't expect to see paq8k2 on LTCB anytime soon. It took 9 hours to compress a 6 MB file for the generic test

I looked at the source. It takes out the word, bmp, jpeg, sparse, repeat, analog, pic, and distance models and adds 1200 randomModels, which are 32 bit contexts with random bits masked out. The other models were useful for many common file types, thus the worse compression. I think it was custom tuned for this one benchmark.

There are probably better ways to do this. uiq2 generates bit-streams with a NUL byte terminator. It might be useful to expand bits or bit pairs to bytes with a transform and also to use the offset from the last terminator as context. Well, I would need to experiment before I could say this for sure

[chornobyl]

Just tested paq8k2 on 512k binary image, the speed is impressive 99 bytes/second wow

344693 5290 bm1_6.paq8k2
343741  106 bm1_6.paq8o9
348029 3581 bm1_1.paq8k2
524288	    bm1.raw

[LovePimple]

Here's a couple of speed optimised builds for PAQ8K fans...

ENJOY!

[Skymmer]

Definitely I'm not a PAQ8k fan but its interesting to see how much boost we have. Here is small test performed on my AMD Athlon 64 4000+ (Single core) at -6 level on background07.bsp file from HL2 game.

paq8k         457.757
paq8k_lp      394.078
paq8k_lp2     393.617

Damn! 14.01% Really good speedup! Thanks! Also your compiles not only faster but support wildcards while original is not. And as the bonus piece of news... Output files are identical

[LovePimple]

Thanks for testing!

[Darek]

@LovePimple
great thanks for this version! I'm serious paq8k fan, becouse his still unbeaten general/standard compression ratio.

My scores:

0.wav
paq8k 864,36
paq8k_lp 669,72
paq8k_lp2 685,05

For this file it's 29% of speedup! I'll test other files.
Thanks again.

p.s.
And I'll reply my question for paq developers - is any chance to add paq8k model? As a "x" mark in compression method sufiix like -6x, -5x or method -m9?

[Jan Ondrus]

p.s.
And I'll reply my question for paq developers - is any chance to add paq8k model? As a "x" mark in compression method sufiix like -6x, -5x or method -m9?

I am not going to add paq8k models as a special method to paq.
Instead I made special hybrid version: paq8kx.
It is paq8px_v60 with paq8k modelling.

DIFFERENCES FROM PAQ8PX
- Replaced Statemap, APM from paq8k
- Added indirectModel2, chartModel from paq8k
- Combined contextModel2 from paq8k and paq8px
- Changed memory usage of models (to values used in paq8k)

small binary file:
HFDDCZE.CPD - 38445 bytes
HFDDCZE.CPD.paq8px_v60 - 7184 bytes
HFDDCZE.CPD.paq8k - 6739 bytes
HFDDCZE.CPD.paq8kx_v1 - 6710 bytes

dll file:
facompress.dll - 361984 bytes
facompress.dll.paq8px_v60 - 100355 bytes
facompress.dll.paq8k - 98910 bytes
facompress.dll.paq8kx_v1 - 98130 bytes

EDIT: added paq8kx_v2 (APMs will be used also for special data - images/audio/jpeg)

ppm file: (24-bit image)
m24.ppm - 36901 bytes
m24.ppm.paq8k - 19327 bytes
m24.ppm.paq8px - 17900 bytes
m24.ppm.paq8kx_v1 - 17947 bytes
m24.ppm.paq8kx_v2 - 17898 bytes

[Darek]

@Jan
Great, great thanks!
I'll test it asap when I would got compiled version - sorry I'm not an programmer, and I can't do this.

Darek

[LovePimple]

Thanks Jan!

Compiled...

[Darek]

I've tested paq8kx_v1 and paq8kx_v2 versions. In terms of compression ratio these versions are best of all compressors of my testbed scores. There are the numbers:
file paq8k paq8kx_v1 paq8kx_v2 paq8px60 size diff to paq8px size diff to paq8k compression type
0.WAV 1411566 1336338 1345062 1333973 -0.2% -5.3% wave
1.BMP 298701 264666 265349 264237 -0.2% -11.4% bmp
A.TIF 852210 500659 500839 498350 -0.5% -41.3% tiff
B.TGA 801862 459055 458729 457016 -0.4% -42.8% targa
C.TIF 335055 310220 309213 308101 -0.7% -7.4% tiff
D.TGA 308679 308135 308135 309457 0.4% -0.2% best score for all compressors x
E.TIF 498839 498765 498765 499040 0.1% 0.0% best score for all compressors x
F.JPG 95321 89843 90313 89752 -0.1% -5.7% jpg
G.EXE 1366192 1366449 1366449 1366215 0.0% 0.0% x
H.EXE 472029 471509 471509 485392 2.9% -0.1% best score for all compressors x
I.EXE 212170 211304 211304 214760 1.6% -0.4% best score for all compressors x
J.EXE 42973 42949 42949 43070 0.3% -0.1% best score for all compressors x
K.WAD 2596898 2591116 2591116 2615813 1.0% -0.2% best score for all compressors x
L.PAK 2809607 2687181 2693025 2693866 0.2% -4.4% best score for all compressors x
M.DBF 53333 52888 52888 51497 -2.6% -0.8% x
N.ADX 84904 84699 84699 85742 1.2% -0.2% best score for all compressors x
O.APR 3883 3859 3859 3852 -0.2% -0.6% x
P.FM3 1010 1017 1017 1011 -0.6% 0.7% x
Q.WK3 194372 187910 187910 206384 9.8% -3.3% best score for all compressors x
R.DOC 28685 28528 28528 28400 -0.4% -0.5% x
S.DOC 25328 25118 25118 24954 -0.7% -0.8% x
T.DOC 18098 17923 17923 17820 -0.6% -1.0% x
U.DOC 8498 8445 8445 8354 -1.1% -0.6% x
V.DOC 18013 17872 17872 17754 -0.7% -0.8% x
W.DOC 12948 12879 12879 12787 -0.7% -0.5% x
X.DOC 10883 10814 10814 10716 -0.9% -0.6% x
Y.CFG 349 349 349 320 -8.3% 0.0% x
Z.MSG 214 214 214 178 -16.8% 0.0% x
TOTAL 12562620 11590704 11605272 11648811 0.5% -7.7%
STANDARD 8767905 8629923 8635767 8697382 0.8% -1.6%
For summary:
paq8kx_v1 and v2: standard files compression even better than paq8!!!! Time of compression in average only 2.3 slower than paq8px_v60turbo mainly due to paq8k_lp 30% speedup. Great improvement!

paq8kx_v1 and v2: special data compression is unfortunately worse than paq8px_v60. Difference isn't big but is visible for v1, but for v2 is even worse. For these files (images/audio/jpeg) paq8pxV60 compression method is better.

Darek

[Darek]

Comparison table isn't look so clearly in text format, then I attached excel file with comparison table in proper shape.
Darek

[Simon Berger]

Your size diff to paq8px seems to be wrong many times. Look at the first for example. paq8px is the best there. Same for the next ones.

[Black_Fox]

If you use [CODE] tag (the # symbol when writing a message), you can preserve spaces:

without:
table a b c d e f
value 5 10 15 20 25 35

with:

table    a    b    c    d    e    f
value    5   10   15   20   25   35

[Darek]

Simon,
you have right - it's my fault. I didn't describe properly how difference is calculated.
For this calculation if the sign is "-" then compression paq8kx_v1 is worse than paq8px, and analogically if the sign is "+" then paq8kx_v1 is better than paq8px. Equation is: "paq8px_size/paq8kx_v1_size - 1" to show eventually paq8kx supremacy....
Of course if we would compare nominal sizes then equation should be reverted and sign (and only sign) in difference should be swapped form + to - and analogically form - to +.

Darek

[Darek]

Hi!
in attached file you could find comparison of compression times of new compilation of paq8k, old/original paq8k and paq8px60 for entire my testbed.

In total test new compilation - paq8k_lp is in average 30% faster than old version.
In this comparison, paq8px60 in total test (with audio/bitmap/jpg algorithms) is 176% (almost 3 times) faster.
However times calculated for standard compression files only for paq8px60 are only about 111% (2 times) faster than new paq8k compilation.

Times of paq8kx_v1/v2 are in average 17% slower than mentioned above calculation.

Great job.Darek

[Darek]

BlackFox,
thanks for this advice/tip. I'll use it in future.

Darek

[Jan Ondrus]

paq8kx_v1 and v2: special data compression is unfortunately worse than paq8px_v60. Difference isn't big but is visible for v1, but for v2 is even worse. For these files (images/audio/jpeg) paq8pxV60 compression method is better.

According to my tests old Statemap from paq8k caused this behaviour.
Here is paq8kx_v3 with Statemap from paq8px.

picture.jpg.paq8kx_v2 - 422673
picture.jpg.paq8kx_v1 - 420099
picture.jpg.paq8px - 419454
picture.jpg.paq8kx_v3 - 419007

ding.wav.paq8kx_v2 - 155067
ding.wav.paq8kx_v1 - 154388
ding.wav.paq8px - 154356
ding.wav.paq8kx_v3 - 154346

HFDDCZE.CPD.paq8px - 7184
HFDDCZE.CPD.paq8kx_v3 - 6783
HFDDCZE.CPD.paq8k - 6739
HFDDCZE.CPD.paq8kx_v1 - 6710

Unfortunatelly it seems that paq8kx_v3 shows poorer general compression.

[LovePimple]

Thanks Jan!

Compiled...

[Darek]

Thanks Jan and LovePimple.
I've tested paq8kx_v3 version. Scores are in attached file.

To sum up about scores on my testbed:

a) compression for default/standard files is much worse than paq8kx_v1, and even worse than paq8px_v60
b) compression for special(audio/graphic/jpg) files is only slightly better than paq8kx_v1 but still worse than paq8px_v60.

Hmm. At now paq8kx_v1 looks still generally the best, even if we add tradeoff from special files compression. If paq8kx_v1 algorithm would be used as an "-x" option to paq8px, then this worse compression on special files wouldn't be a serious problem.

Darek

[Matt Mahoney]

Added paq8kx_v14 to http://cs.fit.edu/~mmahoney/compression/uiq/

Compression is worse than paq8px or paq8q and slower (2572 sec, vs 1002 sec for paq8q_sse2_intel, 1012 sec for paq8px_v60_turbo).

[Rugxulo]

Added paq8kx_v14 to http://cs.fit.edu/~mmahoney/compression/uiq/

v14 ???

BTW, welcome back (from the future??).

[Jan Ondrus]

Added paq8kx_v14 to http://cs.fit.edu/~mmahoney/compression/uiq/

Compression is worse than paq8px or paq8q and slower (2572 sec, vs 1002 sec for paq8q_sse2_intel, 1012 sec for paq8px_v60_turbo).

Best version is paq8kx_v1 and should be comparable to paq8k.

First 100000 bytes from uiq compressed using -6 setting:
x.001 - 100000
x.001.paq8px - 53096
x.001.paq8kx_v3 - 53007
x.001.paq8k - 52506
x.001.paq8kx_v1 - 52415

[Matt Mahoney]

Oops, your right, should be v3.

[Darek]

My scores of paq8kx_v1 for Matt's Mahoney General Compression Benchmark are:

0.9702 for -7 option and
0.9637 for -8 option.

There are worse than paq8k, but better than any px versions.
Darek

[Darek]

Sorry, it should be Generic Compression Benchmark.
Darek

[LovePimple]

Here's a couple of speed optimised PAQ8K2 builds...

ENJOY!

[LovePimple]

These experimental PAQ8K2 builds should be even faster, but they may be unstable.

http://www.sendspace.com/file/fgs5l3