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 previously used methods, being up to 30 times faster. 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, 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, Dropbox DivANS compressor, and JPEG XL image compressor. The basic idea is to encode information into a single natural number formula_1. In the standard binary number system, we can add a bit formula_2 of information to formula_1 by appending formula_4 at the end of formula_1, which gives us formula_6. For an entropy coder, this is  optimal if formula_7. ANS generalizes this process for arbitrary sets of symbols formula_8 with an accompanying probability distribution formula_9. In ANS, if the information from formula_4 is appended to formula_1 to result in formula_12, then formula_13. Equivalently, formula_14, where formula_15 is the number of bits of information stored in the number formula_1, and formula_17 is the number of bits contained in the symbol formula_4. 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 formula_4 into the information already stored in the current number formula_1, we go to number formula_21 being the position of the formula_1-th appearance from the formula_4-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 formula_1 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 formula_25 bits here instead of the original 1000 bits. Generally, such length formula_26 sequences containing formula_27 zeros and formula_28 ones, for some probability formula_29, 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 formula_31 bits. It is still formula_26 bits if formula_33, however, it can also be much smaller . For example, we need only formula_34 bits for formula_35. 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 formula_36 contains formula_37 bits of information. ANS encodes information into a single natural number formula_1 , interpreted as containing formula_15 bits of information. Adding information from a symbol of probability formula_36 increases this informational content to formula_41. Hence, the new number containing both information should be formula_42. Basic concepts of ANS. Imagine there is some information stored in a natural number formula_1, for example as bit sequence of its binary expansion. To add information from a binary variable formula_4, we can use coding function formula_45, which shifts all bits one position up, and place the new bit in the least significant position. Now decoding function formula_46 allows one to retrieve the previous formula_1 and this added  bit: formula_48. We can start with formula_49 initial state, then use the formula_50 function on the successive bits of a finite bit sequence to obtain a final formula_1 number storing this entire sequence. Then using formula_52 function multiple times until formula_49 allows one to retrieve the bit sequence in reversed order. The above procedure is optimal for the uniform (symmetric) probability distribution of symbols formula_54. ANS generalize it to make it optimal for any chosen (asymmetric) probability distribution of symbols: formula_55. While formula_4 in the above example was choosing between even and odd formula_57, in ANS this even/odd division  of natural numbers is replaced with division into subsets having densities corresponding to the assumed probability distribution formula_58: up to position formula_1, there are approximately formula_60 occurrences of symbol formula_4. The coding function formula_62 returns the formula_1-th appearance from such subset corresponding to symbol formula_64. The density assumption is equivalent to condition formula_65. Assuming that a natural number formula_66 contains formula_67 bits information, formula_68. Hence the symbol of probability formula_69 is encoded as containing formula_70 bits of information as it is required from entropy coders. Uniform binary variant (uABS). Let us start with the binary alphabet and a probability  distribution formula_71, formula_72. Up to position formula_66 we want approximately formula_74 analogues of odd numbers (for formula_75). We can choose this number of appearances as formula_76, getting formula_77. This variant is called "uABS" and leads to the following decoding and encoding functions: 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 formula_33 it amounts to the standard binary system (with 0 and 1 inverted), for a different formula_36 it becomes optimal for this given probability distribution. For example, for formula_80 these formulas lead to a table for small values of formula_1: The symbol formula_82 corresponds to a subset of natural numbers with density formula_80, which in this case are positions formula_84. As formula_85, these positions increase by 3 or 4. Because formula_86 here, the pattern of symbols repeats every 10 positions. The coding formula_57 can  be found by taking the row corresponding to a given symbol formula_4, and choosing the given formula_1 in this row. Then the top row provides formula_57. For example, formula_91 from the middle to the top row. Imagine we would like to encode the sequence '0100' starting from formula_49. First formula_93 takes us to formula_94, then formula_82 to formula_96, then formula_93 to formula_98, then formula_93 to formula_100. By using the decoding function formula_101 on this final formula_1, we can retrieve the symbol sequence. Using the table for this purpose, formula_1 in the first row determines the column, then the non-empty  row and the written value determine the corresponding formula_4 and formula_1. 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 size formula_106 ranges, and split each of them in identical way into subranges of proportions given by the assumed probability distribution. We start with quantization of probability distribution to formula_106 denominator, where is chosen (usually 8-12 bits): formula_108 for some natural formula_109 numbers (sizes of subranges). Denote formula_110, and a cumulative distribution function: symbol(y) = s such that CDF[s] < = y < CDF[s+1] Now 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 formula_112 by renormalization: sending the least significant bits of to or from the bitstream (usually and are powers of 2). In rANS variant is for example 32 bit. For 16 bit renormalization, formula_113, 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 formula_114 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 formula_115 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. As for Huffman coding, modifying the probability distribution of tANS is relatively costly, hence it is mainly used in static situations, usually with some Lempel –Ziv scheme (e.g. ZSTD, LZFSE). In this case, the file is divided into blocks - for each of them symbol frequencies are independently counted, then after approximation (quantization) written in the block header and used as static probability distribution for tANS. In contrast, rANS is usually used as a faster replacement for range coding (e.g. CRAM, LZNA, Draco,). It requires multiplication, but is more memory efficient and is appropriate for dynamically adapting probability distributions. Encoding and decoding of ANS are performed in opposite directions, making it a stack for symbols. This inconvenience is usually resolved by encoding in backward direction, after  which decoding can be done forward. For context-dependence, like Markov model, the encoder needs to use context from the perspective of later decoding. For adaptivity, the encoder should first go forward to find probabilities which will be used (predicted) by decoder and store them in a buffer, then encode in backward direction using the buffered probabilities. The final state of encoding is required to start decoding, hence it needs to be stored in the compressed file. This cost can be compensated by storing some information in the initial state of encoder. For example, instead of starting with "10000" state , start with "1****" state, where "*" are some additional stored bits, which can be retrieved at the end of the decoding. Alternatively, this state can be used as a checksum by starting encoding with a fixed state, and testing if the final state of decoding is the expected one. Patent controversy. The author of the novel ANS algorithm and its variants tANS and rANS specifically intended his work to be available freely in the public domain, for altruistic reasons. He has not sought to profit from them and took steps to ensure they would not become a "legal minefield", or restricted  by, or profited from by others. In 2015, Google published a US and then worldwide patent for "Mixed boolean-token ans coefficient coding". At the time, Professor Duda had been asked by Google to help it with video compression, so was intimately aware of this domain, having the original author assisting them. Duda was not pleased by (accidentally) discovering Google's patent intentions, given he had been clear he wanted it as public domain, and had assisted Google specifically on that basis. Duda subsequently filed a third-party application to the US Patent office seeking a rejection. The USPTO rejected  its application in 2018, and Google subsequently abandoned the patent. In June 2019 Microsoft lodged a patent application called "Features of range asymmetric number system encoding and decoding". The USPTO issued a final rejection of the application on October 27, 2020. Yet on March 2, 2021, Microsoft gave a USPTO explanatory filing stating "The Applicant respectfully disagrees with the rejections.", seeking to overturn the final rejection under the "After Final Consideration Pilot 2.0" program. After reconsideration, the USPTO granted the application on January 25, 2022.