ESP Wiki is looking for moderators and active contributors!

Asymmetric numeral systems

Asymmetric numeral systems (ANS) is a family of entropy encoding methods introduced by Jarosław (Jarek) Duda of the Jagiellonian University, in Kraków, Poland. It is an important technology used in data compression since 2014 by various companies worldwide due to improved performance compared to previously used methods, being up to 30 times faster.

Jarek Duda, as the principal author, never intended to patent this technology.[1] However, in January 2022, a variant of ANS was patented[2] by Microsoft despite clear existence of prior art.[3] This is a clear example of software patents blocking innovation and research. A technology released into the public domain is at risk of becoming a monopoly because of patent trolls.

Background

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. It is considered an important development in data compression that will benefit many companies around the world. Already, the algorithm is used by Facebook, Linux, Android, Apple, Google, CRAM, Dropbox, JPEG XL, among many others.[4] ANS has several variants (uABS, rANS, tANS), all at risk of being patented at any given time.

ANS is the brainchild of Jarek Duda in collaboration with various researchers.[5] With his work, Duda hoped to avoid what happened to arithmetic coding, which was locked up by patents for 20 years. Now history is repeating itself, tragically illustrating that software patents are a persistent threat today.

Patents

PetaGene

PetaGene was the first actor that alarmed the data compression community in 2016 with its UK patent[6] on ANS, followed by a US patent[7] a year later. PetaGene develops genomic data compression software.

Google

Duda helped Google engineers implement ANS for video file compression out of genuine interest to see widely used products use the algorithm.[8] Despite Duda's good spirit, Google attempted to patent[9] the technology behind his back. This particular attempt was widely covered by the media,[10][11] which led people to outcry against Google on public forums.[12][13] Duda was also supported by the Electronic Frontier Foundation.[14] Thanks to the combined efforts of media reports and third party notices to the USPTO, the patent application was rejected, but Duda was rightfully appalled by Google's behavior:[15]

Nice "thank you" from a multibillion "don't be evil" corporation to a poor academic whose work they use for free and who has helped them with it for the last three years [...] there was a moment they gave me hope for a formal collaboration with my University so I could build a team, but then silence... probably due to this patent application.

Google has silently registered another patent citing ANS.[16] Duda believes its claims are extremely general.[17]

Microsoft

After Google, it was Microsoft's turn to attempt to register a patent on ANS by filing an application in the United States in June 2019.[18] Again, the data compression community agreed that the application's claims brought zero novelty:[19][20]

Basically I can't really see anything in this patent which isn't basic rANS except for the words "selectively" and the reordering of events. I don't believe the latter is relevant. [...] I'm thinking though the selective nature is what they view their invention as, but the patent is (as always) so badly worded it also affects the most trivial single static-frequency table driven rANS method, as well as the other end of the scale with fully dynamic probabilities. In short, I think it's a total fiasco and wrong both legally as well as morally.

Eventually, the patent was granted[2] in early 2022,[3] while also waiting for decisions on patent applications in Europe, South Korea, and China. A continuing patent application was filed in December 2021.[21]

This development led Duda to also talk about his experience on LibrePlanet 2022.[22]

Impact

The rANS variant is used in JPEG XL, a new and modern image compression format that provides three times better compression than the JPEG specification developed in 1992. Microsoft's patent on ANS, along with others that might follow, will make JPEG XL adoption more difficult. Even if Microsoft never sues developers using the algorithm, it poses a passive threat; because of legal insecurity, programmers are likely to avoid using or contributing to this technology, stagnating progress and harming its development as a standard. JPEG XL is thus added to the long list of free software harmed by software patents.

ANS authors agree that software patents are too abstract and of terrible quality; we need to eliminate them. However, the sheer volume of software patents cannot be addressed by invalidating them one by one. Litigation is too expensive, and we will never guarantee that more software patents on the same technology won't be registered. This is why we should abolish software patents altogether.

Related pages on ESP Wiki

References

  1. ↑ Duda Jarek, Jarek Duda on software patents[archived], endsoftwarepatents.org, 2018-01-19.
  2. ↑ 2.0 2.1 Gladding Derek E. et al., Microsoft Technology Licensing LLC, Features of range asymmetric number system encoding and decoding[USPTO][Google][PAT2PDF], U.S. Patent No. 11,234,023, issued on 2022-01-25.
  3. ↑ 3.0 3.1 Claburn Thomas, Alarm raised after Microsoft wins data-encoding patent[archived], theregister.com, 2022-02-17.
  4. ↑ Duda Jarek, List of Asymmetric Numeral Systems implementations[archived], encode.su, 2014-11-12.
  5. ↑ Dr Jarosław Duda[archived], th.if.uj.edu.pl.
  6. ↑ Greenfield Daniel Leo & Rrustemi Alban, Petagene Ltd, System and method for compressing data using asymmetric numeral systems with probability distributions[UKIPO][Google], GB2538218, issued on 2016-11-16.
  7. ↑ Greenfield Daniel Leo & Rrustemi Alban, Petagene Ltd, System and method for compressing data using asymmetric numeral systems with probability distributions[USPTO][Google][PAT2PDF], U.S. Patent No. 9,847,791, issued on 2017-12-19.
  8. ↑ Duda Jarek, New entropy coding: faster than Huffman, compression rate like arithmetic[archived], groups.google.com, 2014-01-01.
  9. ↑ Converse Alexander Jay, Google LLC, Mixed boolean-token ans coefficient coding[USPTO][Google][PAT2PDF], Application US15/370,840, filed on 2016-12-06.
  10. ↑ Lee Timothy B., Inventor says Google is patenting work he put in the public domain[archived], arstechnica.com, 2018-10-06.
  11. ↑ Cimpanu Catalin, Google Accused of Trying to Patent Public Domain Technology[archived], bleepingcomputer.com, 2017-09-11.
  12. ↑ Google Accused of Trying To Patent Public Domain Technology[archived], yro.slashdot.org, 2017-09-11.
  13. ↑ Google Accused of Trying to Patent Public Domain Technology[archived], old.reddit.com, 2017-09-12.
  14. ↑ Nazer Daniel, After Patent Office Rejection, It is Time For Google To Abandon Its Attempt to Patent Use of Public Domain Algorithm[archived], eff.org, 2018-08-30.
  15. ↑ Duda Jarek, Published rANS patent by Storeleap (Post #61)[archived], encode.su, 2017-06-17.
  16. ↑ Hemmer Michael & Stava Ondrej, Google LLC, Folded integer encoding[USPTO][Google][PAT2PDF], U.S. Patent No. 9,595,976, issued on 2017-03-14.
  17. ↑ Duda Jarek, Published rANS patent by Storeleap (Post #30)[archived], encode.su, 2017-03-20.
  18. ↑ Claburn Thomas, Third time's a harm? Microsoft tries to get twice-rejected encoding patent past skeptical examiners[archived], theregister.com, 2021-03-13.
  19. ↑ JamesWasil, Published rANS patent by Storeleap (Post #122)[archived], encode.su, 2021-03-06.
  20. ↑ JamesB, RANS: Microsoft wins data-encoding patent (Post #2)[archived], encode.su, 2022-05-11.
  21. ↑ Gladding Derek E. et al., Microsoft Technology Licensing LLC, Features of range asymmetric number system encoding and decoding[USPTO][Google][PAT2PDF], Application US17/552,295, filed on 2021-12-15.
  22. ↑ Duda Jarek, ANS coding replacing Huffman and AC — from introduction to patent issues[archived], framatube.org, 2022-03-29.

External links

Retrieved from "https://wiki.endsoftwarepatents.org/w/index.php?title=Asymmetric_numeral_systems&oldid=38340"