Lossless Compression with Asymmetric Numeral Systems (2020) (bjlkeng.io)

Asymmetric Numeral Systems (ANS), introduced by Jaroslaw Duda in 2009, is an entropy coding method that maps an entire message to a single natural number so that likely messages get small numbers and unlikely ones get large numbers. Like arithmetic coding, ANS can approach the Shannon entropy limit (-Σ p log2 p) but it does so with much simpler, faster integer operations. The basic binary version is just x_{i+1} = 2 x_i + b (and decoding recovers bits from parity), and ANS generalizes this by partitioning the natural-number space in proportions matching symbol probabilities so that encoding a symbol b roughly multiplies x by 1/p_b. This yields codes that consume about -log2 p_b bits per symbol and achieve near-optimal compression with efficient incremental encoding/decoding. For the AI/ML community, ANS matters because it provides high-throughput, low-overhead entropy coding useful for model and dataset compression, streaming of large probabilistic outputs, and efficient storage/transmission in data pipelines. Its blend of near-theoretical compression efficiency with practical speed is why major companies (Facebook, Apple, Google) integrated ANS into modern compressors since 2014. Key technical implications: ANS operates with exact integer arithmetic, supports adaptive and static probability models, decodes in reverse symbol order (but can be indexed for streaming), and often outperforms arithmetic coding in speed while matching its compression quality.