Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding

By J. Duda. 2013

261 citations recorded by the source corpus.

The modern data compression is mainly based on two approaches to entropy coding: Huffman (HC) and arithmetic/range coding (AC). The former is much faster, but approximates probabilities with powers of 2, usually leading to relatively low compression rates. The latter uses nearly exact probabilities - easily approaching theoretical compression rate limit (Shannon entropy), but at cost of much larger computational cost. Asymmetric numeral systems (ANS) is a new approach to accurate entropy coding, which allows to end this trade-off between speed and rate: the recent implementation [1] provides about $50\%$ faster decoding than HC for 256 size alphabet, with compression rate similar to provided by AC. This advantage is due to being simpler than AC: using single natural number as the state, instead of two to represent a range. Beside simplifying renormalization, it allows to put the entire behavior for given probability distribution into a relatively small table: defining entropy coding automaton. The memory cost of such table for 256 size alphabet is a few kilobytes. There is a large freedom while choosing a specific table - using pseudorandom number generator initialized with cryptographic key for this purpose allows to simultaneously encrypt the data. This article also introduces and discusses many other variants of this new entropy coding approach, which can provide direct alternatives for standard AC, for large alphabet range coding, or for approximated quasi arithmetic coding.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

Citations in the corpus

Fast Lossless Neural Compression with Integer-Only Discrete Flows (2022, methodology): “The speedup is lower than that for inference latency due to our suboptimal CPU implementation of rANS.”
Integer Discrete Flows and Lossless Compression (2019, methodology): “In our experiments the entropy coder rANS [10] (see Appendix A.”
Compression with Flows via Local Bits-Back Coding (2019, methodology): “There is already a rich literature of tailored coding algorithms for autoregressive models and variational autoencoders built from conditional distributions which are already tractable for coding [38, 12, 18, 13, 42], but there are currently no such algorithms for general types of flow models [32].”
HTSlib: C library for reading/writing high-throughput sequencing data (2021, unknown): “The CRAM format uses columnspecific compression methods including gzip, rANS [14], LZMA, and bzip2.”
iFlow: Numerically Invertible Flows for Efficient Lossless Compression via a Uniform Coder (2021, methodology): “As follows, we introduce our Uniform Base Conversion Systems (UBCS), which is easy to implement and the coding bandwidth is much greater than that of rANS [12].”
iVPF: Numerical Invertible Volume Preserving Flow for Efficient Lossless Compression (2021, methodology): “, Huffman coding [18], Arithmetic coding [39] and Asymmetric Numeral Systems [9], are developed so that symbols with certain distribution density can be encoded with codelength close to the entropy.”
IDF++: Analyzing and Improving Integer Discrete Flows for Lossless Compression (2020, methodology): “[12, 13, 49] is used for lossless compression of the latent variables z = [ z (1) , . . . , z ( L ) ] by using the probability distribution p ( z ) = p ( z ( L ) ) p ( z ( L − 1) | y ( L − 1) ) . . . p ( z (1) | y (1) ) corresponding to the model’s multi-level structure.”