Results 1 to 13 of 13

Thread: Compression algorithms explanation [LZ4,zstd,lizard]

  1. #1
    Member
    Join Date
    Dec 2020
    Location
    Moscow, Russia
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Compression algorithms explanation [LZ4,zstd,lizard]

    Hi, right now I study at University and work at my coursework, related to compression algorithms.
    And I consider Lizard library, compared to ZSTD and LZ4.
    Can anyone provide explanations of these algorithms and why Lizard provides better performance than LZ4?

  2. #2
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,131
    Thanks
    319
    Thanked 1,395 Times in 800 Posts
    Well,
    https://en.wikipedia.org/wiki/Zstandard#Design
    https://en.wikipedia.org/wiki/LZ4_(c...orithm)#Design
    "Lizard" (https://github.com/inikep/lizard; aka LZ5) is simply a branch of LZ4 with added optional huffman coding.
    There could be also some unique speed optimizations, but nothing noticeable: https://github.com/inikep/lizard#benchmarks
    and likely the only way to compare LZ4 vs lizard would be to directly analyze the sources... or get @inikep to explain, but I don't think he has time for that.
    To start, you'd have to actually benchmark the algorithms on your own - LZ4 and zstd also kept updating, so I don't think there's an up-to-date benchmark anywhere.

    Also keep in mind that "levels" are arbitrary, they're simply indices in a table with detailed compressor parameter profiles:
    https://github.com/inikep/lizard/blo..._common.h#L234
    But only zstd has a dedicated tool for optimization of these level profiles - https://github.com/facebook/zstd/blo...mgrill.c#L2632
    so manually chosen profiles in other compressors may have worse performance,
    while not actually reflecting the best possible performance of the algorithm (with optimal parameters for given data).

  3. #3
    Member lz77's Avatar
    Join Date
    Jan 2016
    Location
    Russia
    Posts
    176
    Thanks
    60
    Thanked 16 Times in 12 Posts
    Quote Originally Posted by fibersel View Post
    why Lizard provides better performance than LZ4?
    I guess, because LZ4 has only one codeword type: 16 bit for offset, and 4 bit for literal/match length counter. This is wasteful.

  4. #4
    Member
    Join Date
    Dec 2020
    Location
    Moscow, Russia
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Lizard has more codeword types?

  5. #5
    Member lz77's Avatar
    Join Date
    Jan 2016
    Location
    Russia
    Posts
    176
    Thanks
    60
    Thanked 16 Times in 12 Posts
    I don't know about Lizard, but LZ5 has 4 or 5 codeword types.

  6. #6
    Member
    Join Date
    May 2020
    Location
    Berlin
    Posts
    76
    Thanks
    21
    Thanked 25 Times in 20 Posts
    Quote Originally Posted by lz77 View Post
    I don't know about Lizard, but LZ5 has 4 or 5 codeword types.
    This still seems to be the case:
    The token is a one byte. Token decribes:
    • how many literals should be copied from Literals_Stream
    • if offset should be read from 16-bit_Offsets_Stream or 24-bit_Offsets_Stream
    • how many bytes are part of a match and should be copied from a sliding window

    Lizard uses 4 types of tokens:

    • [0_MMMM_LLL] - 3-bit literal length (0-7+), use offset from 16-bit_Offsets_Stream, 4-bit match length (4-15+)
    • [1_MMMM_LLL] - 3-bit literal length (0-7+), use last offset, 4-bit match length (0-15+)
    • token 31 - no literal length, use offset from 24-bit_Offsets_Stream, match length (47+)
    • token 0-30 - no literal length, use offset from 24-bit_Offsets_Stream, 31 match lengths (16-46)

    lizard/lizard_Block_format.md at lizard · inikep/lizard · GitHub

  7. #7
    Member lz77's Avatar
    Join Date
    Jan 2016
    Location
    Russia
    Posts
    176
    Thanks
    60
    Thanked 16 Times in 12 Posts
    Yes, I saw these codewords in LZ5 a few years ago. They make me smile.
    I'm planning to write simple LZ-type compressor (without preprocessor for the/and/.../E8/E9 etc.) that compresses enwik8 up to ~40.5% and (de)compresses it faster than zstd -1 (ratio = 40.8%). Or maybe I'm trying in vain and there are already such compressors?

  8. #8
    Member lz77's Avatar
    Join Date
    Jan 2016
    Location
    Russia
    Posts
    176
    Thanks
    60
    Thanked 16 Times in 12 Posts
    4 questions about the fastest compression mode (zstd.exe -1 ...)

    1. Does zstd use additional compression (Huffman, FSE) besides LZ?
    2. Is there any optimization (E8/E9 etc.) or analysis of source data to configure the compression algorithm?
    3. What is the size of the hash table with this option (how many cells and are there chains)?
    4. What is the size of the input buffer?

    Thanks.

  9. #9
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,131
    Thanks
    319
    Thanked 1,395 Times in 800 Posts
    0) -1 is not the fastest mode (--fast=# ones are faster).
    It seems that --fast disables huffman coding for literals, but still keeps FSE for matches.
    1) Yes, huffman for literals, FSE for matches - or nothing if block is incompressible
    2) No. Certainly no preprocessing, but maybe you'd say that "--adapt" mode is related.
    3) https://github.com/facebook/zstd/blo...mpress.c#L5003 - 16k cells
    4) The library works with user buffers of whatever size, zstdcli seems to load 128KB blocks with fread.
    https://github.com/facebook/zstd/blo...ib/zstd.h#L108

  10. Thanks:

    lz77 (25th January 2021)

  11. #10
    Member lz77's Avatar
    Join Date
    Jan 2016
    Location
    Russia
    Posts
    176
    Thanks
    60
    Thanked 16 Times in 12 Posts
    Wow, I guess I finishing writing (for now in Delphi 7) not bad simple pure LZ77-type compressor called notbadlz. I'm trying to beat zstd at fast levels for sporting interest. I set in my compressor 128K input buffer and 16K cells, here are results:
    (zstd-v1.4.4-win64)
    Code:
    A:\>timer.exe zstd.exe --fast -f --no-progress --single-thread enwik8
    
    Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
    enwik8               : 51.82%   (100000000 => 51817322 bytes, enwik8.zst)
    
    
    Kernel Time  =     0.062 = 00:00:00.062 =   7%
    User Time    =     0.781 = 00:00:00.781 =  90%
    Process Time =     0.843 = 00:00:00.843 =  98%
    Global Time  =     0.859 = 00:00:00.859 = 100%
    ***
    
    A:\>timer.exe notbadlz.exe
    
    
    Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
    Source size 100000000, packed size: 47086177 ratio 0.47086
    Done in 1.35210
    
    
    Kernel Time  =     0.078 = 00:00:00.078 =   5%
    User Time    =     1.359 = 00:00:01.359 =  93%
    Process Time =     1.437 = 00:00:01.437 =  98%
    Global Time  =     1.453 = 00:00:01.453 = 100%
    ***
    
    A:\>timer.exe zstd.exe -d -f --no-progress --single-thread enwik8.zst -o enwik
    
    
    Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
    enwik8.zst          : 100000000 bytes
    
    
    Kernel Time  =     0.109 = 00:00:00.109 =  24%
    User Time    =     0.203 = 00:00:00.203 =  44%
    Process Time =     0.312 = 00:00:00.312 =  68%
    Global Time  =     0.453 = 00:00:00.453 = 100%
    
    A:\>timer notbadlzunp.exe
    
    
    Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
    Compressed size: 47086177 Decompressed size: 100000000
    Done in 0.52653 sec.
    
    
    Kernel Time  =     0.093 = 00:00:00.093 =  12%
    User Time    =     0.515 = 00:00:00.515 =  68%
    Process Time =     0.609 = 00:00:00.609 =  81%
    Global Time  =     0.750 = 00:00:00.750 = 100%



    With 128K cells and input buffer size = 256 Mb notbadlz compresses enwik8 better than zstd -1. Zstd does it faster, but I have in stock asm 64, prefetch etc. Now I'm thinking whether it's worth porting my program in FASM...

  12. #11
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,131
    Thanks
    319
    Thanked 1,395 Times in 800 Posts
    Maybe increase window size for zstd? "-1" default is 512kb
    Also test newer zstd? They made significant speed improvements in 1.4.5, and extra 5% in 1.4.7 too.

  13. Thanks:

    lz77 (27th January 2021)

  14. #12
    Member
    Join Date
    Dec 2013
    Location
    Italy
    Posts
    517
    Thanks
    25
    Thanked 45 Times in 37 Posts
    Quote Originally Posted by lz77 View Post
    Wow, I guess I finishing writing (for now in Delphi 7) not bad simple pure LZ77-type compressor called notbadlz. I'm trying to beat zstd at fast levels for sporting interest. I set in my compressor 128K input buffer and 16K cells, here are results:
    (zstd-v1.4.4-win64)
    Code:
    A:\>timer.exe zstd.exe --fast -f --no-progress --single-thread enwik8
    
    Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
    enwik8               : 51.82%   (100000000 => 51817322 bytes, enwik8.zst)
    
    
    Kernel Time  =     0.062 = 00:00:00.062 =   7%
    User Time    =     0.781 = 00:00:00.781 =  90%
    Process Time =     0.843 = 00:00:00.843 =  98%
    Global Time  =     0.859 = 00:00:00.859 = 100%
    ***
    
    A:\>timer.exe notbadlz.exe
    
    
    Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
    Source size 100000000, packed size: 47086177 ratio 0.47086
    Done in 1.35210
    
    
    Kernel Time  =     0.078 = 00:00:00.078 =   5%
    User Time    =     1.359 = 00:00:01.359 =  93%
    Process Time =     1.437 = 00:00:01.437 =  98%
    Global Time  =     1.453 = 00:00:01.453 = 100%
    ***
    
    A:\>timer.exe zstd.exe -d -f --no-progress --single-thread enwik8.zst -o enwik
    
    
    Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
    enwik8.zst          : 100000000 bytes
    
    
    Kernel Time  =     0.109 = 00:00:00.109 =  24%
    User Time    =     0.203 = 00:00:00.203 =  44%
    Process Time =     0.312 = 00:00:00.312 =  68%
    Global Time  =     0.453 = 00:00:00.453 = 100%
    
    A:\>timer notbadlzunp.exe
    
    
    Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
    Compressed size: 47086177 Decompressed size: 100000000
    Done in 0.52653 sec.
    
    
    Kernel Time  =     0.093 = 00:00:00.093 =  12%
    User Time    =     0.515 = 00:00:00.515 =  68%
    Process Time =     0.609 = 00:00:00.609 =  81%
    Global Time  =     0.750 = 00:00:00.750 = 100%



    With 128K cells and input buffer size = 256 Mb notbadlz compresses enwik8 better than zstd -1. Zstd does it faster, but I have in stock asm 64, prefetch etc. Now I'm thinking whether it's worth porting my program in FASM...
    Can you please post the Delphi source?

  15. #13
    Member lz77's Avatar
    Join Date
    Jan 2016
    Location
    Russia
    Posts
    176
    Thanks
    60
    Thanked 16 Times in 12 Posts
    > Can you please post the Delphi source?

    Pardon, I have another plans.
    I do not receive a salary either on Google or on Facebook. I want to sell this algorithm and sources (in C) as a shareware. Perhaps the students will be interested in this. Maybe in the next GDC this algorithm will help me win a prize.

    Quote Originally Posted by Shelwien View Post
    Maybe increase window size for zstd? "-1" default is 512kb
    Also test newer zstd? They made significant speed improvements in 1.4.5, and extra 5% in 1.4.7 too.
    zstd ver. 1.4.7 in fast mode and single thread shows the same results: 50% faster than notbadlz, but ratio worse on 4%.

    notbadlz with input buffer size = 100 Mb and hash table size = 2 Mb compresses enwik8 up to 38.75%, silesia.tar up to 35%.
    Last edited by lz77; 30th January 2021 at 20:02.

Similar Threads

  1. Amazon AZ64 compression better than Zstd
    By SolidComp in forum Data Compression
    Replies: 9
    Last Post: 1st May 2020, 20:58
  2. Replies: 8
    Last Post: 30th July 2019, 18:20
  3. Combining compression algorithms (image + archive)
    By Noob in forum Data Compression
    Replies: 19
    Last Post: 3rd July 2016, 00:58
  4. Papers - Summary of Data Compression Algorithms
    By Gonzalo in forum The Off-Topic Lounge
    Replies: 12
    Last Post: 10th February 2015, 08:24
  5. BWTS explanation?
    By TopQuark in forum Data Compression
    Replies: 5
    Last Post: 8th April 2009, 23:26

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
  •