lzpm overview

[encode]

Okay, some details about the new engine:

This compressor uses a LZ77-PM compression – an LZ77 coder with some context related tricks (A younger brother of ROLZ2 ). It uses a Lazy Matching trick, so you can directly compare the listed results to the QUAD with Normal mode. The most important thing about this engine is that I finally implement a very tricky hashing. With hashing from QUAD, this engine is nearly 20...100 times slower . With the new scheme lzpm is fairly fast. The decompression is very fast on many files it is even faster than QUAD, however, I noticed that with large text files QUAD has a higher decompression speed. One important thing, with 16 MB buffer, lzpm needs just ~20 MB for decompression.

Memory usage
For compression: Hash table size (64 MB) + Buffer size (16 MB) + 4 MB + 256 KB
For decompression: Buffer size (16 MB) + 4 MB + 256 KB

Hash table size can vary. But I've found that 64 MB version provides good enough results – the compression becomes just slightly lower compared to the brute-force approach.

Buffer can be also variable sized. Check out some testing results:

ENWIK8
16 MB: 29,092,328 bytes
32 MB: 28,956,075 bytes
64 MB: 28,903,463 bytes

ENWIK9
16 MB: 253,267,637 bytes
32 MB: 252,030,819 bytes
64 MB: 251,300,786 bytes

PAK0.PAK
16 MB: 94,538,952 bytes
32 MB: 94,382,852 bytes
64 MB: 94,292,727 bytes

Overall, the 16 MB buffer is enough. Again, keeping in mind the low memory usage for decompression.

Okay, check out some other results with standard configuration (16 MB buffer + 64 MB hash table):

A10.jpg: 835,031 bytes

world95.txt: 613,849 bytes

acrord32.exe: 1,681,314 bytes (Note that lzpm has no E8/E9 transformer)

book1: 270,122 bytes

pht.psd: 1,271,658 byte

3200.txt: 5,065,137 bytes

The development in progress...

[Black_Fox1]

Cool!!

[Bulat Ziganshin]

im also working on lzh algo and things are even worser - optimum hash size is 1/16th of block size!

Overall, the 16 MB buffer is enough.

it depends on data and hash algo/size

[encode]

Note that lzpm stays in very early stage of development! I have many ideas for compression/speed improvements. (Better LZ-output coding, improved hashing, etc. etc.)
To be continued...

[encode]

Good news!

First, now I understand how LZMA gets such fast arithmetic compression/decompression - instead of keeping counters we directly modify the probabiliry of a next bit.

With my lzpm I've made different thing. I also use a bit-oriented coding.

With a new midification I use a precomputed tables for each probability - this trick doubles decompression speed - i.e. now lzpm is notable faster than QUAD at decompression and very close to the LZMA.

Furthermore, I changed the update rule for counters - making model more non stationary. As a result we have a higher binary compression, at the cost of slightly lower compression of text and precompressed files.