Hacker News new | ask | show | jobs
by hexxagone 1766 days ago
Huffmann is rather simple and hard to beat in decompression speed.
2 comments
vardump 1766 days ago
For high entropy data (=somewhat random data), FSE is quite comparable to Huffman in compression speed.

For low entropy (lots of high probability symbols, like zeroes), Huffman is about 2-3x faster. But on the flipside, FSE achieves markedly higher compression ratio.

I think FSE is worth the speed tradeoff vs Huffman in most cases.

link
hexxagone 1766 days ago
"FSE achieves markedly higher compression ratio". I do not thin it is true, FSE/ANS achieves slightly better ratios in general. Zstd uses both Huffman (for large alphabets) and FSE (for small alphabets).
link
user-the-name 1766 days ago
Arithmetic coding is much, much simpler. And decompression speed is not a limiting factor in most applications of data compression like this.
link
hexxagone 1766 days ago
"Arithmetic coding is much, much simpler." Let us agree to disagree. "And decompression speed is not a limiting factor in most applications of data compression like this". It depends on the application. Zstd and Brotli are certainly aiming at the fastest decompression speed possible.
link
user-the-name 1766 days ago
Arithmetic coding can be implemented in as little as maybe ten lines of code. It is far simpler than Huffman coding.
link
hexxagone 1765 days ago
The Huffman encoding loop is 2 lines and decoding loop is 4 lines of branchless code. Do you have an example of branchless arithmetic encoder or decoder ?
link