Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding

Created on 2024-09-28T17:57:02-05:00

Return to the Index

This card pertains to a resource available on the internet.

This card can also be read via Gemini.

The "numerical system" is called asymmetric because the space is not divided in powers of two. Ranges are instead divided proportionally.

In a traditional arithmetic encoding table we would split the numbers up such that if 50% of an input is "x," then we take areas from 0 to 0.5 and dedicate it to "x." Then "zoom in" to this region and count the probability of symbols that occur directly after "x."

I think in rANS we do not necessarily do that; the given formulas have a single layer of context, though they do still work on the premise of arranging symbols in to "ranges" of allowed values based on popularity.

Like many compression techniques this is about selling out the least important symbols so the more important symbols can have shorter codes--and then hoping it all works out in the end.

"Streaming" rANS constrains state spaces to fit within a window and then bit buckets around the window to pretend to read and write numbers much larger than the system permits.

Last In First Out

Huffman

It appears huffman tables are still significantly faster once SIMD instructions are involved and capable of outputting multiple symbols per code.

I suspect this has to do with treating whole n-grams as symbols for huffman coding (which could also be done) or possibly some SIMD shenanigan where multiple codes are tabled together and read at once?

Fabian has interleaved rANS which can run multiple encoders simultaneously (but not one coder faster)