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, long-term JPEG XL and learning-based JPEG AI image compressors.

The basic idea is to encode information into a single natural number

x

{\displaystyle x}

. In the standard binary number system, we can add a bit

s

∈

{

0

,

1

}

{\displaystyle s\in \{0,1\}}

of information to

x

{\displaystyle x}

by appending

s

{\displaystyle s}

at the end of

x

{\displaystyle x}

, which gives us

x

′

=

2

x

+

s

{\displaystyle x'=2x+s}

. For an entropy coder, this is optimal if

Pr

(

0

)

=

Pr

(

1

)

=

1

/

2

{\displaystyle \Pr(0)=\Pr(1)=1/2}

. ANS generalizes this process for arbitrary sets of symbols

s

∈

S

{\displaystyle s\in S}

with an accompanying probability distribution

(

p

s

)

s

∈

S

{\displaystyle (p_{s})_{s\in S}}

.