u/Specialist_Data_5403

Hello everyone!

I'd like to share my latest (and first in the field of compression) project being a new LZ77-based compressor. It is built around the idea that when looking for a match to, say, string "abc123456", the parser will find many places where data starts with "abcX", such that X is not "1", and very few places where data starts with "abc123".

lzmpo is memory-heavy because it builds hash chains which link positions where data of length X gives the same hash. Multiple chains are computed for each length from a list, and parser tries to find matches by jumping along these hash chains starting with the one that corresponds to the greatest length of the data hashed (as collisions in that chain are the least likely to happen).

My compressor is designed to work well with big files (like enwik9) yielding results that are comparable to zstd in terms of decompression speed (sitting at about 70-80% of it) but having much better ratios (20.4% vs 21.37% of zstd). As for the negatives, it uses about 50GB of RAM when compressing enwik9, and generally takes longer to finish.

UPD1: Core ideas used:

lzmpo operates on the entire file, which, when paired with the next ideas, allows it to reach good ratios. My calculations show that a substantial portion of the generated matches (35%) are at distances >10% of the file size, and about 15% of all matches are at distances >50% of the file size (tested on enwik).
lzmpo builds multiple hashchains for substrings for different lengths. When parser is looking for a match, it uses the chain that corresponds to the greatest length, which is more likely to result in a longer match.
lzmpo splits data into blocks which are then calcualted by threads.
Within each block, true optimal parsing is done: the parser collects all possible matches of length up to 256 for each position withing the block, and then proceedes to find the optimal coverage of the block with matches. My calculations show that limiting match length by 256 is not hurting the performance, as 99% of generated matches are of length <50 (when used with `-9` level). Note: when looking for matches, parser is NOT limited by the current block, it looks in the entire file history up to the current position.
Cost of a match is estimated in two ways: in the first pass, it is a simple heuristic. On subsequent passes, results of previous pass are used, and cost of a token is roughly its entropy according to the stream of tokens generated by the previous pass.
There are many entropy encoders supported, with the best one being Turbo-Range-Coder, but the second best one and the fastest one (in terms of decompression) being rans_static order0 avx2.

The project homepage is https://github.com/lis05/lzmpo, you can find the detailed explanation of how it works in the README.

Results on enwik9:

File: enwik9
────  ───────────  ─────────  ────────────  ────────  ────────────  ────────
Rank  Compressor   Ratio      C.Speed MB/s  C.Mem MB  D.Speed MB/s  D.Mem MB
────  ───────────  ─────────  ────────────  ────────  ────────────  ────────
*     lzmpo -9rc   20.07113%  0.18          51312.9   78.93         1556.8
1     lzmpo -9     20.40550%  0.18          51312.9   495.27        1559.9  
2     lzmpo -8     20.42281%  0.27          51312.9   496.24        1560.8  
3     lzmpo -7     20.46996%  0.43          51312.9   499.47        1561.8  
4     lzmpo -6     20.53418%  0.76          47498.2   507.15        1562.3  
5     lzmpo -5     20.55473%  0.86          47498.2   477.80        1563.1  
6     lzmpo -4     20.60857%  1.44          32880.9   500.05        1565.2  
7     lzmpo -3     20.99710%  2.66          29066.2   485.98        1578.7  
8     zstd -22     21.37212%  1.76          8669.9    638.34        215.7   
9     xz -9        21.56742%  5.36          5653.8    466.15        1528.2  
10    lzmpo -2     22.20778%  5.13          20040.4   465.42        1632.5  
11    brotli -q11  22.33457%  0.58          247.0     321.60        22.5    
12    lzmpo -1     23.20203%  8.16          20119.5   454.98        1677.4  
13    xz -5        23.68271%  19.21         3729.1    1047.92       1137.3  
14    zstd -18     23.95552%  11.59         1698.5    969.48        151.4   
15    brotli -q9   25.17618%  3.68          128.6     349.06        22.8    
16    lzmpo -0     26.13254%  16.88         12858.7   435.32        1827.6

I would appreciate some feedback and just general thoughts / suggestions. While not a practical compressor, I think it could be used as a decompressor without big sacrifices.

Best regards.

(original thread on encode.su: https://encode.su/threads/4513-lzmpo-memory-heavy-LZ77-compressor)

Platform(s): Android

Genre: Dungeon crawler

Estimated year of release: Hard to say, but I played it during the 2010s

Graphics/art style: Simple pixelated 2d graphics. Clean, rather few details.

Notable characters: I clearly remember there being a slime enemy (in the first level). Also, in the winter themed level there was a Yeti / some other big white boss. There also were skeletons, I think.

Notable gameplay mechanics:
You had to traverse dungeons (maybe more than 1) and clear out the enemies. There were areas where you could buy new gear: swords, spears, bows, longbows, armor sets, shields, food (which healed the character, like apples, bread, pies?). I think there were several levels of gear, like wooden/basic, iron/steel, etc.

The end of each level ended with a boss fight. The fighting system was rather simple: you could press a button and shoot / hit with your weapon, same goes for the enemies. You could move freely.

The levels were themed (e.g. summer themed, underground themed, winter themed, etc) and an important element of those were ladders which you could use to climb. I also think gear areas were located in these levels, and were sort of a safe room.

Other details:
Don't remember.

lzmpo - memory-heavy LZ77 compressor

[Android][2010 - ????] 2D Dungeon crawler platformer with gear areas and food