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

Abstract

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.

24 pages, 12 figures

References in corpus (2)

• Asymmetric numeral systems
• Optimal encoding on discrete lattice with translational invariant constrains using statistical algorithms

Cited by in corpus (27)

• Sprintz: Time Series Compression for the Internet of Things
• Techniques for Inverted Index Compression
• Lossy Image Compression with Quantized Hierarchical VAEs
• IDF++: Analyzing and Improving Integer Discrete Flows for Lossless Compression
• Interleaved entropy coders
• Transform Network Architectures for Deep Learning based End-to-End Image/Video Coding in Subsampled Color Spaces
• High-Fidelity Variable-Rate Image Compression via Invertible Activation Transformation
• Lightweight compression with encryption based on Asymmetric Numeral Systems
• Attention-Based Generative Neural Image Compression on Solar Dynamics Observatory
• Integer Discrete Flows and Lossless Compression
• On Optimally Partitioning Variable-Byte Codes
• Neural-based Compression Scheme for Solar Image Data
• Flexible Variable-Rate Image Feature Compression for Edge-Cloud Systems
• Variable-Rate Deep Image Compression through Spatially-Adaptive Feature Transform
• On the Out-of-distribution Generalization of Probabilistic Image Modelling
• Designing dedicated data compression for physics experiments within FPGA already used for data acquisition
• A Combined Deep Learning based End-to-End Video Coding Architecture for YUV Color Space
• Fast Entropy Coding for ALICE Run 3
• Learning Non-linear Wavelet Transformation via Normalizing Flow
• Partition and Code: learning how to compress graphs
• Learned Video Codec with Enriched Reconstruction for CLIC P-frame Coding
• OSOA: One-Shot Online Adaptation of Deep Generative Models for Lossless Compression
• Encoding of probability distributions for Asymmetric Numeral Systems
• iVPF: Numerical Invertible Volume Preserving Flow for Efficient Lossless Compression
• Nonuniform probability modulation for reducing energy consumption of remote sensors
• Lossless Compression with Probabilistic Circuits
• Near-imperceptible Neural Linguistic Steganography via Self-Adjusting Arithmetic Coding