Page 2 of 2 FirstFirst 12
Results 31 to 55 of 55

Thread: ZPAQ pre-release

  1. #31
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    zpaq 0.05 updates: I changed the representation of probabilities to 15 bits in the squashed domain (linear) and 12 bits in the stretched domain with 6 bits after the decimal rather than 8. This has the effect of improving compression on highly redundant files by allowing probabilities closer to 0 and 1 to be represented. For example, a 1 MB file of all zero bytes compressed with max.cfg is 428 bytes with v0.04 and 274 bytes with v0.05. All but 35 bytes of that are the header. Compression of most other files has not changed much so don't expect big gains.

    I also constrained mixer weights to 20 bits, so it is possible to guarantee no arithmetic overflow. I tried 16 bits (which would have a fast MMX/SSE2 implementation) but it hurts compression. Unfortunately, checking bounds on mixer weights adds about 2% to overall compression time.

    I also found that constraining the weights on a MIX2 to add to 1 improves compression, so that is changed also (making it not equivalent to a MIX with 2 inputs where the weights are not constrained). It also saves some memory because you only need 1 weight per context.

    v0.04 config files should work with v0.05, but archives are not compatible (yet).

    http://cs.fit.edu/~mmahoney/compression/#zpaq

  2. #32
    Member
    Join Date
    May 2008
    Location
    Germany
    Posts
    410
    Thanks
    37
    Thanked 60 Times in 37 Posts
    thank you Matt for the new version!
    ---
    my results for my testfile with zpaq 0.05:

    - the compression works 10% faster then in zpaq 0.04

    - for min.cfg the compression-ratio is a little bit lower then in zpaq 0.04
    - for max.cfg the compression-ratio is a little bit higher then in zpaq 0.04

    good result

    but
    the testing results would be more significant, if there was the
    possibility to compress a whole directory inclusive subdirectories

    best regards

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

    zpaq czpmin.cfg ..\RESULT\tdzpaqmi ..\ORGDTA\db.dmp
    zpaq czpmax.cfg ..\RESULT\tdzpaqma ..\ORGDTA\db.dmp
    ---
    zpaq 0.03 result:

    tdzpaqmi = 136.669.356 bytes on CORE2DUO time= 290 sec
    tdzpaqma = 17.137.735 bytes on CORE2DUO time= 4920 sec
    ---
    zpaq 0.04 result:

    tdzpaqmi = 78.064.730 bytes on CORE2DUO time= 292 sec
    tdzpaqma = 15.924.959 bytes on CORE2DUO time= 6090 sec
    --
    zpaq 0.05 result:

    tdzpaqmi = 78.357.515 bytes on CORE2DUO time= 267.00 sec
    tdzpaqma = 15.866.365 bytes on CORE2DUO time= 5494.42 sec
    ---
    ---
    zpaq005 czpmin.cfg ..\RESULT\tdzpaqmi ..\ORGDTA\db.dmp
    ---
    4.264 MB memory required.
    ..\ORGDTA\db.dmp 648331264 -> 78357515
    -> 78357515
    Used 267.00 seconds
    ---
    zpaq005 czpmax.cfg ..\RESULT\tdzpaqma ..\ORGDTA\db.dmp
    ---
    278.475 MB memory required.
    ..\ORGDTA\db.dmp 648331264 -> 15866365
    -> 15866365
    1: 271/2048 (13.23%)
    2: 32098/524288 (6.12%)
    3: 1064814/4194304 (25.39%)
    4: 5495844/16777216 (32.76%)
    5: 11749831/33554432 (35.02%)
    6: 22381703/67108864 (33.35%)
    7: 23410757/67108864 (34.88%)
    8: 14290597/16777216 (85.18%)
    9: 486200/8388608 (5.80%)
    10: 5009671/33554432 (14.93%)
    11: 22521/65536 (34.36%)
    12: 24365/65536 (37.18%)
    13: 27526/65536 (42.00%)
    14: 467875/1048576 (44.62%)
    Used 5494.42 seconds
    ---

  3. #33
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    zpaq v0.06. http://cs.fit.edu/~mmahoney/compression/

    I added SHA1 checksums to detect errors. This adds 20 bytes per file, but you can use the b command (instead of a or c) to append without checksums. If the checksum is present then the decompressor will verify it, but it is optional. I used SHA1 because it is impossible to create 2 different files with the same checksum. (Well, not impossible in theory, but nobody has been able to do it). Also, SHA1 is very fast.

    Also I replaced IMIX2 with ISSE. Instead of 2 inputs (where 1 is usually CONST), it has 1 input plus a constant as a parameter. This gives more flexibility since each one can have a different fixed input without making lots of CONST components. (Although it turns out after tuning that the fixed inputs are mostly the same). The initial weights are initialized to 1/2 for the component input and 0 for the constant input. Making these tunable parameters would only help compression a few bytes so I decided to simplify it instead.

    The new max.cfg gives very slightly better compression on the Calgary corpus (about 1 KB to 645 KB), mainly due to tuning the ISSE components and replacing AVG with MIX2 with no contexts. In v0.05 I constrained the MIX2 weights to add to 1, unlike a MIX with 2 inputs.

    I may still try tuning the bit history states, and experiment with a run context model like in PAQ8 (where a context maps to the next byte and a repeat count).

  4. #34
    Member
    Join Date
    Jan 2009
    Location
    Germany
    Posts
    35
    Thanks
    0
    Thanked 0 Times in 0 Posts
    tested 0005 and 006: (and for comparison paq8o8zw, which i didnt test yet )

    Code:
    \zpaq005>zpaq cmin.cfg cna-queen.zpaq005min cna-queen.tar
    
    4.264 MB memory required.
    cna-queen.tar 22278656 -> 12136139
    -> 12136139
    Used 16.89 seconds
    
    
    \zpaq005>zpaq cmax.cfg cna-queen.zpaq005max cna-queen.tar
    
    278.475 MB memory required.
    cna-queen.tar 22278656 -> 7109647
    -> 7109647
     1: 271/2048 (13.23%)
     2: 69640/524288 (13.28%)
     3: 2617240/4194304 (62.40%)
     4: 6611697/16777216 (39.41%)
     5: 12161622/33554432 (36.24%)
     6: 22689077/67108864 (33.81%)
     7: 22494080/67108864 (33.52%)
     8: 13670456/16777216 (81.48%)
     9: 1848551/8388608 (22.04%)
    10: 8376909/33554432 (24.97%)
    11: 44707/65536 (68.22%)
    12: 44811/65536 (68.38%)
    13: 44870/65536 (68.47%)
    14: 887483/1048576 (84.64%)
    Used 341.26 seconds
    
    
    \zpaq006>zpaq amin.cfg cna-queen.tar.zpaq006min cna-queen.tar
    
    4.264 MB memory required.
    cna-queen.tar 22278656 -> 12136159
    -> 12136159
    Used 17.03 seconds
    
    
    \zpaq006>zpaq amax.cfg cna-queen.tar.zpaq006max cna-queen.tar
    
    261.697 MB memory required.
    cna-queen.tar 22278656 -> 7102343
    -> 7102343
     1: 271/2048 (13.23%)
     2: 69640/524288 (13.28%)
     3: 2617240/4194304 (62.40%)
     4: 6611697/16777216 (39.41%)
     5: 12161622/33554432 (36.24%)
     6: 22689077/67108864 (33.81%)
     7: 22494080/67108864 (33.52%)
     8: 13670456/16777216 (81.48%)
     9: 1848551/8388608 (22.04%)
    10: 8376909/33554432 (24.97%)
    11: 44707/65536 (68.22%)
    12: 44811/65536 (68.38%)
    13: 44870/65536 (68.47%)
    14: 887483/1048576 (84.64%)
    Used 340.72 seconds
    
    
    \paq8o8z-dec25-bin\bin>paq8o8zw -8 cna-queen.tar
    
    paq8o8z compiled Dec 23 2008 by OpenWatcom 1.8 for Win32 (686-tuned)
    CPUID? yes, MMX or SSE2? yes yes, using SSE2
    Creating archive cna-queen.tar.paq8o8z via level 8 with 1 file(s)...
    cna-queen.tar 22278656 -> 6377764
    22278656 -> 6377802
    Time 2928.28 sec, used 1725915622 bytes of memory

  5. #35
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    zpaq v0.07. http://cs.fit.edu/~mmahoney/compression/

    Compression is improved slightly from 645.5K to 644.7K on the Calgary corpus for max.cfg. About 0.5K comes from an improved ISSE in which the weights for the fixed input side are adjusted by a decreasing learning rate controlled by a counter rather than a constant rate controlled by an input parameter. I also removed the constant parameter. I made this change after noticing that with a learning rate you have to trade off between good compression of small files (if fast) vs large files (if slow). Now you can have it both ways.

    Another 0.3K comes from an improved bit history state table. I experimented with the 6 different tables in lpaq8, but I found that 5 made compression worse and 1 made no change. Then I started experimenting with the state table generating code in paq8o8. I found that I could decrease the number of states in the n0=0, n1=0 rows on the edges of the 2D map (because once you leave these states you can't return to them) and by doing so I could allocate more states to the rest of the map. So for n0=(0,1,2,3,4) the bounds on n1 are changed from (40,39,12,5,4) to (19,56,13,6,5) and the upper bound on n0+n1 for states having a nonempty history string was increased from 14 to 16. This allocates 255 states.

    I also tried tuning the discount() function but the gains were very small so I left it alone. (discount() decreases the count of the bit not observed. So if you observe a 1 you increment n1 and throw away some count from n0).

    I also dropped the mask parameter from SSE since there is no good reason to have it. If you have any config files from v0.06 you need to remove it, and also drop the c and rate parameters from ISSE.

    I think I have squeezed about as much as I can from the core components, so I am not anticipating any more changes that will break backward compatibility. I may experiment with a run context model (like in paq, but this will only break forward compatibility. I still intend to wait 30 days after the last break in compatibility in either direction before declaring the current implementation as standard level 1.

    I also tried compiling with g++ 4.3.7 from the Cygwin distribution. The latest version from MinGW is 3.4.5. I found that g++ 4.3.7 produces slower code by about 2 seconds (47 vs. 45 on the Calgary corpus) with -O2, and -O3 is even worse (about 51 sec). For g++ 3.4.5, -O2 and -O3 are about the same speed. Both are faster than Borland or Mars. Also, wildcards only work when compiled with MinGW.

    Lots more testing is needed first. I anticipate that most compression gains from now on will come from modeling and transforms, which means writing ZPAQL code, which means maybe discovering the need to add new instructions (breaking forward compatibility) or bugs in existing ones (breaking backward compatibility). For the Calgary corpus, the text files will benefit from a dictionary transform. The remaining files can be compressed with a custom config file for each one.

    Once I am pretty sure the spec isn't going to change, I'll write a minimal decompressor (unzpaq) that will be part of the standard. Future improvements to the compressor (like new transforms and config files) should maintain compatibility with unzpaq.

  6. #36
    Member
    Join Date
    Jan 2009
    Location
    Germany
    Posts
    35
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Using the same file:

    Code:
    \zpaq007>zpaq amax.cfg cna-queen.tar.zpaq007max cna-queen.tar
    
    261.697 MB memory required.
    cna-queen.tar 22278656 -> 7103491
    -> 7103491
     1: 271/2048 (13.23%)
     2: 69640/524288 (13.28%)
     3: 2640333/4194304 (62.95%)
     4: 6620034/16777216 (39.46%)
     5: 12170486/33554432 (36.27%)
     6: 22690778/67108864 (33.81%)
     7: 22494401/67108864 (33.52%)
     8: 13670456/16777216 (81.48%)
     9: 1848575/8388608 (22.04%)
    10: 8376982/33554432 (24.97%)
    11: 44891/65536 (68.50%)
    12: 44934/65536 (68.56%)
    13: 45177/65536 (68.93%)
    14: 888770/1048576 (84.76%)
    Used 380.14 seconds
    
    
    \zpaq007>zpaq amin.cfg cna-queen.tar.zpaq007min cna-queen.tar
    
    4.264 MB memory required.
    cna-queen.tar 22278656 -> 12136438
    -> 12136438
    Used 18.55 seconds
    better compression on max, a bit lower on min cfg.

  7. #37
    Member
    Join Date
    May 2008
    Location
    Germany
    Posts
    410
    Thanks
    37
    Thanked 60 Times in 37 Posts
    @matt - thank you for the new versions of zpaq

    my results are similar to mstar results:

    higher compression-ratio on max.cfg
    and a bit lower compression-ratio on min cfg

    ask:
    would it help to increase the ram-usage maybe to 2x or to 4x ?
    or for test-purposes half the memory for min.cfg to minimize the time ?

    my results with the Oracle-dump-file (648331264 bytes):
    --
    zpaq004min = 78.064.730 bytes on CORE2DUO time= 292 sec
    zpaq004max = 15.924.959 bytes on CORE2DUO time= 6090 sec
    --
    zpaq005min = 78.357.515 bytes on CORE2DUO time= 267.00 sec
    zpaq005max = 15.866.365 bytes on CORE2DUO time= 5494.42 sec
    --
    zpaq006min = 78.357.535 bytes on CORE2DUO time= 275.63 sec
    zpaq006max = 15.835.024 bytes on CORE2DUO time= 5772.59 sec
    --
    zpaq007min = 78.360.936 bytes on CORE2DUO time= 270.94 sec
    zpaq007max = 15.765.487 bytes on CORE2DUO time= 5924.59 sec
    ---
    --- ---
    ---
    zpaq006 czpmin.cfg ..\RESULT\tdzpqmi6 ..\ORGDTA\db.dmp

    4.264 MB memory required.
    ..\ORGDTA\db.dmp 648331264 -> 78357535
    -> 78357535
    Used 275.63 seconds
    ---
    zpaq006 czpmax6.cfg ..\RESULT\tdzpqma6 ..\ORGDTA\db.dmp

    261.697 MB memory required.
    ..\ORGDTA\db.dmp 648331264 -> 15835024
    -> 15835024
    1: 271/2048 (13.23%)
    2: 32098/524288 (6.12%)
    3: 1064814/4194304 (25.39%)
    4: 5495844/16777216 (32.76%)
    5: 11749831/33554432 (35.02%)
    6: 22381703/67108864 (33.35%)
    7: 23410757/67108864 (34.88%)
    8: 14290597/16777216 (85.18%)
    9: 486200/8388608 (5.80%)
    10: 5009671/33554432 (14.93%)
    11: 22521/65536 (34.36%)
    12: 24365/65536 (37.18%)
    13: 27526/65536 (42.00%)
    14: 467875/1048576 (44.62%)
    Used 5772.59 seconds
    ---
    zpaq007 czpmin.cfg ..\RESULT\tdzpqmi7 ..\ORGDTA\db.dmp

    4.264 MB memory required.
    ..\ORGDTA\db.dmp 648331264 -> 78360936
    -> 78360936
    Used 270.94 seconds
    ---
    zpaq007 czpmax7.cfg ..\RESULT\tdzpqma7 ..\ORGDTA\db.dmp

    261.697 MB memory required.
    ..\ORGDTA\db.dmp 648331264 -> 15765487
    -> 15765487
    1: 271/2048 (13.23%)
    2: 32098/524288 (6.12%)
    3: 1064911/4194304 (25.39%)
    4: 5500398/16777216 (32.78%)
    5: 11754895/33554432 (35.03%)
    6: 22388505/67108864 (33.36%)
    7: 23475719/67108864 (34.98%)
    8: 14290597/16777216 (85.18%)
    9: 486210/8388608 (5.80%)
    10: 5009876/33554432 (14.93%)
    11: 22901/65536 (34.94%)
    12: 24714/65536 (37.71%)
    13: 27745/65536 (42.34%)
    14: 468070/1048576 (44.64%)
    Used 5924.59 seconds
    ---

  8. #38
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    Increasing memory for big files will usually help. You can double memory usage by incrementing the sizebits parameter for all the components (except CONST and AVG which don't use memory). In particular, you can increase for ISSE, ICM, and MATCH except for low order contexts where there is no point. This should almost double memory usage:

    Code:
    comp 5 9 0 3 22 (hh hm ph pm n)
      0 const 160
      1 icm 5  (orders 0-6)
      2 isse 13 1 (sizebits j)
      3 isse 17 2
      4 isse 19 3
      5 isse 20 4
      6 isse 21 5
      7 isse 21 6
      8 match 23
      9 icm 18 (order 0 word)
      10 isse 20 9 (order 1 word)
      11 icm 10 (sparse with gaps 1-3)
      12 icm 10
      13 icm 10
      14 icm 14 (pic)
      15 mix 16 0 15 24 255 (mix orders 1 and 0)
      16 mix 8 0 16 10 255 (including last mixer)
      17 mix2 0 15 16 24 0
      18 sse 8 17 32 255 (order 0)
      19 mix2 8 17 18 16 255
      20 sse 16 19 32 255 (order 1)
      21 mix2 0 19 20 16 0
    You also probably don't need the pic model for the Calgary corpus, so this code:

    Code:
      d++ a=b a-= 212 b=a a=0 hash
        *d=a b<>a a-= 216 b<>a a=*b a&= 60 hashd (pic)
    could go, along with component 14. pic has a width of 216 bytes. What this code does is compute a hash of the byte in the row above and 2 bits of the byte in the byte 2 rows above. If your data has any kind of repeating structure like an image or fixed width table, you could use similar code to use neighboring elements as context.

    Not sure how to make min.cfg any faster. Probably an LZP preprocessor would help with highly redundant files, but I still need to write the code for it.

  9. #39
    Member
    Join Date
    Jan 2009
    Location
    Germany
    Posts
    35
    Thanks
    0
    Thanked 0 Times in 0 Posts
    i have tried your increased mem max.cfg, here are the results:
    Code:
    \zpaq007>zpaq amax.cfg cna-queen.tar.zpaq cna-queen.tar
    
    261.697 MB memory required.
    cna-queen.tar 22278656 -> 7103491
    -> 7103491
     1: 271/2048 (13.23%)
     2: 69640/524288 (13.28%)
     3: 2640333/4194304 (62.95%)
     4: 6620034/16777216 (39.46%)
     5: 12170486/33554432 (36.27%)
     6: 22690778/67108864 (33.81%)
     7: 22494401/67108864 (33.52%)
     8: 13670456/16777216 (81.48%)
     9: 1848575/8388608 (22.04%)
    10: 8376982/33554432 (24.97%)
    11: 44891/65536 (68.50%)
    12: 44934/65536 (68.56%)
    13: 45177/65536 (68.93%)
    14: 888770/1048576 (84.76%)
    Used 373.61 seconds
    
    \zpaq007>zpaq amax2.cfg cna-queen.tar.zpaq2 cna-queen.tar
    
    509.161 MB memory required.
    cna-queen.tar 22278656 -> 7093543
    -> 7093543
     1: 271/2048 (13.23%)
     2: 69640/524288 (13.28%)
     3: 5328851/8388608 (63.52%)
     4: 12803124/33554432 (38.16%)
     5: 23233098/67108864 (34.62%)
     6: 43231789/134217728 (32.21%)
     7: 43414657/134217728 (32.35%)
     8: 17149776/33554432 (51.11%)
     9: 2280745/16777216 (13.59%)
    10: 9354007/67108864 (13.94%)
    11: 44891/65536 (68.50%)
    12: 44934/65536 (68.56%)
    13: 45177/65536 (68.93%)
    14: 888770/1048576 (84.76%)
    Used 370.14 seconds
    
    \zpaq007>zpaq amax3.cfg cna-queen.tar.zpaq3 cna-queen.tar
    
    735.654 MB memory required.
    cna-queen.tar 22278656 -> 7089083
    -> 7089083
     1: 271/2048 (13.23%)
     2: 69640/524288 (13.28%)
     3: 8743705/16777216 (52.12%)
     4: 23678509/67108864 (35.28%)
     5: 42739727/134217728 (31.84%)
     6: 43231789/134217728 (32.21%)
     7: 43414657/134217728 (32.35%)
     8: 17149776/67108864 (25.56%)
     9: 2457042/33554432 (7.32%)
    10: 9574987/134217728 (7.13%)
    11: 44891/65536 (68.50%)
    12: 44934/65536 (68.56%)
    13: 45177/65536 (68.93%)
    14: 888770/1048576 (84.76%)
    Used 380.50 seconds
    the max.cfg is the default 007 version, the max2.cfg is from your last post, the max3.cfg is an one step extrapolation of max to max2.cfg:
    Code:
      0 const 160
      1 icm 5  (orders 0-6)
      2 isse 13 1 (sizebits j)
      3 isse 18 2
      4 isse 20 3
      5 isse 21 4
      6 isse 21 5
      7 isse 21 6
      8 match 24
      9 icm 19 (order 0 word)
      10 isse 21 9 (order 1 word)
      11 icm 10 (sparse with gaps 1-3)
      12 icm 10
      13 icm 10
      14 icm 14 (pic)
      15 mix 16 0 15 24 255 (mix orders 1 and 0)
      16 mix 8 0 16 10 255 (including last mixer)
      17 mix2 0 15 16 24 0
      18 sse 8 17 32 255 (order 0)
      19 mix2 8 17 18 16 255
      20 sse 16 19 32 255 (order 1)
      21 mix2 0 19 20 16 0

  10. #40
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    zpaq 0.08. http://cs.fit.edu/~mmahoney/compression/#zpaq

    Changes:
    - Added an LZP preprocessor.
    - MATCH takes 2 arguments to specify buffer and hash table sizes separately.
    - Small speed improvement (removed an array bounds check that -DNDEBUG didn't turn off).
    - Improved reporting of memory usage by component.
    - Added mid.cfg for average compression and speed.
    - Fixed memory usage reporting error.

    max.cfg compression is not changed. max.cfg and mid.cfg don't use LZP because it hurts compression. However, min.cfg improves in both speed and compression by using LZP preprocessing, for example, without LZP:

    Code:
    4.264 MB memory required.
    maxcomp\a10.jpg 842468 -> 893728
    maxcomp\acrord32.exe 3870784 -> 2033501
    maxcomp\english.dic 4067439 -> 1061318
    maxcomp\FlashMX.pdf 4526946 -> 4072755
    maxcomp\fp.log 20617071 -> 3531662
    maxcomp\mso97.dll 3782416 -> 2375928
    maxcomp\ohs.doc 4168192 -> 1406166
    maxcomp\rafale.bmp 4149414 -> 1309193
    maxcomp\vcfiu.hlp 4121418 -> 1365875
    maxcomp\world95.txt 2988578 -> 1232492
    -> 19282618
    
    Memory utilization:
     0 cm 19 5: 491520/524288 (93.75%)
    Used 33.07 seconds
    With LZP:
    Code:
    4.264 MB memory required.
    maxcomp\a10.jpg 842468 -> 894970
    maxcomp\acrord32.exe 3870784 -> 1842836
    maxcomp\english.dic 4067439 -> 932972
    maxcomp\FlashMX.pdf 4526946 -> 3948939
    maxcomp\fp.log 20617071 -> 971551
    maxcomp\mso97.dll 3782416 -> 2225611
    maxcomp\ohs.doc 4168192 -> 914956
    maxcomp\rafale.bmp 4149414 -> 1358702
    maxcomp\vcfiu.hlp 4121418 -> 908671
    maxcomp\world95.txt 2988578 -> 803096
    -> 14802304
    
    Memory utilization:
     0 cm 19 5: 491514/524288 (93.75%)
    Used 20.51 seconds
    min.cfg with LZP on is:

    Code:
    comp 3 3 18 20 1 (hh hm ph pm n)
      0 cm 19 5 (context model size=2^19, limit=5*4)
    hcomp
      *d<>a a^=*d a<<= 8 *d=a (order 2 context)
      halt
    post
      p 127 2 96 (LZP esc minlen hmul (order 3))
    end
    p = LZP. The arguments mean use 127 as an escape byte, don't code matches of length 2 or less, and use 96 as a hash multiplier (hash = hash * 96 + next_byte). ph=18 means use an index hash table of size 2^18. pm=20 means use a rotating buffer of size 2^20. To turn off LZP, replace the command after POST with "0".

    LZP decoding is done by a ZPAQL program appended to the file after the transform and before compression. The 3 LZP parameters are written into the ZPAQL program so it is properly decoded. To develop the code I first wrote the decoder in ZPAQL as a file lzp.cfg with pseudocode and comments in parenthesis with hardcoded values esc=5, minlen=3, hmul=40. I tested the code using the zpaq "h" command, then used the "s" command to output a list of bytes that I pasted into zpaq.cpp. Then I added code to overwrite the hardcoded values with the LZP parameters where they occur in the code. After testing, I could discard lzp.cfg.

    Code:
    (lzp.cfg)
    comp 3 5 18 20 1
      0 const 128
    hcomp
      (lzp: M=output buffer, H=index hash table,
            B=number of outputs, D=context hash,
            H[D]=location in M of match,
            F=last byte is escape?
    
      if F (last byte was esc?)
        if A == 0
          goto output
        else
          R0 = A+3 (count)
          C = H[D]
          do
            H[D] = B
            M[B++] = A = M[C++]
            out A
            D = hash(D, A)
          while count-- > 0
          F = 0
       else
         if (A == esc)
           F = 1
         else if A == -1 (EOS)
           F = 0
         else
           goto output
    
      output:
        H[D] = B
        M[B++] = A
        out A
        D = hash(D, A)
        F = 0
    )
    
      jf 30 (last byte was esc?)
        a> 0
          jf 37 (goto output esc)
        a+= 3 r=a 0
          c=*d
            *d=b (top of copy loop)
            a=*c *b=a b++ c++
            out
            d<>a a*= 40 a+=d d<>a
            a=r 0 a-- r=a 0
          a> 0 jt -20 (to top of copy loop)
        halt
      a== 5 jf 1
        halt
      a> 255 jf 4
        a<a halt (F=0)
    
    (output esc)
      a= 5 
    (output:)
      *d=b
      *b=a b++
      out
      d<>a a*= 40 a+=d d<>a
      halt
    
    post
      0
    end
    Next I plan to look at dictionary coding in ZPAQL.

  11. #41
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,511
    Thanks
    746
    Thanked 668 Times in 361 Posts
    > 96 as a hash multiplier

    i suggest to use 137 or 123456791

    btw, "<>" operation looks like "non-equality". may be it will be better to write it as "<=>"?

  12. #42
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    Or better use optimized multiplier. Using optimizer try 8000+ multipliers and choose the best one, as example.

  13. #43
    Member
    Join Date
    Oct 2007
    Location
    Germany, Hamburg
    Posts
    408
    Thanks
    0
    Thanked 5 Times in 5 Posts
    How is the decompression difference between the old and the new min.cfg? I don't think it will be this big.

  14. #44
    Member
    Join Date
    Oct 2007
    Location
    Germany, Hamburg
    Posts
    408
    Thanks
    0
    Thanked 5 Times in 5 Posts
    Did it myself now.
    But before the results I found a bug:
    Code:
    Won't overwrite enwik8, skipping... Decompressing enwik8 ... Checksum OK
    The file was extracted after.

    zpaq7:
    Code:
    size  - compression time - decompression time
    100000000 -> 36041583 - 49281ms  - 52687ms
    zpaq8:
    Code:
    size  - compression time - decompression time
    100000000 -> 33460947 - 37562ms - 46718ms
    Result was as expected . But nice improvement for compression anyway and it's slightly faster on decompression too. Hoping for improved script handling later . Maybe osmanturan will do.

  15. #45
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Simon Berger View Post
    ...Maybe osmanturan will do.
    After upgrading to level>1, surely i'll do
    BIT Archiver homepage: www.osmanturan.com

  16. #46
    Member
    Join Date
    Oct 2007
    Location
    Germany, Hamburg
    Posts
    408
    Thanks
    0
    Thanked 5 Times in 5 Posts
    I think you meant >= :-P

  17. #47
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    zpaq v0.09 http://cs.fit.edu/~mmahoney/compression/#zpaq

    I removed the counters that controlled learning rate from ISSE and ICM and instead initialized probability tables to (n1 + 0.5)/(n0 + n1 + 1). This results in a few percent better speed for these components and about the same compression ratio. (Some files are better, some worse).

    Also I fixed the bug where x says it won't clobber files and it does anyway.

    Anyway to answer questions:

    LZP hash multiplier should be an even number so that bits get shifted out. If you want order n hash and the hash table width is ph, then multiplier should be an odd multiple of 2^(ph/n) rounding up. In min.cfg, ph = 18 (256K hash table), hmul = 96 = 3 * 2^5, so this is an order 4 context (so my comment is wrong). The CM is order 3, so this is what you want (1 higher than the context model). Of course you can play around with these numbers. Using higher ph and pm (I recommend pm = ph + 2 for best memory efficiency) might improve compression (or might not)

    ZPAQL only allows immediate operands in the range 0...255. To write larger numbers you need to use coding tricks. For example, instead of a*= 300 you have to write a*= 150 a+=a or something. I had some instructions to make it easier to load big numbers into registers, but took them out because they were not as useful as it seemed.

    Yeah I know swap instruction <> looks like not-equal but I use C-like instructions so that would be != Anyway, ultimate goal is a high level language that compiles to ZPAQL (or maybe another language like a restricted subset of x86 that the decompressor can prove is safe). The spec doesn't say how you have to write the code.

    Anyway, min.cfg is faster and better compressing with LZP, but mid.cfg and max.cfg compress better without it.

  18. #48
    Member chornobyl's Avatar
    Join Date
    May 2008
    Location
    ua/kiev
    Posts
    153
    Thanks
    0
    Thanked 0 Times in 0 Posts
    zpaq v0.09 (level 0) removes counters from ISSE and ICM to improve speed. Not compatible with v0.09. Mar. 9, 2009.
    I hope this is typo.

  19. #49
    Member
    Join Date
    Jan 2009
    Location
    Germany
    Posts
    35
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Tested with the same 3D Data TAR:

    Code:
    \zpaq009>zpaq amin.cfg cna-queen.tar.zpaq009min cna-queen.tar
    
    4.264 MB memory required.
    cna-queen.tar 22278656 -> 10110243
    -> 10110243
    
    Memory utilization:
     0 cm 19 5: 491494/524288 (93.75%)
    Used 12.45 seconds
    
    
    \zpaq009>zpaq amid.cfg cna-queen.tar.zpaq009mid cna-queen.tar
    
    111.494 MB memory required.
    cna-queen.tar 22278656 -> 7540656
    -> 7540656
    
    Memory utilization:
     0 icm 5: 271/2048 (13.23%)
     1 isse 13 0: 69640/524288 (13.28%)
     2 isse 17 1: 5328851/8388608 (63.52%)
     3 isse 18 2: 6620034/16777216 (39.46%)
     4 isse 18 3: 6252031/16777216 (37.27%)
     5 isse 19 4: 11832860/33554432 (35.26%)
     6 match 22 24: buffer=22278657/16777216 index=3893789/4194304 (92.84%)
     7 mix 16 0 7 24 255: 456926/458752 (99.60%)
    Used 112.33 seconds
    
    
    \zpaq009>zpaq amax.cfg cna-queen.tar.zpaq009max cna-queen.tar
    
    278.474 MB memory required.
    cna-queen.tar 22278656 -> 7100136
    -> 7100136
    
    Memory utilization:
     0 const 160
     1 icm 5: 271/2048 (13.23%)
     2 isse 13 1: 69640/524288 (13.28%)
     3 isse 16 2: 2640333/4194304 (62.95%)
     4 isse 18 3: 6620034/16777216 (39.46%)
     5 isse 19 4: 12170486/33554432 (36.27%)
     6 isse 20 5: 22690778/67108864 (33.81%)
     7 isse 20 6: 22494401/67108864 (33.52%)
     8 match 22 24: buffer=22278657/16777216 index=3951117/4194304 (94.20%)
     9 icm 17: 1848575/8388608 (22.04%)
    10 isse 19 9: 8376982/33554432 (24.97%)
    11 icm 10: 44891/65536 (68.50%)
    12 icm 10: 44934/65536 (68.56%)
    13 icm 10: 45177/65536 (68.93%)
    14 icm 14: 888770/1048576 (84.76%)
    15 mix 16 0 15 24 255: 489554/983040 (49.80%)
    16 mix 8 0 16 10 255: 4080/4096 (99.61%)
    17 mix2 0 15 16 24 0: 1/1 (100.00%)
    18 sse 8 17 32 255: 8150/8192 (99.49%)
    19 mix2 8 17 18 16 255: 255/256 (99.61%)
    20 sse 16 19 32 255: 856746/2097152 (40.85%)
    21 mix2 0 19 20 16 0: 1/1 (100.00%)
    Used 311.16 seconds
    great improvement on min.cfg, nice speed improvement of max.cfg.
    [I would like a change of speed of mid.cfg to 5x slower than max and 5x faster than min, (now its ~3x faster than max and 9x slower than min.cfg) so it would feel more 'mid' ]

    Edit:

    I tried to shave off some ISSEs to get more speed:
    med.cfg:
    Code:
    (zpaq 0.08 file tuned for average compression.
    Uses 77 MB memory)
    
    comp 3 3 0 0 6 (hh hm ph pm n)
      0 icm 5
      1 isse 13 0
      2 isse 17 1
      3 isse 19 2
      4 match 22 24
      5 mix 16 0 5 24 255
    hcomp
      c++ *c=a b=c a=0 (save in rotating buffer)
      d= 1 hash *d=a
      b-- d++ hash *d=a
      b-- d++ hash *d=a
      b-- d++ hash b-- hash *d=a
      d++ a=*c a<<= 6 *d=a
      halt
    post
      (0 = pass)
      (x = E8E9, set ph=0, pm=3)
      (p esc minlen hmul = LZP, set ph>6, pm>8)
      0
    end
    resulting in:

    Code:
    \zpaq009>zpaq amed.cfg cna-queen.tar.zpaq009med cna-queen.tar
    
    77.411 MB memory required.
    cna-queen.tar 22278656 -> 7637108
    -> 7637108
    
    Memory utilization:
     0 icm 5: 271/2048 (13.23%)
     1 isse 13 0: 69640/524288 (13.28%)
     2 isse 17 1: 5328851/8388608 (63.52%)
     3 isse 19 2: 12803124/33554432 (38.16%)
     4 match 22 24: buffer=22278657/16777216 index=3668399/4194304 (87.46%)
     5 mix 16 0 5 24 255: 82873/327680 (25.29%)
    Used 83.22 seconds
    
    \zpaq009>zpaq x cna-queen.tar.zpaq009med
    
    Decompressing cna-queen.tar ... Checksum OK
    1 file(s) extracted
    Used 83.73 seconds
    Last edited by mstar; 11th March 2009 at 00:02.

  20. #50
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    zpaq 1.00. http://cs.fit.edu/~mmahoney/compression/

    This is a candidate for the standard, if I can hold off from changing the spec for 30 days At least I won't make any changes without a good reason, like major bugs.

    The standard includes a reference decoder, unzpaq1, which is part of the spec. It is a subset of the compressor, which is not part of the spec. Aside from the reference decoder, the major change is to the state tables. I didn't like having a meaningless list of numbers in the spec, so I replaced them with an algorithm for generating the table. I simplified it by removing bit history sequences longer than 1 bit, which I found didn't help much, and freed up extra states. The result is very slightly better compression on some files like the Calgary corpus and maximumcompression (but not on all files) and worse on others like enwik8.

  21. #51
    Member
    Join Date
    Jan 2009
    Location
    Germany
    Posts
    35
    Thanks
    0
    Thanked 0 Times in 0 Posts
    a run with the 3 configs:

    Code:
    \zpaq100>zpaq.exe cmin.cfg cna-queen.tar.zpaq100min cna-queen.tar
    4.264 MB memory required.
    cna-queen.tar 22278656 -> 10110243
    -> 10110243
    
    Memory utilization:
     0 cm 19 5: 491494/524288 (93.75%)
    Used 12.58 seconds
    
    
    \zpaq100>zpaq.exe cmid.cfg cna-queen.tar.zpaq100mid cna-queen.tar
    111.494 MB memory required.
    cna-queen.tar 22278656 -> 7536810
    -> 7536810
    
    Memory utilization:
     0 icm 5: 271/2048 (13.23%)
     1 isse 13 0: 69640/524288 (13.28%)
     2 isse 17 1: 5346636/8388608 (63.74%)
     3 isse 18 2: 6628851/16777216 (39.51%)
     4 isse 18 3: 6265002/16777216 (37.34%)
     5 isse 19 4: 11837071/33554432 (35.28%)
     6 match 22 24: buffer=22278657/16777216 index=3893789/4194304 (92.84%)
     7 mix 16 0 7 24 255: 456917/458752 (99.60%)
    Used 113.05 seconds
    
    
    \zpaq100>zpaq.exe cmax.cfg cna-queen.tar.zpaq100max cna-queen.tar
    278.474 MB memory required.
    cna-queen.tar 22278656 -> 7097460
    -> 7097460
    
    Memory utilization:
     0 const 160
     1 icm 5: 271/2048 (13.23%)
     2 isse 13 1: 69640/524288 (13.28%)
     3 isse 16 2: 2686155/4194304 (64.04%)
     4 isse 18 3: 6628851/16777216 (39.51%)
     5 isse 19 4: 12177985/33554432 (36.29%)
     6 isse 20 5: 22692103/67108864 (33.81%)
     7 isse 20 6: 22494605/67108864 (33.52%)
     8 match 22 24: buffer=22278657/16777216 index=3951117/4194304 (94.20%)
     9 icm 17: 1848575/8388608 (22.04%)
    10 isse 19 9: 8377000/33554432 (24.97%)
    11 icm 10: 45111/65536 (68.83%)
    12 icm 10: 45226/65536 (69.01%)
    13 icm 10: 45389/65536 (69.26%)
    14 icm 14: 890167/1048576 (84.89%)
    15 mix 16 0 15 24 255: 489560/983040 (49.80%)
    16 mix 8 0 16 10 255: 4080/4096 (99.61%)
    17 mix2 0 15 16 24 0: 1/1 (100.00%)
    18 sse 8 17 32 255: 8151/8192 (99.50%)
    19 mix2 8 17 18 16 255: 255/256 (99.61%)
    20 sse 16 19 32 255: 856952/2097152 (40.86%)
    21 mix2 0 19 20 16 0: 1/1 (100.00%)
    Used 310.86 seconds

  22. #52
    Member
    Join Date
    Feb 2009
    Location
    Cicero, NY
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Here are some settings and outputs from zpaq 0.09 I have achieved through some tests. I coded a small matlab file which optimizes the configurable parts of the config, I just let this run for a while to see what it outputs.

    enwik8
    Code:
    1946.037 MB memory required.
    enwik8 100000000 -> 18909482
    -> 18909482
    
    Memory utilization:
     0 const 159
     1 icm 5: 236/2048 (11.52%)
     2 isse 12 1: 27015/262144 (10.31%)
     3 isse 17 2: 689524/8388608 (8.22%)
     4 isse 21 3: 4984269/134217728 (3.71%)
     5 isse 22 4: 18569235/268435456 (6.92%)
     6 isse 22 5: 44389997/268435456 (16.54%)
     7 isse 23 6: 124309600/536870912 (23.15%)
     8 match 26 25: buffer=100000001/33554432 index=16377721/67108864 (24.40%)
     9 icm 21: 9962007/134217728 (7.42%)
    10 isse 22 9: 89792300/268435456 (33.45%)
    11 icm 11: 33762/131072 (25.76%)
    12 icm 11: 36289/131072 (27.69%)
    13 icm 12: 38269/262144 (14.60%)
    14 icm 1: 84/128 (65.63%)
    15 mix 17 0 14 7 255: 342201/1835008 (18.65%)
    16 mix 8 0 15 55 255: 3311/3840 (86.22%)
    17 mix2 0 15 16 146 0: 1/1 (100.00%)
    18 sse 8 16 9 255: 6201/8192 (75.70%)
    19 mix2 9 17 18 36 255: 218/512 (42.58%)
    20 sse 17 19 4 255: 269163/4194304 (6.42%)
    21 mix2 0 19 20 41 0: 1/1 (100.00%)
    Used 945.09 seconds

    enwik8 Pre-Processed with XWRT
    I used this XWRT 3.2 command line:
    xwrt.exe -3 -b255 -m255 -s -f64 enwik8
    Code:
    1946.037 MB memory required.
    enwik8_3.xwrt 59861805 -> 18496115
    -> 18496115
    
    Memory utilization:
     0 const 159
     1 icm 5: 271/2048 (13.23%)
     2 isse 12 1: 68334/262144 (26.07%)
     3 isse 17 2: 2467379/8388608 (29.41%)
     4 isse 21 3: 13724993/134217728 (10.23%)
     5 isse 22 4: 43563074/268435456 (16.23%)
     6 isse 22 5: 83346381/268435456 (31.05%)
     7 isse 23 6: 171665423/536870912 (31.98%)
     8 match 26 25: buffer=59861806/33554432 index=26614448/67108864 (39.66%)
     9 icm 21: 9715179/134217728 (7.24%)
    10 isse 22 9: 73157630/268435456 (27.25%)
    11 icm 11: 67508/131072 (51.50%)
    12 icm 11: 67644/131072 (51.61%)
    13 icm 12: 69584/262144 (26.54%)
    14 icm 1: 84/128 (65.63%)
    15 mix 17 0 14 7 255: 852968/1835008 (46.48%)
    16 mix 8 0 15 55 255: 3824/3840 (99.58%)
    17 mix2 0 15 16 146 0: 1/1 (100.00%)
    18 sse 8 16 9 255: 7575/8192 (92.47%)
    19 mix2 9 17 18 36 255: 255/512 (49.80%)
    20 sse 17 19 4 255: 516228/4194304 (12.31%)
    21 mix2 0 19 20 41 0: 1/1 (100.00%)
    Used 566.09 seconds
    Calgary Corpus Fileset
    Code:
    1498.996 MB memory required.
    cc\bib 111261 -> 23053
    cc\book1 768771 -> 198454
    cc\book2 610856 -> 123774
    cc\geo 102400 -> 46635
    cc\news 377109 -> 90637
    cc\obj1 21504 -> 8685
    cc\obj2 246814 -> 55967
    cc\paper1 53161 -> 11161
    cc\paper2 82199 -> 17109
    cc\pic 513216 -> 28448
    cc\progc 39611 -> 9099
    cc\progl 71646 -> 11024
    cc\progp 49379 -> 7933
    cc\trans 93695 -> 11548
    -> 643527
    
    Memory utilization:
     0 const 159
     1 icm 5: 271/2048 (13.23%)
     2 isse 8 1: 10718/16384 (65.42%)
     3 isse 13 2: 250986/524288 (47.87%)
     4 isse 21 3: 2084845/134217728 (1.55%)
     5 isse 21 4: 4188978/134217728 (3.12%)
     6 isse 22 5: 6517457/268435456 (2.43%)
     7 isse 22 6: 11895686/268435456 (4.43%)
     8 match 26 19: buffer=3141623/524288 index=1355829/67108864 (2.02%)
     9 icm 21: 745778/134217728 (0.56%)
    10 isse 22 9: 7705659/268435456 (2.87%)
    11 icm 11: 45385/131072 (34.63%)
    12 icm 9: 23746/32768 (72.47%)
    13 icm 12: 61158/262144 (23.33%)
    14 icm 12: 184556/262144 (70.40%)
    15 mix 16 0 15 17 255: 431965/983040 (43.94%)
    16 mix 7 0 16 18 255: 2048/2048 (100.00%)
    17 mix2 0 15 16 48 0: 1/1 (100.00%)
    18 sse 8 17 21 255: 6059/8192 (73.96%)
    19 mix2 9 17 18 50 255: 254/512 (49.61%)
    20 sse 17 19 3 255: 288433/4194304 (6.88%)
    21 mix2 8 19 20 28 0: 1/256 (0.39%)
    Used 28.44 seconds
    Last edited by russelms; 20th March 2009 at 20:45.

  23. #53
    Member
    Join Date
    Mar 2009
    Location
    Prague, CZ
    Posts
    60
    Thanks
    27
    Thanked 6 Times in 6 Posts
    here is config using ~2GB RAM, optimized on 350MB testset of well compressible non-text data. MAybe usefull for somebody.

    comp 5 9 0 3 22 (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 isse 21 3
    5 isse 22 4
    6 isse 23 5
    7 isse 23 6
    8 match 25 28
    9 icm 18 (order 0 word)
    10 isse 20 9 (order 1 word)
    11 icm 10 (sparse with gaps 1-3)
    12 icm 10
    13 icm 10
    14 icm 14 (pic)
    15 mix 17 0 15 24 255 (mix orders 1 and 0)
    16 mix 8 0 16 10 255 (including last mixer)
    17 mix2 0 15 16 24 0
    18 sse 8 17 32 255 (order 0)
    19 mix2 8 17 18 16 255
    20 sse 17 19 32 255 (order 1)
    21 mix2 0 19 20 16 0

  24. #54
    Member
    Join Date
    Feb 2009
    Location
    Cicero, NY
    Posts
    9
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Matt when I run zpaq 1.00 with the v flag for verbose output it doesn't appear to register it correctly, shifting all of the input commands?

    zpaq.exe v cconfig_test.cfg enwik8_small.zpaq enwik8 <- The v here shifts all the statements

    therefore I just throw it at the end of the command line so it creates an error and I get the verbose output.

    zpaq.exe cconfig_test.cfg enwik8_small.zpaq enwik8 v

  25. #55
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    The config file is only used for compression. To list the contents, use one of:

    zpaq l archive
    zpaq v archive

Page 2 of 2 FirstFirst 12

Similar Threads

  1. zpaq updates
    By Matt Mahoney in forum Data Compression
    Replies: 2527
    Last Post: 4th May 2019, 13:33
  2. ZPAQ 1.05 preview
    By Matt Mahoney in forum Data Compression
    Replies: 11
    Last Post: 30th September 2009, 05:26
  3. zpaq 1.02 update
    By Matt Mahoney in forum Data Compression
    Replies: 11
    Last Post: 10th July 2009, 01:55
  4. FreeArc 0.40 pre-release version
    By Bulat Ziganshin in forum Forum Archive
    Replies: 110
    Last Post: 3rd January 2008, 00:29
  5. quad 1.07BETA2 - pre-release of 1.08 available
    By encode in forum Forum Archive
    Replies: 4
    Last Post: 11th March 2007, 23:59

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •