Encoding of probability distributions for Asymmetric Numeral Systems

Jarek Duda

Publication date: 11 June 2021

Abstract: Many data compressors regularly encode probability distributions for entropy coding - requiring minimal description length type of optimizations. Canonical prefix/Huffman coding usually just writes lengths of bit sequences, this way approximating probabilities with powers-of-2. Operating on more accurate probabilities usually allows for better compression ratios, and is possible e.g. using arithmetic coding and Asymmetric Numeral Systems family. Especially the multiplication-free tabled variant of the latter (tANS) builds automaton often replacing Huffman coding due to better compression at similar computational cost - e.g. in popular Facebook Zstandard and Apple LZFSE compressors. There is discussed encoding of probability distributions for such applications, especially using Pyramid Vector Quantizer(PVQ)-based approach with deformation, bucket approximation, prefix trees, improving accuracy with additional bits, also tuned symbol spread for tANS.

Has companion code repository: https://github.com/JarekDuda/AsymmetricNumeralSystemsToolkit

This page was built for publication: Encoding of probability distributions for Asymmetric Numeral Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6370078)