Asymmetric numeral systems

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (May 2017) (Learn how and when to remove this message)

Asymmetric numeral systems (ANS)^[1][2] is a family of entropy encoding methods introduced by Jarosław (Jarek) Duda^[3] from Jagiellonian University, used in data compression since 2014^[4] due to improved performance compared to previous methods.^[5] ANS combines the compression ratio of arithmetic coding (which uses a nearly accurate probability distribution), with a processing cost similar to that of Huffman coding. In the tabled ANS (tANS) variant, this is achieved by constructing a finite-state machine to operate on a large alphabet without using multiplication.

Among others, ANS is used in the Facebook Zstandard compressor^[6][7] (also used e.g. in Linux kernel,^[8] Google Chrome browser,^[9] Android^[10] operating system, was published as RFC 8478 for MIME^[11] and HTTP^[12]), Apple LZFSE compressor,^[13] Google Draco 3D compressor^[14] (used e.g. in Pixar Universal Scene Description format^[15]) and PIK image compressor,^[16] CRAM DNA compressor^[17] from SAMtools utilities,^[18] NVIDIA nvCOMP high speed compression library,^[19] Dropbox DivANS compressor,^[20] Microsoft DirectStorage BCPack texture compressor,^[21] and JPEG XL^[22] image compressor.

The basic idea is to encode information into a single natural number ${\displaystyle x}$. In the standard binary number system, we can add a bit ${\displaystyle s\in \{0,1\}}$ of information to ${\displaystyle x}$ by appending ${\displaystyle s}$ at the end of ${\displaystyle x}$, which gives us ${\displaystyle x'=2x+s}$. For an entropy coder, this is optimal if ${\displaystyle \Pr(0)=\Pr(1)=1/2}$. ANS generalizes this process for arbitrary sets of symbols ${\displaystyle s\in S}$ with an accompanying probability distribution ${\displaystyle (p_{s})_{s\in S}}$. In ANS, if the information from ${\displaystyle s}$ is appended to ${\displaystyle x}$ to result in ${\displaystyle x'}$, then ${\displaystyle x'\approx x\cdot p_{s}^{-1}}$. Equivalently, ${\displaystyle \log _{2}(x')\approx \log _{2}(x)+\log _{2}(1/p_{s})}$, where ${\displaystyle \log _{2}(x)}$ is the number of bits of information stored in the number ${\displaystyle x}$, and ${\displaystyle \log _{2}(1/p_{s})}$ is the number of bits contained in the symbol ${\displaystyle s}$.

For the encoding rule, the set of natural numbers is split into disjoint subsets corresponding to different symbols – like into even and odd numbers, but with densities corresponding to the probability distribution of the symbols to encode. Then to add information from symbol ${\displaystyle s}$ into the information already stored in the current number ${\displaystyle x}$, we go to number ${\displaystyle x'=C(x,s)\approx x/p}$ being the position of the ${\displaystyle x}$-th appearance from the ${\displaystyle s}$-th subset.

There are alternative ways to apply it in practice – direct mathematical formulas for encoding and decoding steps (uABS and rANS variants), or one can put the entire behavior into a table (tANS variant). Renormalization is used to prevent ${\displaystyle x}$ going to infinity – transferring accumulated bits to or from the bitstream.