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
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
- The LIFO attribute of rANS comes from the streaming version proposed in the paper.
- Because a sliding window is used to contain the number, the lowest bits of the number are continuously shifted out to a bitstream during "renormalization." Reading the message then involves piping the high bits back in to the window and working to the lower bits.
- This is why rANS coding requires working in reverse.
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)