Page 1 of 2 12 LastLast
Results 1 to 30 of 52

Thread: paq8p3

  1. #1
    Member
    Join Date
    May 2008
    Location
    Estonia
    Posts
    406
    Thanks
    155
    Thanked 235 Times in 127 Posts

    Post paq8p3

    DIFFERENCES FROM PAQ8P1
    splited sparseModel to sparseTextModel and sparseModel
    display output size in real time
    jpeg model from paq8p2
    modified word model, bmp model, model1bit
    model long matches directly after normal model
    other small tunes

    Code:
    paq8p1 -7 FP.LOG 20617071 -> 260068 2308.10 sec 8,7 KB/s
    paq8p3 -7 FP.LOG 20617071 -> 261979 1515.79 sec 13,2 KB/s
    paq8p1 -7 calgary.tar 3152896 -> 602021 325.28 sec 9,4 KB/s
    paq8p3 -7 calgary.tar 3152896 -> 603739 234.91 sec 13,1 KB/s
    paq8p1 -7 english.dic 4067439 -> 387435 419.73 sec 9,4 KB/s
    paq8p3 -7 english.dic 4067439 -> 389814 269.56 sec 14,7 KB/s
    paq8p1 -7 AcroRd32.exe 3870784 -> 922817 349.79 sec 10,8 KB/s
    paq8p3 -7 AcroRd32.exe 3870784 -> 920481 332.24 sec 11,3 KB/s
    Speed came form removing sparse model from text compression.
    Look at diff and you see what has been done.


    Only source. This is test version.
    http://paq8.googlecode.com/svn/trunk/paq8p3.cpp

    Had some free time to throw dices.

    Comments...
    KZo


  2. #2
    Member
    Join Date
    Aug 2008
    Location
    Saint Petersburg, Russia
    Posts
    215
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Insane speed improvements for paq8 considering the compression ratio loss this slight! Great job!

  3. #3
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts

    Thumbs up

    Thanks Kaitz!

    Compiled...

    EDIT: Attachment "paq8p3_kaitz_test_version.zip" removed. Download the latest version here.

  4. #4
    Member
    Join Date
    Oct 2007
    Location
    Germany, Hamburg
    Posts
    408
    Thanks
    0
    Thanked 5 Times in 5 Posts
    Very very nice speed improvement on text files for this small compression loss. On executables speed and compression improvement. Impressive!
    Are there any worse results in your tests?

  5. #5
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Why did not anyone add M1's context masks to PAQ8 variants as additional sparse context models? This would surely improve compression. Because they are locally optimal (in M1's architecture). And this should be true for PAQ8 too.
    BIT Archiver homepage: www.osmanturan.com

  6. #6
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    Some benchmarks. I noticed that memory usage is also reduced.
    http://cs.fit.edu/~mmahoney/compression/uiq/
    Compression time was 735 sec for 6.5 MB.

  7. #7
    Member
    Join Date
    May 2008
    Location
    Estonia
    Posts
    406
    Thanks
    155
    Thanked 235 Times in 127 Posts

    Post

    Quote Originally Posted by Simon Berger View Post
    Very very nice speed improvement on text files for this small compression loss. On executables speed and compression improvement. Impressive!
    Are there any worse results in your tests?
    Did not test that hard.

    Running enwik8 for speed test now.
    KZo


  8. #8
    Member
    Join Date
    May 2008
    Location
    Estonia
    Posts
    406
    Thanks
    155
    Thanked 235 Times in 127 Posts

    Post

    Quote Originally Posted by Matt Mahoney View Post
    Some benchmarks. I noticed that memory usage is also reduced.
    http://cs.fit.edu/~mmahoney/compression/uiq/
    Compression time was 735 sec for 6.5 MB.
    Memory usage is low only if one type of data is proccesed. If exe type data then it is small reduction (text,binary,bmp,jpg etc).
    I think.

    uip data is default (unkn).
    KZo


  9. #9
    Member
    Join Date
    May 2008
    Location
    Germany
    Posts
    410
    Thanks
    37
    Thanked 60 Times in 37 Posts
    @kaitz + @lovepimple

    yesterday i have tested paq8p3_speed

    one word: great!

    wonderful compression!

    what about to implement such strong compression into a program like paqzip

    that means to combine it with a well-knowed archiv-format?

    best regards

  10. #10
    Member
    Join Date
    Oct 2007
    Location
    Germany, Hamburg
    Posts
    408
    Thanks
    0
    Thanked 5 Times in 5 Posts
    One general question. Could there a support for bmp's with a version 2 header easily be implemented? The reason is to support better compression of image data where only a simple bmp header could be added, that would be really good because of much less overhead. 14 vs 40 byte second header and one byte less for every entry of the color map.

  11. #11
    Member
    Join Date
    May 2008
    Location
    Estonia
    Posts
    406
    Thanks
    155
    Thanked 235 Times in 127 Posts

    Post

    Code:
    G:\svn\PAQ8\trunk>paq8p3_speed_optimised -7 G:\svn\PAQ8\trunk\enwik8
    Creating archive G:\svn\PAQ8\trunk\enwik8.paq8p3 with 1 file(s)...
    G:/svn/PAQ8/trunk/enwik8 100000000 -> 18044198     (    18044175)
    100000000 -> 18044229
    Time 7264.56 sec, used 803406033 bytes of memory
    
    Type    Size            Parts
    unkn    214             10
    utf8    99999786                11
    Total parts: 21, fragmentation cost 105 bytes
    
    G:\svn\PAQ8\trunk>paq8p1.exe -7 G:\svn\PAQ8\trunk\enwik8
    Creating archive G:\svn\PAQ8\trunk\enwik8.paq8p1 with 1 file(s)...
    G:/svn/PAQ8/trunk/enwik8 100000000 -> 18013801
    100000000 -> 18013832
    Time 11761.34 sec, used 811500705 bytes of memory
    
    Type    Size            Parts
    unkn    214             10
    utf8    99999786                11
    Total parts: 21, fragmentation cost 105 bytes
    
    G:\svn\PAQ8\trunk>paq8p3_speed_optimised -7 enwik9
    Creating archive enwik9.paq8p3 with 1 file(s)...
    enwik9 1000000000 -> 150709802    (   150709295)
    1000000000 -> 150709834
    Time 72412.58 sec, used 803406050 bytes of memory
    
    Type    Size            Parts
    unkn    676             24
    text    90              1
    utf8    999999234               24
    Total parts: 49, fragmentation cost 245 bytes
    Last edited by kaitz; 21st April 2009 at 00:10.
    KZo


  12. #12
    Member
    Join Date
    May 2008
    Location
    Estonia
    Posts
    406
    Thanks
    155
    Thanked 235 Times in 127 Posts

    Post

    Updated paq8p3. Source at SVN.

    Code:
    paq8p3 -7 FP.LOG 20617071 -> 259417 Time 1594.77 sec, 803216706 bytes of memory
    KZo


  13. #13
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts

    Thumbs up

    Thanks Kaitz!

    Compiled...

    EDIT: Attachment "paq8p3_kaitz_test_version_2.zip" removed.

  14. #14
    Member
    Join Date
    May 2008
    Location
    Estonia
    Posts
    406
    Thanks
    155
    Thanked 235 Times in 127 Posts

    Post

    Some results:
    Code:
    paq8p3 -7 enwik8 100000000 -> 17990788, Time 8689.19 sec, 803216705 bytes of memory
    paq8p3 -8 enwik8 100000000 -> 17759875, Time 8730.50 sec, 1574968641 bytes of memory
    So it has better results then paq8o10t -8 17772821 (http://encode.su/forum/showpost.php?p=999&postcount=14).
    Hope it counts as improvement.

    I am out of ideas and knowledge.
    KZo


  15. #15
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    For some ideas on text compression, look at latest version of lpaq. I know Alexander Rhatushnyak was hard at work on it just before releasing the latest Hutter prize entry. The code is not clear, the result of lots of tuning, but the main improvement comes from dictionary preprocessing. When you run the Hutter prize entry decomp.exe (from LTCB under paq8hp12) it will extract the dictionary.

    Newer lpaq versions use several state tables, but my experiments with zpaq showed that none of them improved on the original table from lpaq1 on the Calgary corpus. You could also use the state table from zpaq, which does improve on it. (One of these days I'll get around to benchmarking my own program on my own benchmark )

    Also, more memory would help a lot on enwik9.

  16. #16
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,507
    Thanks
    742
    Thanked 665 Times in 359 Posts
    btw: paq reach great compression ratio due to use of f lot of models, although on every concrete type of data most models are useless. afaiu, every model has its own "importance" rating and mixer take into account this

    how about temporary disabling of least useful models? for example, we can analyze data chunk, decide what models to use and explicitly send this info to decoder

    paq compression can be made multithrteaded, decompression - can't. this way, we can run paq-level compression and decompression rather fast. compression phase need a lot of resources but it can be multi-threaded (in particular, we can analyze usabilkity of evetry model in separate thread) while decompression will need less resources since only subset of models will be used

  17. #17
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,611
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Quote Originally Posted by Bulat Ziganshin View Post
    btw: paq reach great compression ratio due to use of f lot of models, although on every concrete type of data most models are useless. afaiu, every model has its own "importance" rating and mixer take into account this

    how about temporary disabling of least useful models? for example, we can analyze data chunk, decide what models to use and explicitly send this info to decoder

    paq compression can be made multithrteaded, decompression - can't. this way, we can run paq-level compression and decompression rather fast. compression phase need a lot of resources but it can be multi-threaded (in particular, we can analyze usabilkity of evetry model in separate thread) while decompression will need less resources since only subset of models will be used
    Models do predictions independently? If yes, what's the problem with executing them in parallel?

  18. #18
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,507
    Thanks
    742
    Thanked 665 Times in 359 Posts
    in order to make predictions, you need to know previous data up to the last bit. this means that compression can be made m/t, decompression - can't

  19. #19
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,611
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Quote Originally Posted by Bulat Ziganshin View Post
    in order to make predictions, you need to know previous data up to the last bit. this means that compression can be made m/t, decompression - can't
    OK, I get what you mean.
    I mean something different. As far as I understand CM, each character is predicted independently by several models, then their outputs are mixed. Giving a thread for each model (OK, in practice something lighter would be needed) should work, no?

  20. #20
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,507
    Thanks
    742
    Thanked 665 Times in 359 Posts
    it will work, but syncronization costs will be much larger than benefit may be, on next CPU generation (like Sun Niagara these costs will be much less and it will be possible to synchronize million times per second)

  21. #21
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,611
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Quote Originally Posted by Bulat Ziganshin View Post
    it will work, but syncronization costs will be much larger than benefit may be, on next CPU generation (like Sun Niagara these costs will be much less and it will be possible to synchronize million times per second)
    Possibly.
    However, when compressing the only synchronisation needed is ensuring that mixer won't start too quickly, models can rush ahead.
    Decompression is worse...
    And with really large number of models some splitting this way would be surely worthwhile (the PAQ optimized for UIQ, don't remember the name).

  22. #22
    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 Bulat Ziganshin View Post
    ...how about temporary disabling of least useful models? for example, we can analyze data chunk, decide what models to use and explicitly send this info to decoder...
    It's already used in most PAQ8 series. But, they don't have too precise analyzer. At least, they can classify data as text or binary. Also, some models have already automatic switch off features (like RecordModel). PAQ's main problem is all of prediction relies on context mapping (on even WAV and BMP models). There is really visible redundancy. Someone could easily compare OptimFROG and PAQ8pX series on wave files. They share same modeling (technically) but encoding is different. PAQ8pX uses context mapping for "each" bits in wave files and OptimFROG uses estimated samples+modeling.
    Quote Originally Posted by m^2
    As far as I understand CM, each character is predicted independently by several models, then their outputs are mixed. Giving a thread for each model (OK, in practice something lighter would be needed) should work, no?
    That depend on actual implementation. PAQ8 is totally bitwise and "all models called for each coded bits". So, creating a model pool for multithreading could be very costly. There is a saying in Turkish about such circumstances: "The undercoat becomes more expensive than the face of the cloth" IMO, only analyzer part could be put in another thread as suggested by Bulat. But, note that current PAQ8 analyzer is too bad. For example, my analyzer reaches 30-40 MiB/s on Stephan's testsets. And I'm sure my implementation is not "perfect". Someone could easily beat it. So, there are lots of room for improvements in PAQ8.
    BIT Archiver homepage: www.osmanturan.com

  23. #23
    Member
    Join Date
    Oct 2007
    Location
    Germany, Hamburg
    Posts
    408
    Thanks
    0
    Thanked 5 Times in 5 Posts
    I got a crash for non DWORD align images. I created an example bmp 5x4. Also for 6x4 paq says it found a 8x4 image.
    Still compression and decompression seems to work but at the end of decompression the program crashes.

    Btw thats no stupid self created file. That's from an image editor.
    Attached Files Attached Files

  24. #24
    Programmer Jan Ondrus's Avatar
    Join Date
    Sep 2008
    Location
    Rychnov nad Kněžnou, Czech Republic
    Posts
    278
    Thanks
    33
    Thanked 137 Times in 49 Posts

    paq8p3fix

    paq8p3fix

    http://www.sendspace.com/file/87xvei

    - logfile was used but not opened for decompression
    - wrong width computation for 24-bit BMP images

  25. #25
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts

    Thumbs up

    Thanks Jan!

    Compiled...

    EDIT: Attachment "paq8p3_kaitz_test_version_3.zip" removed.

  26. #26
    Member
    Join Date
    Oct 2007
    Location
    Germany, Hamburg
    Posts
    408
    Thanks
    0
    Thanked 5 Times in 5 Posts
    Thank you Jan . Really fast.

  27. #27
    Member
    Join Date
    May 2008
    Location
    Estonia
    Posts
    406
    Thanks
    155
    Thanked 235 Times in 127 Posts
    Quote Originally Posted by Jan Ondrus View Post
    paq8p3fix

    http://www.sendspace.com/file/87xvei

    - logfile was used but not opened for decompression
    - wrong width computation for 24-bit BMP images
    Uploaded source in SVN.
    KZo


  28. #28
    Member
    Join Date
    Oct 2007
    Location
    Germany, Hamburg
    Posts
    408
    Thanks
    0
    Thanked 5 Times in 5 Posts
    I compressed an bmp without a color map (8 bit) and it was well detected and processed. Doesn't the model use the color palette?

  29. #29
    Member
    Join Date
    May 2008
    Location
    Estonia
    Posts
    406
    Thanks
    155
    Thanked 235 Times in 127 Posts
    Quote Originally Posted by Simon Berger View Post
    I compressed an bmp without a color map (8 bit) and it was well detected and processed. Doesn't the model use the color palette?
    No palette is used.
    KZo


  30. #30
    Member
    Join Date
    May 2008
    Location
    Antwerp , country:Belgium , W.Europe
    Posts
    487
    Thanks
    1
    Thanked 3 Times in 3 Posts
    Why is paq8p3 -0 so much slower then Paq8px -0 ? (15x slower !)

    Code:
    G:\test\enwik9>paq8px -0 enwik9
    Creating archive enwik9.paq8px with 1 file(s)...
    enwik9 1000000000 -> 1000000610
    1000000000 -> 1000000641
    Time 75.99 sec, used 600306 bytes of memory
    
    G:\test\enwik9>paq8p3 -0 enwik9
    Creating archive enwik9.paq8p3 with 1 file(s)...
    enwik9 1000000000 -> 1000000245   (   999997471)
    1000000000 -> 1000000276
    Time 1165.93 sec, used 600306 bytes of memory
    
    Type    Size            Parts
    unkn    676             24
    text    90              1
    utf8    999999234               24
    Total parts: 49, fragmentation cost 245 bytes

Page 1 of 2 12 LastLast

Posting Permissions

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