Asymmetric numeral systems

Asymmetric numeral systems (ANS) is a family of entropy encoding methods introduced by Jarosław (Jarek) Duda from Jagiellonian University, used in data compression since 2014 due to improved performance compared to previous methods. 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 (also used e.g. in Linux kernel, Google Chrome browser, Android operating system, was published as RFC 8478 for MIME and HTTP), Apple LZFSE compressor, Google Draco 3D compressor (used e.g. in Pixar Universal Scene Description format) and PIK image compressor, CRAM DNA compressor from SAMtools utilities, NVIDIA nvCOMP high speed compression library, Dropbox DivANS compressor, Microsoft DirectStorage BCPack texture compressor, and JPEG XL 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.

Suppose a sequence of 1,000 zeros and ones would be encoded, which would take 1000 bits to store directly. However, if it is somehow known that it only contains 1 zero and 999 ones, it would be sufficient to encode the zero's position, which requires only ${\displaystyle \lceil \log _{2}(1000)\rceil \approx 10}$ bits here instead of the original 1000 bits.

Generally, such sequences of length ${\displaystyle n}$ containing ${\displaystyle pn}$ zeros and ${\displaystyle (1-p)n}$ ones, for some probability ${\displaystyle p\in (0,1)}$, are called combinations. Using Stirling's approximation we get their asymptotic number being

called Shannon entropy.