4 ms·

Asymmetric numeral systems (2014)

39 points by morenoh149 10y ago

eln1 10y ago
It points to even older paper for ANS: http://arxiv.org/abs/0710.3861 http://arxiv.org/abs/0710.3861 The more recent one is: http://arxiv.org/abs/1311.2540 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 https://en.wikipedia.org/wiki/Fibonacci_coding )- on a lattice, such that there cannot be two neighboring '1's. It also uses an interesting concept of Maximal Entropy Random Walk.
- sctb 10y ago
  Thanks, we updated the link to the newer version.
thristian 10y ago
I once found a really great article explaining arithmetic encoding¹, and I felt I understood what was going on and managed to re-implement the article's example from MS-DOS-era C to modern Python, but when I tried to use it for anything else it didn't work and I wasn't smart enough to debug it. The claim that asymmetric numeral systems are simpler than arithmetic encoding is quite interesting, but as a working programmer, I have difficulty with the academic language and mathematical generality used in papers like this. Does anybody have a more approachable explanation of what's going on? ¹: http://marknelson.us/1991/02/01/arithmetic-coding-statistical-modeling-data-compression/ http://marknelson.us/1991/02/01/arithmetic-coding-statistica...
- eln1 10y ago
  Here are explanations of various people: http://www.ezcodesample.com/abs/abs_article.html http://www.ezcodesample.com/abs/abs_article.html http://cbloomrants.blogspot.com/2014/02/02-18-14-understanding-ans-conclusion.html http://cbloomrants.blogspot.com/2014/02/02-18-14-understandi... http://fastcompression.blogspot.fr/2013/12/finite-state-entropy-new-breed-of.html http://fastcompression.blogspot.fr/2013/12/finite-state-entr... (Yann Collet, he has many posts) https://fgiesen.wordpress.com/2014/02/02/rans-notes/ https://fgiesen.wordpress.com/2014/02/02/rans-notes/ interactive simulator: http://demonstrations.wolfram.com/DataCompressionUsingAsymmetricNumeralSystems/ http://demonstrations.wolfram.com/DataCompressionUsingAsymme...

39 points by morenoh149 10y ago

eln1 10y ago

It points to even older paper for ANS: http://arxiv.org/abs/0710.3861 http://arxiv.org/abs/0710.3861 The more recent one is: http://arxiv.org/abs/1311.2540 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 https://en.wikipedia.org/wiki/Fibonacci_coding )- on a lattice, such that there cannot be two neighboring '1's. It also uses an interesting concept of Maximal Entropy Random Walk.

sctb 10y ago
Thanks, we updated the link to the newer version.

thristian 10y ago

I once found a really great article explaining arithmetic encoding¹, and I felt I understood what was going on and managed to re-implement the article's example from MS-DOS-era C to modern Python, but when I tried to use it for anything else it didn't work and I wasn't smart enough to debug it. The claim that asymmetric numeral systems are simpler than arithmetic encoding is quite interesting, but as a working programmer, I have difficulty with the academic language and mathematical generality used in papers like this. Does anybody have a more approachable explanation of what's going on? ¹: http://marknelson.us/1991/02/01/arithmetic-coding-statistical-modeling-data-compression/ http://marknelson.us/1991/02/01/arithmetic-coding-statistica...

eln1 10y ago
Here are explanations of various people: http://www.ezcodesample.com/abs/abs_article.html http://www.ezcodesample.com/abs/abs_article.html http://cbloomrants.blogspot.com/2014/02/02-18-14-understanding-ans-conclusion.html http://cbloomrants.blogspot.com/2014/02/02-18-14-understandi... http://fastcompression.blogspot.fr/2013/12/finite-state-entropy-new-breed-of.html http://fastcompression.blogspot.fr/2013/12/finite-state-entr... (Yann Collet, he has many posts) https://fgiesen.wordpress.com/2014/02/02/rans-notes/ https://fgiesen.wordpress.com/2014/02/02/rans-notes/ interactive simulator: http://demonstrations.wolfram.com/DataCompressionUsingAsymmetricNumeralSystems/ http://demonstrations.wolfram.com/DataCompressionUsingAsymme...