Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Asymmetric numeral systems
Summary
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, 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, DNA compressor from SAMtools utilities,
Dropbox DivANS compressor, Microsoft DirectStorage BCPack texture compressor, and JPEG XL image compressor.
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.