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 _______________________________________________ x265-devel mailing list [email protected] https://mailman.videolan.org/listinfo/x265-devel
