Recognition: unknown
Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 7 Pith papers
-
Fast and Exact: Asymptotically Linear KL-Optimal Frequency Normalization
Three new provably KL-optimal frequency normalization algorithms are presented, one running in linear time in the number of symbols.
-
Decoupling Vector Data and Index Storage for Space Efficiency
DecoupleVS decouples vector data and index storage in ANNS systems to cut storage space by up to 58.7% with competitive search and update performance.
-
ENEC: A Lossless AI Model Compression Method Enabling Fast Inference on Ascend NPUs
ENEC delivers 3.43X higher throughput than DietGPU and 1.12X better compression ratio than nvCOMP for lossless model weight compression on Ascend NPUs, yielding up to 6.3X end-to-end inference speedup.
-
OpenZL: Using Graphs to Compress Smaller and Faster
OpenZL uses a directed acyclic graph of modular codecs to enable rapid creation of application-specific compressors that deliver better ratios and speeds than general-purpose tools while remaining competitive with dee...
-
TStore: Rethinking AI Model Hub with Tensor-Centric Compression
TStore reduces AI model storage via tensor-level fingerprinting, clustering, and compression without annotations while claiming to preserve usability.
-
LEAN-3D: Low-latency Hierarchical Point Cloud Codec for Mobile 3D Streaming
LEAN-3D delivers 3-5x lower latency and up to 5.1x lower edge energy for learned point cloud compression on mobile hardware by restricting learned components to shallow hierarchy levels and using deterministic coding ...
-
TStore: Rethinking AI Model Hub with Tensor-Centric Compression
TensorHub reduces storage in AI model hubs via tensor-centric deduplication and compression while keeping model performance intact.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.