Transformation for UIQ2

[Matt Mahoney]

Sorry, fixed. http://mattmahoney.net/dc/uiq/

[pat357]

Some more scores :

UIQ2 1
UIQ2_t4b e 1 o1 o2
Ratio = (o1 packed  +   1184009) /  3008492			

			o1 packed	o2		1.pmm		ratio
o1.paq8pf  -8		1,456,374	1,184,009	3,008,492	0.8776
o1_bliz.bliz    	1,457,311					0.8780
o1_bcm9.bcm     	1,459,999					0.8788
o1_nz7.nz  -cc -m1.4g	1,461,544					0.8794
o1_paq9a_9.paq9a	1,464,802					0.8804
o1_paq9a_5.paq9a	1,464,869					0.8805
o1_nz7 -cO -m50m	1,480,140					0.8855
o1.pmm (default)	1,488,291					0.8883
o1 7z_ppmd_o6.7z	1,538,741					0.9050
o1_uha_mx.uha   	1,545,940					0.9074
o1.7z   lzma  		1,752,840					0.9762
o1  (unpacked)       	3,000,000

I was surprised by the good scores from BCM v0.09 and BLIZ v0.24.
These, together with Nanozip, come very close to PAQ8 and are order of magnitudes faster !

[Jan Ondrus]

o1 ... 3000000 bytes
zpaq.exe cmax.cfg (278 MB) -> 1452086 bytes
zpaq.exe cmax_o1.cfg (14.6 MB) -> 1454493 bytes

cmax_o1.cfg:

comp 5 9 0 3 12 (hh hm ph pm n)
  0 const 160
  1 icm 5  (orders 0-6)
  2 isse 13 1 (sizebits j)
  3 isse 16 2
  4 icm 10 (sparse with gap 1)
  5 mix 16 0 5 24 255 (mix orders 1 and 0)
  6 mix 8 0 6 10 255 (including last mixer)
  7 mix2 0 5 6 24 0
  8 sse 8 7 32 255 (order 0)
  9 mix2 8 7 8 16 255
  10 sse 16 9 32 255 (order 1)
  11 mix2 0 9 10 16 0
hcomp
  c++ *c=a b=c a=0 (save in rotating buffer)
  d= 2 hash *d=a b-- (orders 1,2)
  d++ hash *d=a b--
  d++ b=c b-- a=0 hash *d=a (sparse)
  d++ a=*c a<<= 8 *d=a (mix)
  d++ d++ d++ d++
  d++ *d=a (sse)
  halt
post
  0
end

=> only 5 models are the most important for compression of this file (const, order0, order1, order2, sparse1)

[Shelwien]

@pat357: If bliz and bcm show good results... can you also test bwtmix then?
http://ctxmodel.net/files/mix_test/BWTmix_v1.rar

Also, does anybody verify decodability here?

[pat357]

@pat357: If bliz and bcm show good results... can you also test bwtmix then?
http://ctxmodel.net/files/mix_test/BWTmix_v1.rar

Updated with a few more packers/archivers :

UIQ2_t4b e 1 o1 o2

	(o1 packed  +   1184009) /  3008492			

			o1 packed	o2		1.pmm		ratio
o1  (unpacked)       	3,000,000	1,184,009	3,008,492	1.3907
o1.7z   lzma  		1,752,840	1,184,009	3,008,492	0.9762
o1_uha_mx.uha   	1,545,940	1,184,009	3,008,492	0.9074
o1 7z_ppmd_o6.7z	1,538,741	1,184,009	3,008,492	0.9050
o1_grzip_b3m_m3_a_p	1,505,121	1,184,009	3,008,492	0.8938
o1.pmm (default)	1,488,291	1,184,009	3,008,492	0.8883
o1_nz7 -cO -m50m	1,480,140	1,184,009	3,008,492	0.8855
o1_paq9a_5.paq9a	1,464,869	1,184,009	3,008,492	0.8805
o1_paq9a_9.paq9a	1,464,802	1,184,009	3,008,492	0.8804
o1_nz7.nz  -cc -m1.4g	1,461,544	1,184,009	3,008,492	0.8794
o1_bcm9.bcm     	1,459,999	1,184,009	3,008,492	0.8788
o1_bliz.bliz    	1,457,311	1,184,009	3,008,492	0.8780
o1.paq8pf  -8		1,456,374	1,184,009	3,008,492	0.8776
bbb  -cfk3000		1,456,005	1,184,009	3,008,492	0.8775
BWTMix v1		1,455,947	1,184,009	3,008,492	0.8775
Paq8px_64 -8		1,454,348	1,184,009	3,008,492	0.8770
BWTmix v0		1,456,481	1,184,009	3,008,492	0.8777

It looks that Bwtmonstr might beat Paq8 !!

[pat357]

Also, does anybody verify decodability here?

I checked it for the filter : uiq2_t4b is ok , previous versions were NOT OK !
(could not restore back to UIQ2 )

[Matt Mahoney]

Thanks for testing pat357. I have updated results http://mattmahoney.net/dc/uiq/

Also, I modified max_o1.cfg and improved compression to 0.8763. I added offset mod 3 to all contexts, replaced ICM/ISSE with CM 255 because the source is stationary, then tuned everything. max_o2.cfg is linked from above.

[Darek]

@pat357: if you would compress o2 file too, then you could tune your scores a little bit again.

Darek

[Matt Mahoney]

o2 is nearly random. I compressed both files, but the difference is after the 4th decimal place.

[Darek]

Yeah... for my testbed is a difference of packed or unpacked t4 is about 1/1000 - it changes the score.

For t3 or t2 versions differences were 3 or 4/1000 and it were worth to compress.

Darek

[pat357]

I added a few compressors/archivers to my score table :

UIQ2_t4b e 1 o1 o2	(o1 packed  +   1184009) /  3008492			

			o1 packed	o2		1.pmm		ratio
o1  (unpacked)       	3,000,000	1,184,009	3,008,492	1.3907
7z  lzma (ultra)  	1,752,840	1,184,009	3,008,492	0.9762
7z BZIP2 (ultra)	1,669,011	1,184,009	3,008,492	0.9483
RZM v0.07h		1,625,776	1,184,009	3,008,492	0.9340
uha_mx			1,545,940	1,184,009	3,008,492	0.9074
7z ppmd_o6 m512mb	1,538,741	1,184,009	3,008,492	0.9050
ASH v0.7o6 m1024	1,535,459	1,184,009	3,008,492	0.9039
CCMx v130c -7		1,518,419	1,184,009	3,008,492	0.8983
CCMx v126b -7		1,515,689	1,184,009	3,008,492	0.8974
7z ppmd o2 m12mb	1,513,638	1,184,009	3,008,492	0.8967
grzip_b3m_m3_a_p	1,505,121	1,184,009	3,008,492	0.8938
rings15c_9		1,497,256	1,184,009	3,008,492	0.8912
WinRK 3.1.2 (b. assym)	1,494,885	1,184,009	3,008,492	0.8904
Dark 0.51 p-b3m 	1,493,730	1,184,009	3,008,492	0.8901
slim v0.23_o6_m300	1,489,569	1,184,009	3,008,492	0.8887
ppmonster vJ (256m)	1,488,291	1,184,009	3,008,492	0.8883
bit07_p5		1,483,340	1,184,009	3,008,492	0.8866
nz7 -cO -m50m		1,480,140	1,184,009	3,008,492	0.8855
UHBC v1.0 -b3m -m3	1,478,060	1,184,009	3,008,492	0.8849
m99_3m_m (m99 v2.21)	1,474,473	1,184,009	3,008,492	0.8837
CMM v0.2b -47		1,474,390	1,184,009	3,008,492	0.8836
WinRK 3.1.2 (high)	1,471,764	1,184,009	3,008,492	0.8828
BWT + o19f (shelwien)	1,467,986	1,184,009	3,008,492	0.8815
BWT + o2rc (shelwien)	1,466,420	1,184,009	3,008,492	0.8810
paq9a_5			1,464,869	1,184,009	3,008,492	0.8805
paq9a_9			1,464,802	1,184,009	3,008,492	0.8804
bcm08_e3		1,462,349	1,184,009	3,008,492	0.8796
nz07 -cc -m1.4g		1,461,544	1,184,009	3,008,492	0.8794
WinRK 3.1.2 (PWCM)	1,460,566	1,184,009	3,008,492	0.8790
bcm009 3mb    		1,459,999	1,184,009	3,008,492	0.8788
bliz 0.24 3mb    	1,457,311	1,184,009	3,008,492	0.8780
BWTmix v0		1,456,481	1,184,009	3,008,492	0.8777
paq8pf  -8		1,456,374	1,184,009	3,008,492	0.8776
bbb  -cfk3000		1,456,005	1,184,009	3,008,492	0.8775
BWTMix v1		1,455,947	1,184,009	3,008,492	0.8775
lpaq8_9			1,455,935	1,184,009	3,008,492	0.8775
Paq8px_64 -8		1,454,348	1,183,710	3,008,492	0.8769
BWMonstr v0.02		1,452,229	1,183,670	3,008,492	0.8762
zpaq 1.03 cmax_o2	1,449,337	1,184,009	3,008,492	0.8753
zpaq 1.03 cmax_o2_msr	1,449,218	1,183,315	3,008,492	0.8750

-edit-
Added following compressors/configs :

zpaq 1.03 cmax_o2_msr
BWMonstr v0.02
CCMx v130c
CCMx v126b
CMM v0.2b
rings15c
BWT + o19f (shelwien)
BWT + o2rc (shelwien)

[russelms]

Hey,

I ran some iterations on max_o2.cfg and came up with a modified version which on my machine provided equivalent or slightly better compression of o1 using less memory.

Running max_o2_MSR.cfg on my machine:

o1 = 3000000 -> 1449342 using 72.198 MB in 8.22 sec.
o2 = 1184821 -> 1184134 using 72.198 MB in 3.65 sec.
ppm = 3005994

(o1+o2)/ppm = (1449342+1184134) / 3005994 = .8761

Thanks,

Mike

[pat357]

Hey,

I ran some iterations on max_o2.cfg and came up with a modified version which on my machine provided equivalent or slightly better compression of o1 using less memory.

Running max_o2_MSR.cfg on my machine:

Tested it on my system :

zpaq 1.03 cmax_o2_msr	1,449,218	1,183,315	3,008,492	0.8750

Congrats ! This appears to be the best score I have seen (with only 72 MB RAM !!)
I wonder why your own score is actually a tad worse ( last 2 digits are different...)

[schnaader]

I wonder why your own score is actually a tad worse ( last 2 digits are different...)

I think that's a result of the transform. Have a look at the numbers, in your test both files were compressed a bit better using zpaq and to make it even worse, ppm size is 2498 bytes larger.

Perhaps this statement on Matt's UIQ page describes it the best:

Generally, the two compressors should have about the same capability. ppmonstr was chosen to improve the accuracy of high end compressors.

Using the transform, we've "taken the next step" and have a big advantage over ppmonstr alone - so the average error is bigger now.

There are two possibilities to get more exact values again:
First we could compare with uiq2_t4b + ppmonstr instead of just ppmonstr, but this would mean we couldn't compare to old results.
The other (much better) choice would be to use more output strings (or average the result for multiple files) - this would only take more time to benchmark, but give more exact ratios again that would still be comparable with old ratios.

[pat357]

There are two possibilities to get more exact values again:
First we could compare with uiq2_t4b + ppmonstr instead of just ppmonstr, but this would mean we couldn't compare to old results.

Another problem with this is that it would not make the "variances" smaller,
as the correlation between these scores and the current UIQ2_t4b scores is
just a multiplication by a constant (= 1/0.8883).
IIRC, the variances would become even larger by this factor.

The other (much better) choice would be to use more output strings (or average the result for multiple files) - this would only take more time to benchmark, but give more exact ratios again that would still be comparable with old ratios.

I did a small experiment with different sizes from the UIQ2 output file :

UIQ2 Xm aaaa X000000  (X = 1,2,4,8)

		Xm		Xm.pmm		o1		o2		"Xm.pmm/Xm"
UIQ2 1m		6,517,232	3,008,492	3,000,000	1,184,009	0.4616
UIQ2 2m		13,038,765	5,896,000	6,000,000	2,364,868	0.4522
UIQ2 4m		26,078,539	11,627,194	12,000,000	4,732,352	0.4459
UIQ2 8m		52,148,809	23,017,814	24,000,000	9,464,701	0.4414
					
					
			1m_o1		2m_o1		4m_o1		8m_o1	
o1.zpaq (max_o2_msr)	1,449,218	2,894,289	5,785,534	11,562,897	
o1.zpaq / o1		0.4831		0.4824		0.4821		0.4818	
ratio UIQ2 score	0.8753		0.8920		0.9046		0.9135	
					
BCM v0.09		1,459,999	2,914,732	5,824,808	11,639,440	
o1.bcm / o1		0.4867		0.4858		0.4854		0.4850	
ratio UIQ2 score	0.8788		0.8955		0.9080		0.9169	
					
LPAQ8 9			1,455,935	2,906,580	5,808,992	11,609,015	
o1.lpaq8/ o1		0.4853		0.4844		0.4841		0.4837	
ratio UIQ2 score	0.8775		0.8941		0.9066		0.9155

As you can see, the ratio Xm/Xm.pmm becomes smaller as the files become larger : PPMonstr gives a better ratio on the larger files.

I tested 3 other compression pgms : ZPAQ 1.03 , BCM v0.09 and LPAQ8.
As you can see, the ratio for compressing O1 compared to the original O1 remains almost constant.
The size from O1 has little impact on the ratio.

This obviously means that the UIQ2 score will become worse for larger UIQ2 output files.
The UIQ2 score depends from the file size generated by UIQ2 !!

[Matt Mahoney]

I tested uiq2_t4b|zpaq cmax_o2_msr.cfg 10 times with an average 0.8760 and range 0.8751 to 0.8763 using seeds "1" through "10". The values were .8758, .8763, .8761, .8762, .8751, .8760, .8763, .8762, .8760. For the test I compressed both outputs of uiq2_t4b into a single zpaq archive. This is about 200 bytes smaller (or .00007) than not compressing o2. The test script is:

uiq2 x%1 %1
uiq2_t4b e x%1 o1 o2
zpaq cmax_o2_msr.cfg x%1.zp o1 o2
ppmonstr e x%1
dir x%1*

where %1 is "1", "2", ... "10".

[schnaader]

As you can see, the ratio Xm/Xm.pmm becomes smaller as the files become larger : PPMonstr gives a better ratio on the larger files.

I tested 3 other compression pgms : ZPAQ 1.03 , BCM v0.09 and LPAQ8.
As you can see, the ratio for compressing O1 compared to the original O1 remains almost constant.
The size from O1 has little impact on the ratio.

This obviously means that the UIQ2 score will become worse for larger UIQ2 output files.
The UIQ2 score depends from the file size generated by UIQ2 !!

Damn, that makes so much sense, but I haven't thought of that - thanks for those tests! In that case, the only real way is to get the ratio for multiple files and average it (like Matt just did).

[Jan Ondrus]

There was hard coded parameter in previous versions of uiq2_t.
You can change it in uiq2_t5:
Default value is 10 which should produce same results as uiq2_t4b version.

example:

uiq2_t5.exe e uiq2 o1 o2 256
-> o1(3000000 bytes) -> o1.zpaq(814091 bytes)
-> o2 (4966847 bytes) -> o2.zpaq (2613820 bytes)
total size = 3427911 bytes

uiq2_t5.exe e uiq2 o1 o2 10 (= uiq2_t5.exe e uiq2 o1 o2)
-> o1(3000000 bytes) -> o1.zpaq(1452086 bytes)
-> o2 (1182816 bytes) -> o2.zpaq (1182248 bytes)
total size = 2634334 bytes

uiq2_t5.exe e uiq2 o1 o2 0
-> o1(3000000 bytes) -> o1.zpaq(1667189 bytes)
-> o2 (1026993 bytes) -> o2.zpaq (1024167 bytes)
total size = 2691356 bytes

[Matt Mahoney]

I confirmed that the default parameter 10 gives the best compression with zpaq cmax_o2.cfg.

Edit: and also zpaq cmax_o2_msr.cfg.

[Jan Ondrus]

I managed to rewrite inverse of uiq2_t transformation in ZPAQL (uiq2_t6.cfg).
Output files o1 and o2 files are concatenated into one output file here.

a> 255 ifl a= 0 r=a 0 a= 3 a*= 100 a*= 100 a*= 100 a-- r=a 1 a= 0
r=a 2 do c=r 0 d=*c a=c a++ r=a 0 a=d r=a 3 c=r 0 b=*c a=c a++ r=a
0 a= 255 a-=b r=a 4 c=r 0 b=*c a=c a++ r=a 0 a=b a> 0 if a+= 222
a%= 255 a+= 1 a-=d endif r=a 5 a=r 3 a> 1 if c= 0 a=r 3 b=a b-- a=r 4
a> 0 if b-- endif a=c a<b if do a=r 2 d=a b=r 1 a== 0 if b++ endif
a=b r=a 1 a=d a++ a%= 8 r=a 2 b=*b a= 7 a-=d d=a a=b a>>=d a&= 1
d=c *d=a c++ a=r 3 b=a b-- a=r 4 a> 0 if b-- endif a=c a<b while
endif a=r 4 a> 0 if b=a a&= 127 r=a 4 a=b a&= 128 a== 0 ifnot a= 1
endif d=c *d=a endif endif a=r 4 a== 0 if a=r 3 a> 0 if d=a d--
a= 1 *d=a endif else b=r 3 a=b c=r 5 a+=c a-- b=r 4 c=r 3 a<c ifnot
do a-=b a<c until endif b=a c-- a=c a>b if do d=c d-- a=*d d++
*d=a c-- a=c a>b while endif a= 1 d=c *d=a endif a=r 5 c=a a=c
a> 0 if do a=r 5 a-=c b=r 3 a+=b b=r 4 a-=b d=a b=*d a=r 4 a+=d
d=a *d=b c-- a=c a> 0 while endif a=r 3 b=a a=r 5 a+=b r=a 3 a=r 3
a+= 7 a%= 8 b=a a= 15 a-=b b=a d=r 3 a=b a> 0 if do a= 0 *d=a d++
b-- a=b a> 0 while endif a=d r=a 3 b=r 3 d= 0 do c=*d a=r 7 a&= 127
a*= 2 a+=c r=a 7 c=a a=r 6 a++ a%= 8 r=a 6 a== 0 if a=c out endif
d++ a=d a<b while a= 3 a*= 100 a*= 100 a*= 100 c=a a=r 0 a<c while
c= 0 halt else *c=a c++ halt endif