Also-RANS: Asymmetric Numeral Systems for Entropy Coding
2 days ago
- #data compression
- #rANS
- #entropy coding
- rANS is an asymmetric numeral system used for lossless entropy coding by encoding symbol streams into a single integer via reversible arithmetic operations.
- It achieves nearly perfect compression by using variable-bit encoding per symbol, aligning with Shannon's information theory, unlike fixed-width methods like Huffman coding.
- The encoding process transforms a state integer using symbol frequency (f_s) and cumulative frequency (c_s), with the state growing by approximately the Shannon information content of each symbol.
- Decoding reverses the encoding by extracting the symbol from the state's low digits and reconstructing the previous state, operating in a last-in-first-out (LIFO) manner.
- Renormalization is used to manage state size by spilling low digits to a stream when the state exceeds a bound, ensuring practical implementation with fixed-width integers.
- The algorithm involves processing symbols in reverse during encoding and refilling the state from the stream during decoding, with efficient constant-time operations per symbol.