[x265] New entropy coding - faster than Huffman, compression rate like arithmetic

[Jarosław Duda]

Hallo,

There is a new approach to entropy coding (no patents): Asymmetric Numeral Systems(ANS) - the current implementation has about 50% faster decoding than Huffman (single table use per symbol from a large alphabet), giving rates like arithmetic:
https://github.com/Cyan4973/FiniteStateEntropy
The idea is somehow similar to arithmetic coding, but instead of two numbers to define the current state (range), it uses only a single natural number (containing lg(state) bits of information) - thanks of this much smaller space of states, we can put entire behavior into a small table.
Here is a poster explaining the basic concepts and the difference from arithmetic: https://dl.dropboxusercontent.com/u/12405967/poster.pdf

I would like to propose a discussion about the possibility of applying it in video compression, maybe adding to h.265 - it should be about 10 times faster than CABAC, providing similar compression rate.
The cost is that we need to store coding tables for a given probability distribution: let say 1-16kB for 256 size alphabet.
For different contexts (probability distributions), we can build separate tables and switch between them - the memory cost is "the number of different contexts/distributions" times a few kilobytes.

So if the number of different contexts used for given coding parameters is smaller than let say a thousand, ANS can provide huge speedup there.
It could also work alongside CABAC - speed up only some part of entropy coding.

Best,
Jarek Duda

-- 
dr Jarosław Duda
Center for Science of Information, Purdue University, USA
http://www.soihub.org/people.php?id=484