4 ms·
No way, that compression algorithm is amazing. But I also would like to understand how it works by someone explaining it really simply. I mean it's doing signi
by slowenough 7y ago
No way, that compression algorithm is amazing. But I also would like to understand how it works by someone explaining it really simply.
I mean it's doing significantly better than LZ. Anyone want to provide simple intuition on these algorithms and where they come from?
- yorwba 7y agoThe compression works by identifying repeating subsequences in the input data and picking the one that gives the best savings if replaced by a single byte not yet part of the input. This step requires time quadratic in the length of the input. After replacing the subsequence and tacking it onto the end so it can be recovered, the process continues until no repetition can be found or all possible bytes have been used. It can beat LZ's compression ratio for two reasons: 1. The input consists of only bytes that are valid in an URI, so it doesn't need an additional encoding step. 2. It gets very slow very quickly for larger inputs.
- KilledByAPixel 7y agoAlso, LZ beats it out for longer strings, but not by much for strings in the target range (~5000 characters).