LZ4X - An Optimized LZ4 Compressor

[encode]

Okay, this is the very first release of my optimized version of the LZ4 algorithm. It is compatible with current LZ4 versions (LZ4 Legacy frame). However, in future versions I'd like to remove the decoder restrictions like "LAST_LITERALS" and add support for a larger block (this won't break backward compatibility with the current Legacy format).

For those of you who are not familiar with the LZ4 - this program developed for a fast compression with the fastest and simplest decoder. The goal of the LZ4X is to produce the smallest .LZ4 files possible (c4 level) being compatible with the original LZ4!

The program can be found at: https://github.com/encode84/lz4x

Enjoy new release!

[Sportman]

Used same HTML file as in big test some days ago:

Input:
30,720 bytes HTML

Output:
12,589 bytes, 0.014 sec - 0.009 sec., LZ4Opt cf (0.005 sec. - 0.001 sec. reported)
11,902 bytes, 0.023 sec - 0.009 sec., LZ4Opt cb (0.013 sec. - 0.000 sec. reported)

[Matt Mahoney]

Nice. I posted your results. http://mattmahoney.net/dc/text.html#3721

[encode]

Thanks a lot!

[m^2]

Any chance that you release the sources?

[cbloom]

FYI

Oodle LZB16 (very similar to LZ4)

enwik8 100,000,000 ->41,936,109 = 3.355 bpb = 2.385 to 1

encode 17.493 seconds

Obviously different machine so speeds not directly comparable, but similar ballpark. So, you've got it right!

[encode]

Can't say about the source right now - since the program is still not finished. I'm talking about the Brute mode - I have to do something with the match finder - the one I use right now goes nuts with these unlimited match lengths - with some highly redundant files it may nearly freeze.
I pretty confident with Fast/Normal compression modes right now though.

Great honor and pleasure to see you here, Charles!
As a note, a few things may slightly improve compression here:

• If get rid of LAST_LITERALS decoder restriction. If do so, files won't be unpacked by current versions of LZ4. My decoder has no such restrictions, by the way. The compression improvement is couple of bytes.
• Using the full range of match distances will save us a few bytes for sure. And again this will break LZ4 compatibility completely.
• A better match finder may improve compression for a couple of bytes, again.
• A larger block, say, 16 MB, will lead us to more noticeable compression improvement on ENWIK8/9.
• I'm pretty confident with the current optimal path builder (string parser, whatsoever), however, it is possible to further improve it - again you win a couple of bytes at best.

[joerg]

at first thank you very much for your new program lz4opt

is here a problem with the "cb" - feature? ...

if i compress a file (61 GBytes , database-backup) with mode -c then the compressing needs not a long time
but with mode -cb it now works 25 hours (within taskmanager visible - it use CPU 30 % ...) but no progress is visible ...

***
c:\_2016-01>lz4opt
Optimized LZ4 Compressor, v1.00
Copyright (C) 2016 Ilya Muravyov

Usage: lz4opt command infile outfile

Commands:
c Compress (cf = fast, cb = brute)
d Decompress
***

c:\_2016-01>lz4opt c backup.dat back-c
backup.dat: 61781575680->16229966648 in 937.260s

c:\_2016-01>lz4opt cb backup.dat back-cb
backup.dat:
***

best regards

PS: what do you think about optimizing speed for such old compressing-algorithms like pbzip2 ?
last version 1.1.13 is from 2015-12-18: https://launchpad.net/pbzip2/1.1/1.1...-1.1.13.tar.gz

in our days we have 4 cores or 8 cores or more in a pc and not many algorithms can using good so much cores ...

[encode]

As to "cb" mode, look at my notes above. I call it "Brute" to warn users about its "speed". It's all about getting the best compression possible within given compression format (keeping the decoder compatibility). No matter how much time it will consume. Although, match finder must be improved here for sure. And yes, a progress indicator is pretty handy, but, hey, it was initial release!

[m^2]

How about suffix array match finder?

[joerg]

@encode: thank you for your comment

now the program works 31 hours and it seems really to work on progress ...
the outputfile is now bigger then 7 hours before

best regards

[Bulat Ziganshin]

How about suffix array match finder?

why it should be better?

[cbloom]

My LZB16 optimal parse uses a suffix array.

For the specific parameters of :

1. small window (64k in this case)
2. find the absolute longest match length in that window (not approximate)
3. find matches at every position (optimal parse, not greedy)

in my tests suffix array was the fastest.

Other algorithms all have terrible N^2 blowups unless you limit their search depth, which means they aren't finding the longest matches.

Getting the suffix array searcher right is not trivial. You do something like build suffix arrays on 128k byte chunks that overlap by 64k. When you string search, you need to rule out strings that are ahead of the current position, that has to be done right or it ruins the speed.

Many blog posts on this topic :

http://cbloomrants.blogspot.com/2012...sion-tree.html

http://cbloomrants.blogspot.com/2011...t-release.html

http://cbloomrants.blogspot.com/2011...th-suffix.html

http://cbloomrants.blogspot.com/2011...ts-part-6.html

http://cbloomrants.blogspot.com/2010...ring-pair.html

http://cbloomrants.blogspot.com/2011...ndex-with.html


In hindsight, personally I wouldn't bother with this. I'd just use a simpler matcher and accept that it doesn't get you the absolute best matches.

[cbloom]

In theory, the sliding-window Suffix Tree would work well, but in practice that algorithm is too complicated and a fast implementation has never been done. I have a fast suffix tree, but it's non-sliding, and the current sliding suffix tree implementations are much slower than suffix array.

ADD:

I just uploaded my string match stress test files. Post about it here :

http://www.cbloom.com/rants.html

http://www.cbloom.com/misc/string_match_stress_tests.7z

The current LZ4Opt cb mode does get caught out on a few of these files (unsurprisingly). Anyway, maybe it will be useful for other string match developers to test on these stress cases.

[joerg]

@encode:
first testresult with my testfile:
lz5 Version 1.4 with mode -13 compresses better and faster then the actual lz4opt in mode -cb

c:\_2016-LZ5>lz5 -13 backup.dat bac-lz5-13
Compressed 61781575680 bytes into 10748535546 bytes ==> 17.40%

compressing time for lz5 is 4 hours

keep it working
best regards

[Matt Mahoney]

I use a suffix array (libdivsufsort) to find matches in zpaq -method 2. It quickly finds the longest match by scanning forward and back for the first non-future match and taking the longer of the two. But you also need an inverse suffix array to find where to start the scan. To save memory (4.5x block size instead of 8x), I build just 1/8 of the ISA 8 times.

[encode]

@encode:
lz5 Version 1.4 with mode -13 compresses better and faster then the actual lz4opt in mode -cb

And again you test "Brute" mode on speed... Moreover, you compare apples to oranges here. Compare lz4opt with lzma then. Don't be mistaken by its name - lz5 has nothing in common with lz4. Or else I can call the lzma modification of lz4. A larger dictionary is extremely important with these byte-aligned/no huffman LZ77 coders. And even Greedy LZ77 with a larger window may beat an Optimal LZ with a smaller one...

[inikep]

@joerg: try "lz5 -13 -B7 backup.dat bac-lz5-13-b7"

lz5 has nothing in common with lz4. Or else I can call the lzma modification of lz4.

LZ5 -13 in comparison to LZ4 has:
- different codewords
- a larger window
- an optimal parser
But is not LZ4+LZMA. Maybe it's in the middle between LZ4 and LZMA. LZMA has binary flags, arithmetic coding, and uses contexts.

[joerg]

results for lz4opt:

c:\_2016-01>lz4opt c backup.dat back-c
backup.dat: 61781575680->16229966648 in 937.260s

c:\_2016-01>lz4opt cb backup.dat back-cb
backup.dat: 61781575680->15251536527 in 173665.596s

the program works with -cb correctly , but the time ..

[encode]

Working on a new release. Not really happy with the current program name, so:

Optimized LZ4 Compressor, v1.01
Copyright (C) 2016 Ilya Muravyov

Usage: LZ4X command infile [outfile]

Commands:
    c Compress (ch=High, cx=Extreme)
    d Decompress

My current goal is to improve the match finder. And, I'm planning to simultaneously upgrade the CRUSH's match finder as well.

[comp1]

Working on a new release. Not really happy with the current program name, so:

Optimized LZ4 Compressor, v1.01
Copyright (C) 2016 Ilya Muravyov

Usage: LZ4X command infile [outfile]

Commands:
    c Compress (ch=High, cx=Extreme)
    d Decompress

My current goal is to improve the match finder. And, I'm planning to simultaneously upgrade the CRUSH's match finder as well.

Great news Ilya! Can't wait for both updated versions to be released!

[encode]

Have tested many approaches and kept the Binary Tree match finder for Extreme mode. Compared to initial release, this is a night and day difference. Speed improvement is about 3X to 10X in average in pair with a slightly higher compression!
For Normal (default) and High modes I kept the Hash Chain match finder. New Normal mode is as fast as Fast mode in LZ4Opt with a higher compression. The brand new High mode is kept for reference as the best Greedy coder.



New result for enwik9 is 372,073,904 bytes.

[lz77]

Hi Ilya, does your lz77 compressor uses only one thread in fast mode? Serge

[encode]

Hi Ilya, does your lz77 compressor uses only one thread in fast mode? Serge

Yep, the entire program is single-threaded. For super-fast, multi-threaded compression/decompression you may use the original LZ4. My program is intended to crunch the last byte from the compressed data.

[encode]

For hash functions discussion, please use dedicated threads, like: http://encode.su/threads/62-Knuth-s-...cative-Hashing

BTW, the LZ4X v1.01 is now available!

Look at the first post and CompressMe.net

[encode]

Have tested some LZ4 modifications:
No code has to be inserted here.
LZ4 with 128KB window (we grab one bit from the literal run field) looks pretty good and IMHO it is the best candidate for LZ4v2 (or how we should call it?)
Or, I can release my own program e.g. ULZ as the LZO/LZ4 competitor.

[encode]

BTW, as with LZO, Match Distance if 0 could be EOF

[encode]

The token byte could look like:

rrr o llll (3+1+4 bits)

rrr - literal run length

o - the highest bit of a match distance (17-bit window)

llll - match length as usual

[m^2]

Why does 128 look better than 256 to you?
I'd try to lengthen it still.

[joerg]

c:\_2016-02>lz4x
Optimized LZ4 Compressor, v1.01
Copyright (C) 2016 Ilya Muravyov

Usage: LZ4X command infile [outfile]

Commands:
c Compress (ch=High, cx=Extreme)
d Decompress

c:\_2016-02>lz4x c backup.dat back-lz4xc
backup.dat: 61781575680->16967643527 in 851.640s

c:\_2016-02>lz4x ch backup.dat back-lz4xch
backup.dat: 61781575680->16080120664 in 1317.329s

c:\_2016-02>lz4x cx backup.dat back-lz4xcx
backup.dat: 61781575680->15251128571 in 103948.294s


for reference:

the testfile backup.dat has 61.781.575.680 bytes

compressing with 7z -mx (06 hours) - the resulting file has 6.751.177.712 bytes
compressing with nanozip (20 hours) - the resulting file has 5.531.178.505 bytes

@encode: the new mode "lz4x ch" seems to be the better way ...

best regards