LZPM v0.17 is here! (LZ77+ARI+Optimal Parsing)

[encode]

Hi all!

Please welcome my (new) LZ77 compressor!
It's basically a baseline LZ77 - no buffered (rep) offsets, no literal masking, no exe-filters, whistles and bells. On some files it could be very efficient on other ones - not. On ENWIKs it's not the best performer, but on files like fp.log or english.dic LZPM is pretty good (for pure LZ77).
Window size = block size = 128 MB.

Enjoy new release!

[SolidComp]

What is it for? Is this a reference implementation, a design exercise?

[encode]

I've done some experiments with LZ77 offset (distance) context coding. Decided to share the results + it's my first decent and publicly available "LZ77+ARI+Optimal Parsing" compressor. Previous program was LZPM v0.16 (back in 2008 ) - not the right or competitive implementation. For me, as a data compression author it is a must have.

Quick results on "fp.log":

Original              -> 20,617,071 bytes
NLZM v1.02 -window:27 -> 858,733 bytes
Tornado v0.6 -16      -> 807,692 bytes
ZSTD v1.4.4 -19       -> 805,203 bytes
LZMA v19.00 -fb273    -> 707,646 bytes
MComp v2.00 -mlzx     -> 696,338 bytes
LZPM v0.17            -> 685,952 bytes

[Lucas]

Very impressive work Ilya!
​It's nice to see progress in the lz space.

[encode]

BWT, the work on the program in progress - I already improved the decompression speed (branchless RC operations for unencoded bits (p=0.5))

[Jyrki Alakuijala]

I've done some experiments with LZ77 offset (distance) context coding. Decided to share the results + it's my first decent and publicly available "LZ77+ARI+Optimal Parsing" compressor. Previous program was LZPM v0.16 (back in 2008 ) - not the right or competitive implementation. For me, as a data compression author it is a must have.

Quick results on "fp.log":

Original              -> 20,617,071 bytes
NLZM v1.02 -window:27 -> 858,733 bytes
Tornado v0.6 -16      -> 807,692 bytes
ZSTD v1.4.4 -19       -> 805,203 bytes
LZMA v19.00 -fb273    -> 707,646 bytes
MComp v2.00 -mlzx     -> 696,338 bytes
LZPM v0.17            -> 685,952 bytes

How does it compare with brotli --large_window 25 --quality 11 ?

[encode]

How can I find the official Win32/Win64 binary?

[encode]

Uh, I think it's here:
https://bintray.com/vszakats/generic/brotli

[encode]

How does it compare with brotli --large_window 25 --quality 11 ?

brotli --large_window=25 --quality=11 fp.log result -> 742,328 bytes

[Sportman]

lzpm v0.17:
25,450,555 bytes, 88.156 sec. - 1.398 sec., enwik8
221,642,311 bytes, 1,004.171 sec. - 11.919 sec., enwik9
2,176,296,216 bytes, 9,667.514 sec. - 116.401 sec., enwik10

[Lucas]

If I understand lzpm correctly this is purely context modelling improvements right?
I'll take a wild guess: hierarchical context modelling of the raw offset bits?

​

[encode]

Well, it's much simpler - LZPM make use of greater number of position slots vs standard 6-bit value (64 slots). This leads to more precise coding of higher bits of a distance (offset). However, on regular text files it takes no advantage - that's why LZPM poorly compresses ENWIKs.
The context is simply a match length - a pretty standard and generic thing. This helps catch a match length vs. match distance correlation.
Now I'm experimenting with the lower bits of a distance coding. All in all, the distance value could be huge - so we use "divide and conquer" thing here.
By the LZPM format, the distance (window size) is restricted to ~4 GB. So I'm thinking to add the "Block/Window Size" option. The memory usage for compression is (9*BlockSize) + 64 MB + Arith model. For decoding it's BlockSize + Arith model only.
As a note - I cannot use complex CM stuff here - this will kill the decompression speed. I'm trying to be on par with LZMA complexity. However, LZPM has a higher precision RC/Arith model - try to compress A10.jpg...

[Lucas]

That sounds similar to what I had in mind.
Thank you for sharing!
Btw in my lz endeavours I found very large gains (30-40% higher compression) on binary data by implementing lzma's matchByte model. It doesn't even need to use statistics to give gains, which should keep speed up.
Good luck with lzpm! I like where it's heading

[turpro]

enwik8
Compressing 'enwik8':
​100,000,000 -> 25,450,555 in 140.435s

Decompressing 'enwik8.lzpm':
25,450,555 -> 100,000,000 in 2.764s

acrord32.exe
Compressing 'acrord32.exe':
3,870,784 -> 1,576,824 in 2.726s

Decompressing 'acrord32.exe.lzpm':
1,576,824 -> 3,870,784 in 0.119s

english.dic
Compressing 'english.dic':
4,067,439 -> 778,491 in 2.024s

Decompressing 'english.dic.lzpm':
778,491 -> 4,067,439 in 0.072s