Asymmetric Numeral Systems

Asymmetric Numeral Systems (ANS) is a family of entropy coding methods introduced by Jarosław (Jarek) Duda, used in data compression since 2014 due to improved performance compared to the previously used methods. ANS combines the compression ratio of arithmetic coding (which uses 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, in the Apple LZFSE compressor,Google Draco 3D compressor, in CRAM DNA compressor from popular SAMtools utilities and is considered for AV1 open video coding format from Alliance for Open Media.

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 ${\displaystyle x'}$ is the result of appending the information from ${\displaystyle s}$ to ${\displaystyle x}$, then ${\displaystyle x'\approx x/p_{s}}$. Equivalently, ${\displaystyle \log _{2}(x')\approx \log _{2}(x)+\log _{2}(1/p_{s})}$, where ${\displaystyle \log _{2}(x)}$ is the amount of bits of information stored in number ${\displaystyle x}$ and ${\displaystyle \log _{2}(1/p_{s})}$ is the amount of bits contained in symbol ${\displaystyle s}$.

...
Wikipedia