HackerPapers

arXiv:1311.2540cs.IT

Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding

Jarek Duda

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.

arXiv comments
24 pages, 12 figures
Journal reference
DOI
Subjects
cs.ITInformation Theory

On Hacker News

Linked by 11 identifiable commenters in 11 comments across 10 threads, from Jan 2014 to Mar 2024. Found in 3 HN submissions from May 2016 to Jan 2023. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments10 threads

  1. The Montreal problem: Why programming languages need a style czar 1 comment

    • Some people's brains just work this way. Here's an example of a somewhat popular and regularly maintained library written in a similar style: https://github.com/enkimute/ganja.js/blob/6e97cb45d780cd7c66... Another example is Jarek Duda's paper on the ANS compression algorithm. A…

      jiggawattsView on HNParent context

  2. Silly Lossy Text Compression Idea 1 comment

    • Sounds similar to: https://github.com/Cyan4973/FiniteStateEntropy https://arxiv.org/abs/1311.2540 > 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…

      pyinstallwoesView on HNParent context

  3. Understanding Asymmetric Numeral Systems 1 comment

    • It is. "Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding" https://arxiv.org/abs/1311.2540

      adamnemecekView on HNParent context

  4. Poland's oldest university denies Google's right to patent Polish coding concept 1 comment

    • I think you are correct: ANS is an entropy coding method, so a patent shouldn't be able to claim a new use for encoding some specific type of information [1]. Also, Duda's paper even exemplifies the obvious use case for video compression [2]. [1]…

      peraView on HNParent context

  5. Google is trying to patent video compression use of Asymmetric Numeral Systems 1 comment

    • Who is Jarek - his page http://th.if.uj.edu.pl/~dudaj/ His original publication from - https://arxiv.org/abs/1311.2540 . That work was a result of two years of research that was well documented, and was making noise in encoding community. His first notes on use ans for quick…

      baybal2View on HNParent context

  6. JPEG Huffman Coding Tutorial 1 comment

    • JPEG2000 used Arithmetic coding. But, you'd have to re-write the standard and evaluate it to get JPEG to use Arithmetic coding (e.g. does the way JPEG coefficients are read out still make sense with Arithmetic coding)? There are also other algorithms for universal source coding…

      TheGorramBatmanView on HNParent context

  7. Smaller and faster data compression with Zstandard 1 comment

    • Cyan4973/Yann also is well known for xxhash[1], which is one of the faster hashers[2] out there. Post a new hasher and people will probably ask about xxhash (ex: metrohash[3]). Guy is an absolute machine. If you search Google for 'zstd' right now, you'll find him, not Facebook…

      rektideView on HNParent context

  8. Asymmetric numeral systems (2014) 1 comment

    • It points to even older paper for ANS: http://arxiv.org/abs/0710.3861 The more recent one is: http://arxiv.org/abs/1311.2540 The first one is about kind of multidimensional analogue of Fibonacci coding ( https://en.wikipedia.org/wiki/Fibonacci_coding )- on a lattice, such that…

      eln1View on HNParent context

  9. Apple Open-Sources its Compression Algorithm LZFSE 2 comments

    • This is a baseless speculation. First of all, Apple provides LZ4 in libcompression. Secondly, LZFSE uses Lempel–Ziv algorithm and ANS coder invented by Jarek Duda (https://arxiv.org/abs/1311.2540): https://developer.apple.com/library/ios/documentation/Perfor...

      dchestView on HNParent context

    • LZ4 is a format. All you can say about how energy efficient a format is, is by looking at the average speeds of its implementations. However, zlib for instance (a DEFLATE library) is more energy efficient than zopfli (another DEFLATE library), just by virtue of taking less CPU…

      espadrineView on HNParent context

  10. Finite State Entropy coder (faster than Huffman) 1 comment

    • Blog entry: http://fastcompression.blogspot.fr/2013/12/finite-state-entr... Paper: http://arxiv.org/abs/1311.2540

      wfnView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.