Asymmetric Numeral Systems - how to add fractional bits to Huffman decoder


Jarosław Duda, Uniwersytet Jagielloński


09/03/2016 - 13:15

Entropy coding is the heart of most of data compressors. Standard methods are Huffman coding - fast but inaccurate (suboptimal), and arithmetic/range coding - accurate but an order of magnitude slower (costly). I will tell about new approach: Asymmetric Numeral Systems, which is accurate while having cost similar to Huffman coding. It is for example used in Apple LZFSE (default compressor in iOS9 and OS X 10.11) or CRAM 3.0 DNA compressor of European Bioinformatics Institute. I will also mention about Joint Reconstruction Codes enhancement of Fountain Codes, and generalizations of Kuznetsov-Tsybakov problem for more subtle steganography/watermarking.