Asymmetric numeral systems (ANS)J. Duda, K. Tahboub, N. J. Gadil, E. J. Delp, The use of asymmetric numeral systems as an accurate replacement for Huffman coding, Picture Coding Symposium, 2015.J. Duda, Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding, arXiv:1311.2540, 2013. 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 compressorSmaller and faster data compression with Zstandard, Facebook, August 2016.5 ways Facebook improved compression at scale with Zstandard, Facebook, December 2018. (also used e.g. in Linux kernel,Zstd Compression For Btrfs & Squashfs Set For Linux 4.14, Already Used Within Facebook, Phoronix, September 2017. Google Chrome browser,New in Chrome 123 (Content-Encoding), Google, March 2024. Android operating system, was published as RFC 8478 for MIMEZstandard Compression and The application/zstd Media Type (email standard). and HTTPHypertext Transfer Protocol (HTTP) Parameters, IANA.), Apple LZFSE compressor,Apple Open-Sources its New Compression Algorithm LZFSE, InfoQ, July 2016. Google Draco 3D compressorGoogle Draco 3D compression library. (used e.g. in Pixar Universal Scene Description formatGoogle and Pixar add Draco Compression to Universal Scene Description (USD) Format .) and PIK image compressor,Google PIK: new lossy image format for the internet. CRAM DNA compressorCRAM format specification (version 3.0). from SAMtools utilities, NVIDIA nvCOMP high speed compression library,High Speed Data Compression Using NVIDIA GPUs. Dropbox DivANS compressor,Building better compression together with DivANS. Microsoft DirectStorage BCPack texture compressor,Microsoft DirectStorage overview. long-term JPEG XL and learning-based JPEG AI image compressors.
The basic idea is to encode information into a single natural number . In the standard binary number system, we can add a bit of information to by appending at the end of , which gives us . For an entropy coder, this is optimal if . ANS generalizes this process for arbitrary sets of symbols with an accompanying probability distribution . In ANS, if the information from is appended to to result in , then . Equivalently, , where is the number of bits of information stored in the number , and is the number of bits contained in the symbol .
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 into the information already stored in the current number , we go to number being the position of the -th appearance from the -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 going to infinity transferring accumulated bits to or from the bitstream.
Entropy coding 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 bits here instead of the original 1000 bits.
Generally, such sequences of length containing zeros and ones, for some probability , are called combinations. Using Stirling's approximation we get their asymptotic number being
called Shannon entropy.
Hence, to choose one such sequence we need approximately bits. It is still bits if , however, it can also be much smaller. For example, we need only bits for .
An entropy coder allows the encoding of a sequence of symbols using approximately the Shannon entropy bits per symbol. For example, ANS could be directly used to enumerate combinations: assign a different natural number to every sequence of symbols having fixed proportions in a nearly optimal way.
In contrast to encoding combinations, this probability distribution usually varies in data compressors. For this purpose, Shannon entropy can be seen as a weighted average: a symbol of probability contains bits of information. ANS encodes information into a single natural number , interpreted as containing bits of information. Adding information from a symbol of probability increases this informational content to . Hence, the new number containing both information should be .
Motivating examples Consider a source with 3 letters A, B, C, with probability 1/2, 1/4, 1/4. It is simple to construct the optimal prefix code in binary: A = 0, B = 10, C = 11. Then, a message is encoded as ABC -> 01011.
We see that an equivalent method for performing the encoding is as follows:
Start with number 1, and perform an operation on the number for each input letter. A = multiply by 2; B = multiply by 4, add 2; C = multiply by 4, add 3. Express the number in binary, then remove the first digit 1.
Consider a more general source with k letters, with rational probabilities . Then performing arithmetic coding on the source requires only exact arithmetic with integers.
In general, ANS is an approximation of arithmetic coding that approximates the real probabilities by rational numbers with a small denominator .
Basic concepts of ANS
Imagine there is some information stored in a natural number , for example as the bit sequence of its binary expansion. To add information from a binary variable , we can use the coding function , which shifts all bits one position up, and places the new bit in the least significant position. Now the decoding function allows one to retrieve the previous and this added bit: . We can start with initial state, then use the function on the successive bits of a finite bit sequence to obtain a final number storing this entire sequence. Then using the function multiple times until allows one to retrieve the bit sequence in reversed order.
The above procedure is optimal for the uniform (symmetric) probability distribution of symbols . ANS generalizes it to make it optimal for any chosen (asymmetric) probability distribution of symbols: . While in the above example was choosing between even and odd , in ANS this even/odd division of natural numbers is replaced with division into subsets having densities corresponding to the assumed probability distribution : up to position , there are approximately occurrences of symbol .
The coding function returns the -th appearance from such subset corresponding to symbol . The density assumption is equivalent to the condition . Assuming that a natural number contains bits of information, . Hence the symbol of probability is encoded as containing bits of information as is required from entropy coders.
Variants Uniform binary variant (uABS) Let us start with the binary alphabet and a probability distribution , . Up to position we want approximately analogues of odd numbers (for ). We can choose this number of appearances as , getting . This variant is called uABS and leads to the following decoding and encoding functions:Data Compression Explained, Matt Mahoney
Decoding: s = ceil((x+1)*p) - ceil(x*p) // 0 if fract(x*p) < 1-p, else 1 if s = 0 then new_x = x - ceil(x*p) // D(x) = (new_x, 0), this is the same as new_x = floor(x*(1-p)) if s = 1 then new_x = ceil(x*p) // D(x) = (new_x, 1)
Encoding: if s = 0 then new_x = ceil((x+1)/(1-p)) - 1 // C(x,0) = new_x if s = 1 then new_x = floor(x/p) // C(x,1) = new_x
For it amounts to the standard binary system (with 0 and 1 inverted), for a different it becomes optimal for this given probability distribution. For example, for these formulas lead to a table for small values of :
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 200123456789101112130123456
The symbol corresponds to a subset of natural numbers with density , which in this case are positions . As , these positions increase by 3 or 4. Because here, the pattern of symbols repeats every 10 positions.
The coding can be found by taking the row corresponding to a given symbol , and choosing the given in this row. Then the top row provides . For example, from the middle to the top row.
Imagine we would like to encode the sequence '0100' starting from . First takes us to , then to , then to , then to . By using the decoding function on this final , we can retrieve the symbol sequence. Using the table for this purpose, in the first row determines the column, then the non-empty row and the written value determine the corresponding and .
Range variants (rANS) and streaming The range variant also uses arithmetic formulas, but allows operation on a large alphabet. Intuitively, it divides the set of natural numbers into ranges of size , and splits each of them in an identical way into subranges with proportions given by the assumed probability distribution.
We start by quantizing the probability distribution into steps of , where is chosen (usually 8-12 bits): for some natural numbers (sizes of subranges).
Denote , and a cumulative distribution function:
Note here that the CDF[s] function is not a true CDF in that the current symbol's probability is not included in the expression's value. Instead, CDF[s] represents the total probability of all previous symbols. Example: Instead of the normal definition of CDF = f, it is evaluated as CDF = 0, since there are no previous symbols.
For denote the function (usually tabled)
symbol(y) = s such that CDF[s] <= y < CDF[s+1]
Now the coding function is:
C(x,s) = (floor(x / f[s]) << n) + (x % f[s]) + CDF[s]
Decoding:
s = symbol(x & mask) D(x) = (f[s] * (x >> n) + (x & mask ) - CDF[s], s)
This way we can encode a sequence of symbols into a large natural number . To avoid using large number arithmetic, in practice stream variants are used which enforce by renormalization: Sending the least significant bits of to or from the bitstream (usually and are powers of 2).
In the rANS variant, could be a 32 bit integer for example. For 16 bit renormalization (), the decoder refills the least significant bits from the bitstream when needed:
if (x < (1 << 16)) { x = (x << 16) + read16bits()
Tabled variant (tANS)
tANS variant puts the entire behavior (including renormalization) for into a table which yields a finite-state machine avoiding the need of multiplication.
Finally, the step of the decoding loop can be written as: t = decodingTable(x); x = t.newX + readBits(t.nbBits); //state transition writeSymbol(t.symbol); //decoded symbol
The step of the encoding loop: s = ReadSymbol(); nbBits = (x + ns[s]) >> r; // # of bits for renormalization writeBits(x, nbBits); // send the least significant bits to bitstream x = encodingTable[start[s] + (x >> nbBits)];
A specific tANS coding is determined by assigning a symbol to every position, their number of appearances should be proportional to the assumed probabilities. For example, one could choose "abdacdac" assignment for Pr(a)=3/8, Pr(b)=1/8, Pr(c)=2/8, Pr(d)=2/8 probability distribution. If symbols are assigned in ranges of lengths being powers of 2, we would get Huffman coding. For example, a->0, b->100, c->101, d->11 prefix code would be obtained for tANS with "aaaabcdd" symbol assignment.
Remarks