Page 6 of 8 FirstFirst ... 45678 LastLast
Results 151 to 180 of 239

Thread: Ultra-fast LZ

  1. #151
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    BTW, if replace (in the program above) LZ77 with sort-of-LZRW (hashes instead of offsets), the compression ratio will be lower than with fastest version of LZ77, however, compression time for ENWIK9 is 5 sec here (with I/O). The hefty price of such a fast compression is much slower decompression - so the LZRW thing is out.
    OK, lets call this new program a new ULZ. So the key differences of the new ULZ vs the CRUSH are:
    • ULZ is much simpler, it's kind of "minimalistic" LZ. So it's not a mess to implement it in any programming language, including ASM
    • Extremely low memory usage. Mostly it's I/O buffers. Decompressor needs no extra memory. For compression we need extra 16 KB to 1 MB of RAM
    • Due to literal-runs it is much more stable on already compressed data. The implementation above is not the best example, since it supports max 32-byte literal runs, but this can be extended to any number, but in practice it doesn't really affects compression
    • Simply one downside - relatively poor compression performance

  2. #152
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    Checked sources and docs of a bunch of fast LZ coders, and looks like this new ULZ is just LZF with a better match finder...

  3. #153
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    Results with Lazy Matching (the output is still compatible with LZF):

    FileLazy MatchingGreedy Parsing
    ENWIK846,318,130 bytes46,630,346 bytes
    ENWIK9416,377,743 bytes419,531,784 bytes
    world95.txt1,466,528 bytes1,478,020 bytes
    book1387,916 bytes390,260 bytes
    Photoshop.exe10,970,075 bytes11,079,770 bytes

    The compression gain is smaller than usual, since we do an optimization at literal run only. Anyway, it's an optimized LZF!

    BTW, how can I find the LZF executable?

  4. #154
    Member
    Join Date
    May 2008
    Location
    HK
    Posts
    160
    Thanks
    4
    Thanked 25 Times in 15 Posts
    Quote Originally Posted by encode View Post
    Results with Lazy Matching (the output is still compatible with LZF):

    FileLazy MatchingGreedy Parsing
    ENWIK846,318,130 bytes46,630,346 bytes
    ENWIK9416,377,743 bytes419,531,784 bytes
    world95.txt1,466,528 bytes1,478,020 bytes
    book1387,916 bytes390,260 bytes
    Photoshop.exe10,970,075 bytes11,079,770 bytes

    The compression gain is smaller than usual, since we do an optimization at literal run only. Anyway, it's an optimized LZF!

    BTW, how can I find the LZF executable?
    src:
    http://dist.schmorp.de/liblzf/liblzf-3.6.tar.gz

    mingw gcc 4.8 binary attached.
    Attached Files Attached Files

  5. #155
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    Quote Originally Posted by roytam1 View Post
    src:
    http://dist.schmorp.de/liblzf/liblzf-3.6.tar.gz

    mingw gcc 4.8 binary attached.
    Wow, thanks very much!

    So...

    FileLZFULZ-GreedyULZ-Lazy
    ENWIK854,672,495 bytes46,630,346 bytes46,318,130 bytes
    ENWIK9501,221,776 bytes419,531,784 bytes416,377,743 bytes
    book1472,175 bytes390,260 bytes387,916 bytes
    calgary.tar1,554,990 bytes1,311,772 bytes1,301,840 bytes
    world95.txt1,717,821 bytes1,478,020 bytes1,466,528 bytes
    Photoshop.exe12,135,683 bytes11,079,770 bytes10,970,075 bytes
    MPTRACK.EXE738,350 bytes679,048 bytes672,768 bytes


  6. #156
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,611
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Can you compare to LZ4(hc)?

  7. #157
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    ProgramENWIK8ENWIK9book1calgary.tarworld95.txtPhotoshop.exeMPTRACK.EXEpak0.pak
    LZF54,672,495501,221,776472,1751,554,9901,717,82112,135,683738,350125,205,858
    ULZ-Greedy46,630,346419,531,784390,2601,311,7721,478,02011,079,770679,048115,369,310
    ULZ-Lazy46,318,130416,377,743 387,9161,301,8401,466,52810,970,075672,768114,990,40
    LZ4 1.4 -942,283,904374,905,569363,2361,195,786948,9409,784,402644,134113,739,243
    CRUSH 1.00 cx31,731,711279,491,430302,120986,307678,8697,994,581571,839101,704,718


  8. #158
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,611
    Thanks
    30
    Thanked 65 Times in 47 Posts
    But crush is a different bit stream, isn't it?

  9. #159
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    LZ4 is about different bit stream too. CRUSH was included since it has no entropy coding - simple LZ with bit-codes. And LZF/ULZ make use of much smaller dictionary (8 KB), compared to LZ4 (64 KB)

  10. #160
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,611
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Why use just 8 KB?
    LZF compatibility is worth some, but if it significantly reduces your competitiveness, it's no good IMHO. Also, I wouldn't call bit-packed LZ the same league as byte-aligned ones...that's the territory of Tornado, (not sure) gipfeli; not LZ4.
    And, a minor note, there's LZFX; compatible with LZF too. I forgot to mention it because it was slightly worse than the original in my tests, but you may be interested.
    https://code.google.com/p/lzfx/

  11. #161
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    Quote Originally Posted by m^2 View Post
    Why use just 8 KB?
    I've already wrote a bunch of LZs (from LZP and ROLZ to LZSS and LZ77+ARI), time for something different. No reason to write another strong LZ, as LZPM or CRUSH. The idea is about a tiny LZ (in ASM?). And actually I've already done that for Nintendo DS ROM compression...

  12. #162
    Member
    Join Date
    May 2008
    Location
    HK
    Posts
    160
    Thanks
    4
    Thanked 25 Times in 15 Posts
    what about 8K slide window with 2-bytes hash tree?
    (Yes that is what -pm2- uses, which plays well in MSX world)

  13. #163
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    Quote Originally Posted by roytam1 View Post
    what about 8K slide window with 2-bytes hash tree?
    (Yes that is what -pm2- uses, which plays well in MSX world)
    -pm2- is an LZ77+Huffman a la -lh5-, if not the same.

  14. #164
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    Comparison with a classic LZSS implementation (1-byte represents eight literal/match flags)

    ProgramENWIK8ENWIK9book1calgary.tarworld95.txtPhotoshop.exeMPTRACK.EXEpak0.pak
    LZF54,672,495501,221,776472,1751,554,9901,717,82112,135,683738,350125,205,858
    ULZ-8K-Greedy46,630,346419,531,784390,2601,311,7721,478,02011,079,770679,048115,369,310
    ULZ-8K-Lazy46,318,130416,377,743387,9161,301,8401,466,52810,970,075672,768114,990,40
    LZSS-8K-Greedy45,118,916405,041,870383,8451,262,2291,417,03510,433,410643,017113,768,374
    LZSS-8K-Lazy44,360,389397,833,631376,4661,237,7571,391,48710,274,262633,928113,185,103
    LZSS-16K-Greedy45,072,458399,673,084388,3341,266,2161,119,64110,329,839641,428114,350,876
    LZSS-16K-Lazy44,649,750394,922,394388,0511,252,7041,098,61510,199,170633,899113,595,452
    LZ4 1.4 -942,283,904374,905,569363,2361,195,786948,9409,784,402644,134113,739,243
    CRUSH 1.00 cx31,731,711279,491,430302,120986,307678,8697,994,581571,839101,704,718
    * ULZ-16K leads to a poor results!

  15. #165
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    LZSS results with Optimal (Storer–Szymanski) parsing:

    ProgramENWIK8ENWIK9book1calgary.tarworld95.txtPhotoshop.exeMPTRACK.EXEpak0.pak
    LZSS-8K-Greedy45,118,916405,041,870383,8451,262,2291,417,03510,433,410643,017113,768,374
    LZSS-8K-Lazy44,360,389397,833,631376,4661,237,7571,391,48710,274,262633,928113,185,103
    LZSS-8K-Optimal43,973,740394,518,772371,2591,226,3121,381,18810,245,813631,276112,613,327
    LZSS-16K-Greedy45,072,458399,673,084388,3341,266,2161,119,64110,329,839641,428114,350,876
    LZSS-16K-Lazy44,649,750394,922,394388,0511,252,7041,098,61510,199,170633,899113,595,452
    LZSS-16K-Optimal43,999,912389,298,107379,2351,233,7141,083,77610,146,850629,683112,955,817


  16. #166
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    Completing the square, some testing of original and extremely popular LZSS (with 4 KB window) by Haruhiko Okumura (LZSS.C - 4/6/1989 Haruhiko Okumura):

    ProgramENWIK8ENWIK9book1calgary.tarworld95.txtPhotoshop.exeMPTRACK.EXEpak0.pak
    LZSS by Haruhiko Okumura49,061,218455,245,327424,1471,415,4141,579,10410,986,721669,280116,767,235
    LZSS (My match finder + Greedy parsing)49,030,575454,887,243423,8451,414,4271,578,13310,982,461669,127116,705,639
    LZSS (My match finder + Optimal parsing)47,890,384445,040,474410,7771,379,7981,544,25810,811,360658,915115,431,814


  17. #167
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    Anyway, it might be a good idea to release a new LZF program:
    Optimized LZF compressor, v1.00 ...or something like that.

  18. #168
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    I'm experimenting with LZSS these days.
    Optimized LZF is cool, but I've came up with a somewhat better LZ coder - it's like to sum up all the LZ compressors I have implemented.
    It's LZSS with 16KB window.
    Three compression modes:
    fast (cf) - LZOP & Co competitor - same speed as LZOP, but with a bit higher compression. It's faster than LZF and ULZ in fastest modes. As a note it's not the fastest mode for this LZSS - compression can be slightly faster with a notable compression loss
    normal (c) - Balanced mode - to keep less air in compressed files
    max (cx) - To achieve the maximum compression within a given compression format, at any cost. Optimal parsing (Storer & Szymanski) requires extra 128MB.
    Other modes use 17MB for compression. Decompressor requires 16MB (it's I/O buffer)
    Anyway, why not?

  19. #169
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    The compression results of an upcoming LZSS-16K with different parsing schemes:

    ENWIK9 resultComments
    1,000,000,000 -> 448,712,956Greedy Parsing (Fast Match Finder)
    1,000,000,000 -> 399,850,630Greedy Parsing (Balanced Match Finder)
    1,000,000,000 -> 399,673,075Greedy Parsing (Exhaustive Match Finder)
    1,000,000,000 -> 389,298,103Standard Storer&Szymanski Parsing
    1,000,000,000 -> 380,613,043Advanced Storer&Szymanski Parsing (A few matches considered at each file position)


  20. #170
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    Improved parser, now it's sort of Dynamic Programming. And new ENWIK9 result is 380,192,378 bytes. The LZSS coding is really primitive, so super-mega parser helps just a little. Although, CRUSH with such a parser could be a killer...

  21. #171
    Member
    Join Date
    May 2012
    Location
    United States
    Posts
    323
    Thanks
    178
    Thanked 52 Times in 37 Posts
    Quote Originally Posted by encode View Post
    Although, CRUSH with such a parser could be a killer...
    I think you should make this! Sounds great to me

  22. #172
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    Quote Originally Posted by comp1 View Post
    I think you should make this! Sounds great to me
    Just right now I'm working on PPMX and have no time for LZ experiments. However, right after PPMX v0.09 release I might test CRUSH with Optimal Parsing.

  23. The Following User Says Thank You to encode For This Useful Post:

    Garen (9th March 2014)

  24. #173
    Member
    Join Date
    Oct 2013
    Location
    Filling a much-needed gap in the literature
    Posts
    350
    Thanks
    177
    Thanked 49 Times in 35 Posts
    Anybody have any insight into the effects of using preload dictionaries built with one parsing strategy, but using that at runtime with a different (faster) one?

    I'm wondering if it makes sense to build preloads with optimal parsing, and then use them with greedy parsing, or something like that, so that the parsing done in building the preload implicitly guides how the fast runtime parser chops things up.

    Given my poor understanding of parsing issues, though, I don't know if this even makes sense, or if there's a subtler strategy that would work better than picking between "normal" parsing strategies.

  25. #174
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    I think I will reincarnate my ULZ. I might call it uLZ (micro LZ or Ultra/Unreal LZ) instead of Ultra-fast one, since LZ4 took this niche.
    My goals are:
    • Fast enougth decompression (~1 GB/sec on ENWIK9), faster than my LZ4X and much faster than original ULZ that uses getc()/putc() I/O
    • Deflate-like compression on text files and textures (Ultra compression mode) - due to enlarged window (64-512 KB). I think I'll pick 128 or 256 KB window. I tested 8 MB and up to infinite window size and I didn't really liked what I've got



    I like LZNib (Charles Bloom) idea of coding match lengths and literal runs within nibbles - it provides notable higher compression than LZ4-like scheme (since it is redundant with zero literal run lengths).
    Anyway, I'll test all ideas and pick the best one. And actually original ULZ coding is not bad - it needs just more optimized implementation...

  26. The Following 4 Users Say Thank You to encode For This Useful Post:

    avitar (27th June 2016),Bulat Ziganshin (24th June 2016),Cyan (24th June 2016),SolidComp (23rd June 2016)

  27. #175
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    Current results:

    Window SizeENWIK9ENWIK8world95.txt3200.txtbook1
    64K369,673,32041,775,161927,8897,080,917359,374
    128K348,223,77239,339,915853,6216,540,622334,201
    256K329,119,60937,199,413789,8476,085,096316,618


  28. The Following User Says Thank You to encode For This Useful Post:

    comp1 (24th June 2016)

  29. #176
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    Okay, the new results (my old 3770K @ 4.6 GHz)

    Code:
    z:\>ulz cf enwik8
    Compressing enwik8:
    100000000 -> 45613380 in 0.78s
    
    z:\>ulz c enwik8
    Compressing enwik8:
    100000000 -> 39946599 in 4.16s
    
    z:\>ulz cu enwik8
    Compressing enwik8:
    100000000 -> 37199413 in 11.22s
    
    z:\>ulz d enwik8.ulz
    Decompressing enwik8.ulz:
    37199413 -> 100000000 in 0.16s
    
    z:\>ulz cf enwik9
    Compressing enwik9:
    1000000000 -> 402610627 in 6.98s
    
    z:\>ulz c enwik9
    Compressing enwik9:
    1000000000 -> 353878403 in 33.64s
    
    z:\>ulz cu enwik9
    Compressing enwik9:
    1000000000 -> 329119609 in 114.96s
    
    z:\>ulz d enwik9.ulz
    Decompressing enwik9.ulz:
    329119609 -> 1000000000 in 1.37s


    And a new EXE to play with:
    Attached Files Attached Files

  30. The Following User Says Thank You to encode For This Useful Post:

    comp1 (26th June 2016)

  31. #177
    Member
    Join Date
    Sep 2011
    Location
    uk
    Posts
    237
    Thanks
    187
    Thanked 16 Times in 11 Posts
    Compare with 8 year old ccmx on xp 1.4Ghz, only 1.4G memory. File is text/xml. Same speeds and ulz compresses better than 10% which is good, but ccmx 5 times better compression!

    Why is ccmx still so good?

    How much memory does ulz use?

    j

    c:\live_sole>tim ulz cu ans.dat tmp
    Compressing ans.dat:
    2436181 -> 211056 in 3.02s
    -- ulz cu ans.dat tmp 03.05 1 loops, 3.04 sec each

    c:\live_sole>tim ccmx 3 ans.dat tmp
    -------------------------------------------------------------------------------
    CCMx 1.30c (Apr 24 200 - Copyright (c) 2007-2008 by Christian Martelock
    Contact: christian.martelock@web.de - TEST version - May contain bugs...
    -------------------------------------------------------------------------------
    Allocated 146 MiB of memory.
    2379.08 KiB -> 49.01 KiB (ratio 2.06%, speed 1238 KiB/s)
    -- ccmx 3 ans.dat tmp 02.31 1 loops, 2.29 sec each

  32. #178
    Member
    Join Date
    May 2012
    Location
    United States
    Posts
    323
    Thanks
    178
    Thanked 52 Times in 37 Posts
    Quote Originally Posted by avitar View Post
    Compare with 8 year old ccmx on xp 1.4Ghz, only 1.4G memory. File is text/xml. Same speeds and ulz compresses better than 10% which is good, but ccmx 5 times better compression!

    Why is ccmx still so good?

    How much memory does ulz use?

    j

    c:\live_sole>tim ulz cu ans.dat tmp
    Compressing ans.dat:
    2436181 -> 211056 in 3.02s
    -- ulz cu ans.dat tmp 03.05 1 loops, 3.04 sec each

    c:\live_sole>tim ccmx 3 ans.dat tmp
    -------------------------------------------------------------------------------
    CCMx 1.30c (Apr 24 200 - Copyright (c) 2007-2008 by Christian Martelock
    Contact: christian.martelock@web.de - TEST version - May contain bugs...
    -------------------------------------------------------------------------------
    Allocated 146 MiB of memory.
    2379.08 KiB -> 49.01 KiB (ratio 2.06%, speed 1238 KiB/s)
    -- ccmx 3 ans.dat tmp 02.31 1 loops, 2.29 sec each
    That's comparing apples to oranges:ccmx uses contexts, ulz uses LZ.

    Also, ccms has great filters that Christian wrote to give a great ratio and great speed.

  33. #179
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,965
    Thanks
    367
    Thanked 343 Times in 134 Posts
    Also, try to compare the decompression speed!

    ULZ approx. memuse:
    cf/c - 16*2 + 1 + 1 MB
    cu - 16*2 + 1 + 2 + 16*12 MB
    d - 16*2 MB (no extra memory, except I/O buffers)

  34. #180
    Member
    Join Date
    Sep 2011
    Location
    uk
    Posts
    237
    Thanks
    187
    Thanked 16 Times in 11 Posts
    1) I'm a user not a compressor designer so don't give a s**t how they work - why don't you /bulat/igor et al write good filters too? Surely can't be that hard?Afaik on text lz should be good. Why after all these years can't you and other gurus do as well or better than ccmx? Why is his just so much better than Bulat's, Igor's and you and the other .ru users?

    2) add memory taken to the output a la ccmx?

    3) seriously, end of ccmx rant, thanks for ulz

    j

Page 6 of 8 FirstFirst ... 45678 LastLast

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
  •