Hacker News Reader

For optimal compression, look into Huffman coding: https://en.wikipedia.org/wiki/Huffman_coding

I mention Huffman in my follow-up post: https://mbuffett.com/posts/compressing-chess-moves-even-furt... , but chose arithmetic encoding instead.

I think Huffman would be good, but I don't think it would be optimal (as in, the smallest possible amount of bits)

Huffman requires minimum one bit IIRC whereas Arithmetic coding or ANS ( https://en.wikipedia.org/wiki/Asymmetric_numeral_systems ) can use fewer if there's a skewed distribution.

Arithmetic coding has been avoided in practical situations due to patents, but many of those have expired ( see the patent section of https://en.wikipedia.org/wiki/Arithmetic_coding or maybe not, lawyers tend to advise not even reading about patent specifics )

The core tech patents have expired. They did have some interesting ones around hardware implementations, iirc.

Overall the chilling effect was interesting - I found that many people doing academic work around compression didn't really know much about it, didn't teach it, just because it was a mess.

The core idea is elegant, and easily implemented.

Reply on news.ycombinator.com