rANS achieves Shannon-limit lossless compression by encoding symbol streams into a single integer via reversible arithmetic, avoiding Huffman’s fixed-bit-width ceiling.
Key Takeaways
Huffman coding forces integer bit widths per symbol; rANS encodes fractional bits by scaling state x by M/f_s per symbol, converging to the Shannon limit asymptotically.
Core encode formula: x’ = floor(x/f_s)*M + c_s + (x mod f_s); decode inverts it with one mod, one table lookup, one division, and one multiply per symbol.
rANS is LIFO: encoders process input in reverse so decoders produce symbols in forward order.
Renormalization solves the unbounded-integer problem by spilling low-order base-b digits to a stream, keeping state in fixed range [L, bL) for b=2 (bit stream) or b=256 (byte stream).
The slot_to_symbol lookup table of size M gives O(1) symbol identification during decode, making per-symbol cost near-constant and suitable for performance-sensitive compressors.
