A tutorial on the range variant of asymmetric numeral systems

Abstract

This paper is intended to be a brief and accessible introduction to the range variant of asymmetric numeral systems (ANS), a system for lossless compression of sequences which can be used as a drop in replacement for arithmetic coding (AC). Because of the relative simplicity of ANS, we are able to provide enough mathematical detail to rigorously prove that ANS attains a compression rate close to the Shannon limit. Pseudo-code, intuitive interpretation and diagrams are given alongside the mathematical derivations. A working Python demo which accompanies this tutorial is available at https://raw.githubusercontent.com/j-towns/ans-notes/master/rans.py.

References in corpus (4)

• Asymmetric numeral systems
• Practical Lossless Compression with Latent Variables using Bits Back Coding
• Interleaved entropy coders
• Lightweight compression with encryption based on Asymmetric Numeral Systems

Cited by in corpus (5)

• IDF++: Analyzing and Improving Integer Discrete Flows for Lossless Compression
• Compressing Multisets with Large Alphabets using Bits-Back Coding
• Lossless compression with state space models using bits back coding
• Improving Lossless Compression Rates via Monte Carlo Bits-Back Coding
• Lossless Compression with Latent Variable Models