View source for Asymmetric numeral systems

{{Short description|Entropy coding methods}}
{{More footnotes needed|date=May 2017}}
{{Numeral systems}}
'''Asymmetric numeral systems''' ('''ANS''')<ref name=PCS2015>J. Duda, K. Tahboub, N. J. Gadil, E. J. Delp, [https://ieeexplore.ieee.org/document/7170048/ ''The use of asymmetric numeral systems as an accurate replacement for Huffman coding''], Picture Coding Symposium, 2015.</ref><ref name="Duda2013">J. Duda, [https://arxiv.org/abs/1311.2540 ''Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding''], arXiv:1311.2540, 2013.</ref> is a family of [[entropy encoding]] methods introduced by [[Jarosław Duda (computer scientist)|Jarosław (Jarek) Duda]]<ref>{{cite web |url=http://th.if.uj.edu.pl/~dudaj/ |title=Dr Jarosław Duda (Jarek Duda) |website=Institute of Theoretical Physics |publisher=Jagiellonian University in Krakow |access-date=2021-08-02}}</ref> from [[Jagiellonian University]], used in [[data compression]] since 2014<ref name=list>{{cite web
 |url=https://encode.su/threads/2078-List-of-Asymmetric-Numeral-Systems-implementations
 |title=List of compressors using ANS, implementations and other materials
 |last=Duda |first=Jarek |date=October 6, 2019  |access-date=October 6, 2019}}</ref> due to improved performance compared to previous methods.<ref name="blANS">{{cite web |url=https://www.bleepingcomputer.com/news/google/google-accused-of-trying-to-patent-public-domain-technology/ |title=Google Accused of Trying to Patent Public Domain Technology  |work=[[Bleeping Computer]] |date=September 11, 2017}}</ref> 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<ref name=ZSTD>[https://code.facebook.com/posts/1658392934479273/smaller-and-faster-data-compression-with-zstandard/ ''Smaller and faster data compression with Zstandard''], Facebook, August 2016.</ref><ref name=ZSTD1>[https://code.fb.com/core-data/zstandard/ ''5 ways Facebook improved compression at scale with Zstandard''], Facebook, December 2018.</ref> (also used e.g. in [[Linux]] kernel,<ref name=Linux>[https://www.phoronix.com/scan.php?page=news_item&px=Linux-4.14-Zstd-Pull ''Zstd Compression For Btrfs & Squashfs Set For Linux 4.14, Already Used Within Facebook''], Phoronix, September 2017.</ref> [[Google Chrome]] browser,<ref name=Chrome>[https://developer.chrome.com/blog/new-in-chrome-123 ''New in Chrome 123 (Content-Encoding)''], Google, March 2024.</ref> [[Android (operating system)|Android]]<ref>{{cite web |url=https://android.googlesource.com/kernel/common/+/refs/heads/android-4.14-p-release/fs/btrfs/zstd.c |title=Zstd in Android P release |access-date=2019-05-29 |archive-date=2020-08-26 |archive-url=https://web.archive.org/web/20200826023340/https://android.googlesource.com/kernel/common/+/refs/heads/android-4.14-p-release/fs/btrfs/zstd.c |url-status=dead }}</ref> operating system, was published as RFC&nbsp;8478 for [[MIME]]<ref name=MIME>[https://datatracker.ietf.org/doc/draft-kucherawy-dispatch-zstd/ ''Zstandard Compression and The application/zstd Media Type (email standard)''].</ref> and [[HTTP]]<ref name=HTTP>[https://www.iana.org/assignments/http-parameters/http-parameters.xhtml ''Hypertext Transfer Protocol (HTTP) Parameters''], [[IANA]].</ref>), [[Apple Inc.|Apple]] [[LZFSE]] compressor,<ref name=LZFSE>[https://www.infoq.com/news/2016/07/apple-lzfse-lossless-opensource ''Apple Open-Sources its New Compression Algorithm LZFSE''], InfoQ, July 2016.</ref> [[Google]] Draco 3D compressor<ref name=Draco>[https://github.com/google/draco ''Google Draco 3D compression library''].</ref> (used e.g. in [[Pixar]] [[Universal Scene Description]] format<ref name=Pixar>[https://opensource.googleblog.com/2019/11/google-and-pixar-add-draco-compression.html ''Google and Pixar add Draco Compression to Universal Scene Description (USD) Format ''].</ref>) and PIK image compressor,<ref name=PIK>[https://github.com/google/pik ''Google PIK: new lossy image format for the internet''].</ref> [[CRAM (file format)|CRAM]] DNA compressor<ref name=CRAM>[https://samtools.github.io/hts-specs/CRAMv3.pdf ''CRAM format specification (version 3.0)''].</ref> from [[SAMtools]] utilities,<ref name="pmid34590992">{{cite journal| author=Chen W, Elliott LT| title=Compression for population genetic data through finite-state entropy. | journal=J Bioinform Comput Biol | year= 2021 | volume=  19| issue=  5| pages= 2150026 | pmid=34590992 | doi=10.1142/S0219720021500268 | pmc= | doi-access=free }}</ref> 
[[NVIDIA]] nvCOMP high speed compression library,<ref name=nvCOMP>[https://developer.nvidia.com/nvcomp ''High Speed Data Compression Using NVIDIA GPUs''].</ref>
[[Dropbox (service)|Dropbox]] DivANS compressor,<ref name=DivANS>[https://blogs.dropbox.com/tech/2018/06/building-better-compression-together-with-divans/ ''Building better compression together with DivANS''].</ref> [[Microsoft]] [[DirectStorage]] BCPack texture compressor,<ref name=BCPack>[https://docs.microsoft.com/en-us/gaming/gdk/_content/gc/system/overviews/directstorage/directstorage-overview ''Microsoft DirectStorage overview''].</ref> and [[JPEG XL]]<ref name=jpegxl_committeedraft>{{cite arXiv |title=Committee Draft of JPEG XL Image Coding System |eprint = 1908.03565 |last1 = Rhatushnyak |first1 = Alexander |last2 = Wassenberg |first2 = Jan |last3 = Sneyers |first3 = Jon |last4 = Alakuijala |first4 = Jyrki |last5 = Vandevenne |first5 = Lode |last6 = Versari |first6 = Luca |last7 = Obryk |first7 = Robert |last8 = Szabadka |first8 = Zoltan |last9 = Kliuchnikov |first9 = Evgenii |last10 = Comsa |first10 = Iulia-Maria |last11 = Potempa |first11 = Krzysztof |last12 = Bruse |first12 = Martin |last13 = Firsching |first13 = Moritz |last14 = Khasanova |first14 = Renata |author15 = Ruud van Asseldonk |last16 = Boukortt |first16 = Sami |last17 = Gomez |first17 = Sebastian |last18 = Fischbacher |first18 = Thomas |class = eess.IV |year = 2019}}</ref> image compressor.

The basic idea is to encode information into a single natural number <math>x</math>. In the standard binary number system, we can add a bit <math>s \in \{0, 1\}</math> of information to <math>x</math> by appending <math>s</math> at the end of <math>x</math>, which gives us <math>x' = 2x + s</math>. For an entropy coder, this is optimal if <math>\Pr(0) = \Pr(1) = 1/2</math>. ANS generalizes this process for arbitrary sets of symbols <math>s \in S</math> with an accompanying probability distribution <math>(p_s)_{s \in S}</math>. In ANS, if the information from <math>s</math> is appended to <math>x</math> to result in <math>x'</math>, then <math>x' \approx x \cdot p_s^{-1}</math>. Equivalently, <math>\log_2(x') \approx \log_2(x) + \log_2(1/p_s)</math>, where <math>\log_2(x)</math> is the number of bits of information stored in the number <math>x</math>, and <math>\log_2(1/p_s)</math> is the number of bits contained in the symbol <math>s</math>.

For the encoding rule, the set of natural numbers is split into disjoint subsets corresponding to different symbols{{snd}} 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 <math>s</math> into the information already stored in the current number <math>x</math>, we go to number <math>x' = C(x, s) \approx x/p</math> being the position of the <math>x</math>-th appearance from the <math>s</math>-th subset.

There are alternative ways to apply it in practice{{snd}} 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 <math>x</math> going to infinity{{snd}} 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 <math>\lceil \log_2(1000)\rceil \approx 10</math> bits here instead of the original 1000 bits.

Generally, such sequences of length <math>n</math> containing <math>pn</math> zeros and <math>(1-p)n</math> ones, for some probability <math>p\in(0,1)</math>, are called [[combinations]]. Using [[Stirling's approximation]] we get their asymptotic number being

: <math>{n \choose pn }\approx 2^{nh(p)} \text{ for large } n \text{ and } h(p) =-p \log_2(p)-(1-p)\log_2(1-p), </math>

called [[Entropy (information theory)|Shannon entropy]].

Hence, to choose one such sequence we need approximately <math>n h(p)</math> bits. It is still <math>n</math> bits if <math>p=1/2</math>, however, it can also be much smaller. For example, we need only <math>\approx n/2</math> bits for <math>p = 0.11</math>.

An [[Entropy encoding|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 <math>p</math> contains <math>\log_2(1/p)</math> bits of information. ANS encodes information into a single natural number <math>x</math>, interpreted as containing <math>\log_2(x)</math> bits of information. Adding information from a symbol of probability <math>p</math> increases this informational content to <math>\log_2(x)+\log_2(1/p)=\log_2(x/p)</math>. Hence, the new number containing both information should be <math>x'\approx x/p </math>.

=== 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 <math>n_1/N, ..., n_k/N</math>. 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 <math>r_1, ..., r_k</math> by rational numbers <math>n_1/N, ..., n_k/N</math> with a small denominator <math>N</math>.

== Basic concepts of ANS ==
[[Image:ANS_general_picture.png|thumb|640px|right|Comparison of the concept of [[arithmetic coding]] (left) and ANS (right). Both can be seen as generalizations of standard numeral systems, optimal for uniform probability distribution of digits, into optimized for some chosen probability distribution. Arithmetic or range coding corresponds to adding new information in the most significant position, while ANS generalizes adding information in the least significant position. Its coding rule is "''x'' goes to ''x''-th appearance of subset of natural numbers corresponding to currently encoded symbol". In the presented example, sequence (01111) is encoded into a natural number 18, which is smaller than 47 obtained by using standard binary system, due to better agreement with frequencies of sequence to encode. The advantage of ANS is storing information in a single natural number, in contrast to two defining a range.]]
Imagine there is some information stored in a natural number <math>x</math>, for example as bit sequence of its binary expansion. To add information from a binary variable <math>s</math>, we can use coding function <math>x'=C(x,s) = 2x + s </math>, which shifts all bits one position up, and place the new bit in the least significant position. Now decoding function <math>D(x')=(\lfloor x'/2 \rfloor, \mathrm{mod}(x',2))</math> allows one to retrieve the previous <math>x</math> and this added bit: <math>D(C(x,s))=(x,s),\ C(D(x'))=x'</math>. We can start with <math>x=1</math> initial state, then use the <math>C</math> function on the successive bits of a finite bit sequence to obtain a final <math>x</math> number storing this entire sequence. Then using <math>D</math> function multiple times until <math>x=1</math> allows one to retrieve the bit sequence in reversed order.

The above procedure is optimal for the uniform (symmetric) probability distribution of symbols <math>\Pr(0)=\Pr(1)=1/2</math>. ANS generalize it to make it optimal for any chosen (asymmetric) probability distribution of symbols: <math>\Pr(s)=p_s</math>. While <math>s</math> in the above example was choosing between even and odd <math>C(x,s)</math>, in ANS this even/odd division of natural numbers is replaced with division into subsets having densities corresponding to the assumed probability distribution <math>\{p_s\}_s</math>: up to position <math>x</math>, there are approximately <math>x p_s</math> occurrences of symbol <math>s</math>.

The coding function <math> C(x,s)</math> returns the <math>x</math>-th appearance from such subset corresponding to symbol <math> s</math>. The density assumption is equivalent to condition <math> x'=C(x,s) \approx x / p_s </math>. Assuming that a natural number <math> x </math> contains <math> \log_2(x) </math> bits of information, <math> \log_2(C(x,s)) \approx \log_2(x) + \log_2(1/ p_s) </math>. Hence the symbol of probability <math> p_s </math> is encoded as containing <math> \approx\log_2(1/ p_s) </math> bits of information as it is required from [[Entropy encoding|entropy coders]].

== Variants ==
=== Uniform binary variant (uABS) ===
Let us start with the binary alphabet and a probability distribution <math> \Pr(1) = p</math>, <math>\Pr(0)=1-p </math>. Up to position <math> x </math> we want approximately <math> p\cdot x </math> analogues of odd numbers (for <math>s = 1</math>). We can choose this number of appearances as <math>\lceil x\cdot p \rceil</math>, getting <math>s = \lceil (x+1)\cdot p \rceil - \lceil x\cdot p \rceil </math>. This variant is called ''uABS'' and leads to the following decoding and encoding functions:<ref name=uABS>[http://mattmahoney.net/dc/dce.html#Section_33 Data Compression Explained], Matt Mahoney</ref>

Decoding:
<syntaxhighlight lang="csharp">
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)</syntaxhighlight>

Encoding:
<syntaxhighlight lang="csharp">
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 </syntaxhighlight>

For <math>p=1/2</math> it amounts to the standard binary system (with 0 and 1  inverted), for a different <math>p</math> it becomes optimal for this given probability distribution. For example, for <math>p=0.3</math> these formulas lead to a table for small values of <math>x</math>:

{| class="wikitable" align="center"
|-
! <math>C(x,s) </math>
! 0
! 1
! 2
! 3
! 4
! 5
! 6
! 7
! 8
! 9
! 10
! 11
! 12
! 13
! 14
! 15
! 16
! 17
! 18
! 19
! 20
|-
|align="right"|<math>s=0 </math>
|align="right"|
|align="right"|0
|align="right"|1
|align="right"|
|align="right"|2
|align="right"|3
|align="right"|
|align="right"|4
|align="right"|5
|align="right"|6
|align="right"|
|align="right"|7
|align="right"|8
|align="right"|
|align="right"|9
|align="right"|10
|align="right"|
|align="right"|11
|align="right"|12
|align="right"|13
|align="right"|
|-
|align="right"|<math>s=1 </math>
|align="right"|0
|align="right"|
|align="right"|
|align="right"|1
|align="right"|
|align="right"|
|align="right"|2
|align="right"|
|align="right"|
|align="right"|
|align="right"|3
|align="right"|
|align="right"|
|align="right"|4
|align="right"|
|align="right"|
|align="right"|5
|align="right"|
|align="right"|
|align="right"|
|align="right"|6
|}
 
The symbol <math>s=1</math> corresponds to a subset of natural numbers with density <math>p=0.3</math>, which in this case are positions <math>\{0,3,6,10,13,16,20,23,26,\ldots\}</math>. As <math>1/4< 0.3 < 1/3</math>, these positions increase by 3 or 4. Because <math>p=3/10</math> here, the pattern of symbols repeats every 10 positions.

The coding <math>C(x,s)</math> can be found by taking the row corresponding to a given symbol <math>s</math>, and choosing the given <math>x</math> in this row. Then the top row provides <math>C(x,s)</math>. For example, <math>C(7,0)=11 </math> from the middle to the top row.

Imagine we would like to encode the sequence '0100' starting from <math>x=1</math>. First <math>s=0</math> takes us to <math>x=2</math>, then <math>s=1</math> to <math>x=6</math>, then <math>s=0</math> to <math>x=9</math>, then <math>s=0</math> to <math>x=14</math>. By using the decoding function <math>D(x')</math> on this final <math>x</math>, we can retrieve the symbol sequence. Using the table for this purpose, <math>x</math> in the first row determines the column, then the non-empty row and the written value determine the corresponding <math>s</math> and <math>x</math>.

=== 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 <math>2^n</math> 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 <math>2^n</math> denominator, where {{mvar|n}} is chosen (usually 8-12 bits): <math>p_s \approx f[s]/2^n</math> for some natural <math>f[s]</math> numbers (sizes of subranges).

Denote <math>\text{mask} = 2^n-1</math>, and a cumulative distribution function:

: <math>\operatorname{CDF}[s] = \sum_{i<s} f[i] =f[0]+ \cdots +f[s-1].</math>

Note here that the 
<syntaxhighlight lang="c" inline>CDF[s]</syntaxhighlight> function is not a true [[Cumulative distribution function#Definition|CDF]] in that the current symbol's probability is not included in the expression's value. Instead, the <syntaxhighlight lang="c" inline>CDF[s]</syntaxhighlight> represents the total probability of all previous symbols. Example: Instead of the normal definition of <syntaxhighlight lang="c" inline>CDF[0] = f[0]</syntaxhighlight>, it is evaluated as <syntaxhighlight lang="c" inline>CDF[0] = 0</syntaxhighlight>, since there are no previous symbols.

For <math>y\in[0,2^n-1]</math> denote function (usually tabled)

<syntaxhighlight lang="c">symbol(y) = s  such that  CDF[s] <= y < CDF[s+1] </syntaxhighlight>

Now coding function is:

<syntaxhighlight lang="c">C(x,s) = (floor(x / f[s]) << n) + (x % f[s]) + CDF[s] </syntaxhighlight>

Decoding: <syntaxhighlight lang="c" inline> s = symbol(x & mask) </syntaxhighlight>

<syntaxhighlight lang="c">D(x) = (f[s] * (x >> n) + (x & mask ) - CDF[s], s) </syntaxhighlight>

This way we can encode a sequence of symbols into a large natural number {{mvar|x}}. To avoid using large number arithmetic, in practice stream variants are used: which enforce <math> x\in [L, b \cdot L-1] </math> by renormalization: sending the least significant bits of {{mvar|x}} to or from the bitstream (usually {{mvar|L}} and {{mvar|b}} are powers of 2).

In rANS variant {{mvar|x}} is for example 32 bit. For 16 bit renormalization, <math> x\in [2^{16},2^{32}-1]</math>, decoder refills the least significant bits from the bitstream when needed:

<syntaxhighlight lang="c">if(x < (1 << 16)) x = (x << 16) + read16bits() </syntaxhighlight>

=== {{anchor|tANS}}Tabled variant (tANS) ===
[[Image:Simple example of ANS automaton.png |thumb|480px|right|Simple example of 4 state ANS automaton for Pr(''a'')&nbsp;=&nbsp;3/4, Pr(''b'')&nbsp;=&nbsp;1/4 probability distribution. Symbol ''b'' contains −lg(1/4)&nbsp;=&nbsp;2 bits of information and so it always produces two bits. In contrast, symbol ''a'' contains −lg(3/4)&nbsp;~&nbsp;0.415 bits of information, hence sometimes it produces one bit (from state 6 and 7), sometimes 0 bits (from state 4 and 5), only increasing the state, which acts as buffer containing fractional number of bits: lg(''x''). The number of states in practice is for example 2048, for 256 size alphabet (to directly encode bytes).]]
tANS variant puts the entire behavior (including renormalization) for <math>x\in[L,2L-1]</math> 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:
<syntaxhighlight lang="csharp">t = decodingTable(x);  
x = t.newX + readBits(t.nbBits); //state transition
writeSymbol(t.symbol); //decoded symbol </syntaxhighlight>

The step of the encoding loop:
<syntaxhighlight lang="csharp">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)]; </syntaxhighlight>

A specific tANS coding is determined by assigning a symbol to every <math>[L,2L-1]</math> 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.

[[Image:TANSex.png|thumb|640px|center|Example of generation of tANS tables for m = 3 size alphabet and L = 16 states, then applying them for stream decoding. First we approximate probabilities using fraction with denominator being the number of states. Then we spread these symbols in nearly uniform way, optionally the details may depend on cryptographic key for simultaneous encryption. Then we enumerate the appearances starting with value being their amount for a given symbol. Then we refill the youngests bits from the stream to return to the assumed range for x (renormalization).]]

== 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 [[LZ77 and LZ78|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 encoding|range coding]] (e.g. [[CRAM (file format)|CRAM]], LZNA, Draco,<ref name=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 (abstract data type)|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".<ref>{{cite web |title=Mixed boolean-token ans coefficient coding |url=https://patents.google.com/patent/US20170164007 |access-date=14 June 2021}}</ref> 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<ref>{{cite web |title=Protest to Google |url=http://th.if.uj.edu.pl/~dudaj/protestGoogle.pdf |website=Institute of Theoretical Physics. Jagiellonian University in Krakow Poland |publisher=Professor Jarosław Duda}}</ref> to the US Patent office seeking a rejection. The USPTO rejected its application in 2018, and Google subsequently abandoned the patent.<ref>{{cite web |title=After Patent Office Rejection, It is Time For Google To Abandon Its Attempt to Patent Use of Public Domain Algorithm |date=30 August 2018 |url=https://www.eff.org/deeplinks/2018/08/after-patent-office-rejection-it-time-google-abandon-its-attempt-patent-use-public |publisher=EFF}}</ref>

In June 2019 Microsoft lodged a patent application called "Features of range asymmetric number system encoding and decoding".<ref>{{cite web |title=Features of range asymmetric number system encoding and decoding |url=https://patents.google.com/patent/US20200413106A1 |access-date=14 June 2021}}</ref> 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.",<ref>{{cite web |title=Third time's a harm? Microsoft tries to get twice-rejected compression patent past skeptical examiners |url=https://www.theregister.com/2021/03/13/microsoft_ans_patent/ |publisher=The Register |access-date=14 June 2021}}</ref> seeking to overturn the final rejection under the "After Final Consideration Pilot 2.0" program.<ref>{{cite web |title=After Final Consideration Pilot 2.0 |url=https://www.uspto.gov/patents/initiatives/after-final-consideration-pilot-20 |website=United States Patent and Trademark Office |access-date=14 June 2021}}</ref> After reconsideration, the USPTO granted the application on January 25, 2022.<ref>{{cite web |title=Features of range asymmetric number system encoding and decoding |url=https://patents.google.com/patent/US20200413106A1 |access-date=16 February 2022}}</ref>

== See also ==
* [[Entropy encoding]]
* [[Huffman coding]]
* [[Arithmetic coding]]
* [[Range encoding]]
* [[Zstandard]] Facebook compressor
* [[LZFSE]] Apple compressor

== References ==
<references/>

== External links ==
* [https://ieeexplore.ieee.org/document/7306068/ High throughput hardware architectures for asymmetric numeral systems entropy coding] S. M. Najmabadi, Z. Wang, Y. Baroud, S. Simon, ISPA 2015
* [https://github.com/Cyan4973/FiniteStateEntropy New Generation Entropy coders] Finite state entropy (FSE) implementation of tANS by Yann Collet
* [https://github.com/rygorous/ryg_rans rygorous/ryg_rans] Implementation of rANS by Fabian Giesen
* [https://github.com/jkbonfield/rans_static jkbonfield/rans_static] Fast implementation of rANS and arithmetic coding by James K. Bonfield
* [https://github.com/facebook/zstd/ facebook/zstd] [[Facebook]] [[Zstandard]] compressor by Yann Collet (author of [[LZ4 (compression algorithm)|LZ4]])
* [https://github.com/lzfse/lzfse LZFSE] [[LZFSE]] compressor (LZ+FSE) of [[Apple Inc.]]
* [http://www.ebi.ac.uk/ena/software/cram-toolkit CRAM 3.0 DNA compressor (order 1 rANS)] (part of [[SAMtools]]) by [[European Bioinformatics Institute]]
* [https://chromium-review.googlesource.com/#/c/318743 ] implementation for Google [[VP10]]
* [https://chromium-review.googlesource.com/#/c/338781/ ] implementation for Google [[WebP]]
* [https://github.com/google/draco/tree/master/core ] Google [https://opensource.googleblog.com/2017/01/introducing-draco-compression-for-3d.html Draco 3D compression library]
* [https://aomedia.googlesource.com/aom/+/master/aom_dsp aom_dsp - aom - Git at Google] implementation of [[Alliance for Open Media]]
* [http://demonstrations.wolfram.com/DataCompressionUsingAsymmetricNumeralSystems/ Data Compression Using Asymmetric Numeral Systems - Wolfram Demonstrations Project] Wolfram Demonstrations Project
* [http://gamma.cs.unc.edu/GST/ GST: GPU-decodable Supercompressed Textures] GST: GPU-decodable Supercompressed [[Texture compression|Textures]]
* [https://www.safaribooksonline.com/library/view/understanding-compression/9781491961520/ Understanding compression] book by A. Haecky, C. McAnlis

{{Compression Methods}}

[[Category:Lossless compression algorithms]]
[[Category:Finite automata]]
[[Category:Non-standard positional numeral systems]]
[[Category:Data compression]]