Hacker News Reader

Comment by Waterluvian | Hacker News Reader

Did someone actually write that or did it come from a minified output?

I assume they minified it, but I don't have access to the unminified source. I'd like to clean it up or find a cleaner version, but for now it works well enough.

The article you linked above contains a partially unminified version.

EDIT: On second thought, you'd probably be better off using a completely different compression algorithm that doesn't sacrifice performance for golfability.

I do want to use that as reference if I ever decide to clean it up.

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?

The 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.

Also, LZ beats it out for longer strings, but not by much for strings in the target range (~5000 characters).

Reply on news.ycombinator.com