Asymmetric Numeral Systems: a new approach to entropy coding

When it comes to data compression, having a small sized compressed file is important, but as people continue to create and share more and more data, having a method that can achieve this compression rate quickly and efficiently is also becoming increasingly necessary. Earlier this year, Facebook announced a new standard which is able to achieve good compression rates faster, called ZStandard. ZStandard is shown to be very competitive with current compression algorithms, outdoing some algorithms completely on compression rate and speed benchmarks. The key to this new approach is to use a design that is compatible with the capabilities of modern CPUs, taking advantage of computations that are easy to do. The development that allowed ZStandard to be implemented efficiently is a coding algorithm called Asymmetric Numeral Systems (ANS) developed by Jarek Duda.  ANS is an algorithm which has the speed of Huffman coding but achieves a compression rate similar to arithmetic coding. In this talk, we will give an overview of the ANS algorithm, provide basic intuitions for its main properties, and discuss some of the algorithm's pros and cons.