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
In information theory, an entropy coding (or entropy encoding) is any lossless data compression method that attempts to approach the lower bound declared by Shannon's source coding theorem, which states that any lossless data compression method ...
methods introduced by Jarosław (Jarek) Duda from
Jagiellonian University
The Jagiellonian University ( Polish: ''Uniwersytet Jagielloński'', UJ) is a public research university in Kraków, Poland. Founded in 1364 by King Casimir III the Great, it is the oldest university in Poland and the 13th oldest university in ...
, used in
data compression
In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compressio ...
since 2014
due to improved performance compared to previous methods.
ANS combines the compression ratio of
arithmetic coding
Arithmetic coding (AC) is a form of entropy encoding used in lossless data compression. Normally, a string of characters is represented using a fixed number of bits per character, as in the ASCII code. When a string is converted to arithmetic ...
(which uses a nearly accurate probability distribution), with a processing cost similar to that of
Huffman coding
In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code proceeds by means of Huffman coding, an algo ...
. In the tabled ANS (tANS) variant, this is achieved by constructing a
finite-state machine
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
to operate on a large alphabet without using multiplication.
Among others, ANS is used in the
Facebook
Facebook is an online social media and social networking service owned by American company Meta Platforms. Founded in 2004 by Mark Zuckerberg with fellow Harvard College students and roommates Eduardo Saverin, Andrew McCollum, Dust ...
Zstandard
Zstandard, commonly known by the name of its reference implementation zstd, is a lossless data compression algorithm developed by Yann Collet at Facebook.
''Zstd'' is the reference implementation in C. Version 1 of this implementation was r ...
compressor
[''Smaller 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
Linux ( or ) is a family of open-source Unix-like operating systems based on the Linux kernel, an operating system kernel first released on September 17, 1991, by Linus Torvalds. Linux is typically packaged as a Linux distribution, whi ...
kernel,
[''Zstd Compression For Btrfs & Squashfs Set For Linux 4.14, Already Used Within Facebook'']
Phoronix, September 2017. Android operating system, was published as RFC 8478 for
MIME
Multipurpose Internet Mail Extensions (MIME) is an Internet standard that extends the format of email messages to support text in character sets other than ASCII, as well as attachments of audio, video, images, and application programs. Message ...
[''Zstandard Compression and The application/zstd Media Type (email standard)'']
and
HTTP
The Hypertext Transfer Protocol (HTTP) is an application layer protocol in the Internet protocol suite model for distributed, collaborative, hypermedia information systems. HTTP is the foundation of data communication for the World Wide We ...
[''Hypertext Transfer Protocol (HTTP) Parameters'']
IANA
The Internet Assigned Numbers Authority (IANA) is a standards organization that oversees global IP address allocation, autonomous system number allocation, root zone management in the Domain Name System (DNS), media types, and other Interne ...
.),
Apple
An apple is an edible fruit produced by an apple tree (''Malus domestica''). Apple trees are cultivated worldwide and are the most widely grown species in the genus '' Malus''. The tree originated in Central Asia, where its wild ancest ...
LZFSE
LZFSE (Lempel–Ziv Finite State Entropy) is an open source lossless data compression algorithm created by Apple Inc. It was released with a simpler algorithm called LZVN.
Overview
The name is an acronym for Lempel–Ziv and finite-state entro ...
compressor,
[''Apple Open-Sources its New Compression Algorithm LZFSE'']
InfoQ, July 2016. Google
Google LLC () is an American Multinational corporation, multinational technology company focusing on Search Engine, search engine technology, online advertising, cloud computing, software, computer software, quantum computing, e-commerce, ar ...
Draco 3D compressor
[''Google Draco 3D compression library'']
(used e.g. in
Pixar
Pixar Animation Studios (commonly known as Pixar () and stylized as P I X A R) is an American computer animation studio known for its critically and commercially successful computer animated feature films. It is based in Emeryville, Californ ...
Universal Scene Description
Universal Scene Description (USD) is a framework for interchange of 3D computer graphics data. The framework focuses on collaboration, non-destructive editing, and enabling multiple views and opinions about graphics data. USD is used in many indust ...
format
[''Google 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
Cram may refer to:
* Cram (surname), a surname, and list of notable persons having the surname
* Cram.com, a website for creating and sharing flashcards
* Cram (Australian game show), a television show
* ''Cram'' (game show), a TV game show th ...
DNA compressor
[''CRAM format specification (version 3.0)'']
from
SAMtools
SAMtools is a set of utilities for interacting with and post-processing short DNA sequence read alignments in the SAM (Sequence Alignment/Map), BAM (Binary Alignment/Map) and CRAM formats, written by Heng Li. These files are generated as output b ...
utilities,
Dropbox
Dropbox is a file hosting service operated by the American company Dropbox, Inc., headquartered in San Francisco, California, U.S. that offers cloud storage, file synchronization, personal cloud, and client software. Dropbox was founded in 2007 ...
DivANS compressor,
[''Building better compression together with DivANS'']
Microsoft
Microsoft Corporation is an American multinational technology corporation producing computer software, consumer electronics, personal computers, and related services headquartered at the Microsoft Redmond campus located in Redmond, Washi ...
DirectStorage
The Xbox Series X/S are home video game consoles developed by Microsoft. They were both released on November 10, 2020, as the fourth generation Xbox, succeeding the Xbox One. Along with Sony's PlayStation 5, also released in November 2020, ...
BCPack texture compressor,
[''Microsoft DirectStorage overview'']
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.
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 length
sequences containing
zeros and
ones, for some probability
, are called
combinations. Using
Stirling's approximation
In mathematics, Stirling's approximation (or Stirling's formula) is an approximation for factorials. It is a good approximation, leading to accurate results even for small values of n. It is named after James Stirling, though a related but less p ...
we get their asymptotic number being
:
called
Shannon entropy
Shannon may refer to:
People
* Shannon (given name)
* Shannon (surname)
* Shannon (American singer), stage name of singer Shannon Brenda Greene (born 1958)
* Shannon (South Korean singer), British-South Korean singer and actress Shannon Arrum W ...
.
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
In information theory, an entropy coding (or entropy encoding) is any lossless data compression method that attempts to approach the lower bound declared by Shannon's source coding theorem, which states that any lossless data compression method ...
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
Arithmetic coding (AC) is a form of entropy encoding used in lossless data compression. Normally, a string of characters is represented using a fixed number of bits per character, as in the ASCII code. When a string is converted to arithmetic ...
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 bit sequence of its binary expansion. To add information from a binary variable
, we can use coding function
, which shifts all bits one position up, and place the new bit in the least significant position. Now 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
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 generalize 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 condition
. Assuming that a natural number
contains
bits of information,
. Hence the symbol of probability
is encoded as containing
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
,
. 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
:
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 size
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
denominator, where is chosen (usually 8-12 bits):
for some natural