Asymmetric numeral systems
arXiv:0902.0271
Abstract
In this paper will be presented new approach to entropy coding: family of generalizations of standard numeral systems which are optimal for encoding sequence of equiprobable symbols, into asymmetric numeral systems - optimal for freely chosen probability distributions of symbols. It has some similarities to Range Coding but instead of encoding symbol in choosing a range, we spread these ranges uniformly over the whole interval. This leads to simpler encoder - instead of using two states to define range, we need only one. This approach is very universal - we can obtain from extremely precise encoding (ABS) to extremely fast with possibility to additionally encrypt the data (ANS). This encryption uses the key to initialize random number generator, which is used to calculate the coding tables. Such preinitialized encryption has additional advantage: is resistant to brute force attack - to check a key we have to make whole initialization. There will be also presented application for new approach to error correction: after an error in each step we have chosen probability to observe that something was wrong. There will be also presented application for new approach to error correction: after an error in each step we have chosen probability to observe that something was wrong. We can get near Shannon's limit for any noise level this way with expected linear time of correction.
47 pages, 6 figures
References in corpus (1)
Cited by in corpus (26)
- Variational Diffusion Models
- Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding
- Techniques for Inverted Index Compression
- Bit-Swap: Recursive Bits-Back Coding for Lossless Compression with Hierarchical Latent Variables
- Practical Lossless Compression with Latent Variables using Bits Back Coding
- IDF++: Analyzing and Improving Integer Discrete Flows for Lossless Compression
- Lossless Image Compression through Super-Resolution
- Lightweight compression with encryption based on Asymmetric Numeral Systems
- A tutorial on the range variant of asymmetric numeral systems
- Integer Discrete Flows and Lossless Compression
- Enhanced Invertible Encoding for Learned Image Compression
- HiLLoC: Lossless Image Compression with Hierarchical Latent Variable Models
- Embedding grayscale halftone pictures in QR Codes using Correction Trees
- Towards Real-Time Neural Video Codec for Cross-Platform Application Using Calibration Information
- Compressing Multisets with Large Alphabets using Bits-Back Coding
- Lossless compression with state space models using bits back coding
- On the Out-of-distribution Generalization of Probabilistic Image Modelling
- Overview of online and offline reconstruction in ALICE for LHC Run 3
- Fast Entropy Coding for ALICE Run 3
- Learning Non-linear Wavelet Transformation via Normalizing Flow
- Autoregressive Diffusion Models
- Encoding of probability distributions for Asymmetric Numeral Systems
- Improving Lossless Compression Rates via Monte Carlo Bits-Back Coding
- Rice-Marlin Codes: Tiny and Efficient Variable-to-Fixed Codes
- Optimal compression of hash-origin prefix trees
- Lossless Compression with Latent Variable Models