4 ms·

> I think he is the first one to write a practical fast arithmetic coder using ANS. I don't think he is the first; although RAD game tools has been cagey abou

> I think he is the first one to write a practical fast arithmetic coder using ANS. I don't think he is the first; although RAD game tools has been cagey about the details, many strongly suspect their recently announced Kraken, etc. use ANS in some form and some of their previous products; see the discussion here: https://news.ycombinator.com/item?id=11583898 https://news.ycombinator.com/item?id=11583898 ...and here: http://encode.ru/threads/2492-Kraken-compressor http://encode.ru/threads/2492-Kraken-compressor http://cbloomrants.blogspot.ca/2016_05_01_archive.html http://cbloomrants.blogspot.ca/2016_05_01_archive.html

tmd83 10y ago
Yeah read about Kraken a while ago and found the encode.ru thread you pointed. Its unfortunate that we can't compare that side by side. Those guys seem another of those compression geniuses. Overall the world of compression is moving very fast and well these days. But even with that Yann might be the first. Yan's work on FSE is old [0] and if I'm reading this correctly his work on FSE is a mix of his own work and Jarek Duda. But it seems one of his failed attempt challenged Jarek to invent another version of ANS called rANS [1] and as you can see in the encode.ru comments from the RAD game tools that they seem to be using rANS at least for Kraken. Regardless these are impressive works and these people are bouncing ideas of each others, being challenged and inspired which is a very good thing for the rest of us :). [0] https://fastcompression.blogspot.com/2013/12/finite-state-entropy-new-breed-of.html https://fastcompression.blogspot.com/2013/12/finite-state-en... [1] http://encode.ru/threads/1821-Asymetric-Numeral-System?p=36050&viewfull=1#post36050 http://encode.ru/threads/1821-Asymetric-Numeral-System?p=360... [2] https://github.com/rygorous/ryg_rans https://github.com/rygorous/ryg_rans
- binarycrusader 10y ago
  Yeah, it's all very hazy, and since RAD is (understandably) proprietary, it's difficult to figure out exactly when who did what.
- eln1 10y ago
  Before Yann, this ANS variant was implemented by Andrew Polar in 2008: http://www.ezcodesample.com/abs/abs_article.html http://www.ezcodesample.com/abs/abs_article.html Here is a list of implementations: http://encode.ru/threads/2078-List-of-Asymmetric-Numeral-Systems-implementations http://encode.ru/threads/2078-List-of-Asymmetric-Numeral-Sys...
tmd83 10y ago
Now here things gets really interesting [0]. And the fact that the claim is that higher level of compression has negligible impact on decode speed making Kraken really impressive for one time compression and lots of decompression situation. [0] http://cbloomrants.blogspot.ca/2016/07/introducing-oodle-mermaid-and-selkie.html http://cbloomrants.blogspot.ca/2016/07/introducing-oodle-mer...
illicium 10y ago
RAD use rANS for their compressors. See ryg's blog [0] for more details, and a bunch more interesting posts about compression and various low-level optimizations. [0] https://fgiesen.wordpress.com/2015/12/21/rans-in-practice/ https://fgiesen.wordpress.com/2015/12/21/rans-in-practice/
gliptic 10y ago
There are now actually open source decompressors[0] for Oodle formats, and yes, many use rANS. Especially LZNA's clever use of SSE2 to decode and update 16 symbol models is interesting. FSE (which is tANS) is a different beast, though, and more suitable for rarely updated models. [0] http://encode.ru/threads/2577-Open-source-Kraken-Mermaid-Selkie-LZNA-BitKnit-decompression http://encode.ru/threads/2577-Open-source-Kraken-Mermaid-Sel...
- lifthrasiir 10y ago
  ...and got DMCAed [1]. At the very least the discussion itself is interesting for the inside infos, though. [1] https://github.com/github/dmca/blob/master/2016/2016-08-30-Oodle.md https://github.com/github/dmca/blob/master/2016/2016-08-30-O...
  - gliptic 10y ago
    That was because of the belief that he had used an illegal copy of the DLL, and that he had copied all implementation details (neither is true). A representative from RAD said they would withdraw the DMCA complaint now after that misunderstanding was cleared.

tmd83 10y ago

Yeah read about Kraken a while ago and found the encode.ru thread you pointed. Its unfortunate that we can't compare that side by side. Those guys seem another of those compression geniuses. Overall the world of compression is moving very fast and well these days. But even with that Yann might be the first. Yan's work on FSE is old [0] and if I'm reading this correctly his work on FSE is a mix of his own work and Jarek Duda. But it seems one of his failed attempt challenged Jarek to invent another version of ANS called rANS [1] and as you can see in the encode.ru comments from the RAD game tools that they seem to be using rANS at least for Kraken. Regardless these are impressive works and these people are bouncing ideas of each others, being challenged and inspired which is a very good thing for the rest of us :). [0] https://fastcompression.blogspot.com/2013/12/finite-state-entropy-new-breed-of.html https://fastcompression.blogspot.com/2013/12/finite-state-en... [1] http://encode.ru/threads/1821-Asymetric-Numeral-System?p=36050&viewfull=1#post36050 http://encode.ru/threads/1821-Asymetric-Numeral-System?p=360... [2] https://github.com/rygorous/ryg_rans https://github.com/rygorous/ryg_rans

binarycrusader 10y ago
Yeah, it's all very hazy, and since RAD is (understandably) proprietary, it's difficult to figure out exactly when who did what.
eln1 10y ago
Before Yann, this ANS variant was implemented by Andrew Polar in 2008: http://www.ezcodesample.com/abs/abs_article.html http://www.ezcodesample.com/abs/abs_article.html Here is a list of implementations: http://encode.ru/threads/2078-List-of-Asymmetric-Numeral-Systems-implementations http://encode.ru/threads/2078-List-of-Asymmetric-Numeral-Sys...

tmd83 10y ago

Now here things gets really interesting [0]. And the fact that the claim is that higher level of compression has negligible impact on decode speed making Kraken really impressive for one time compression and lots of decompression situation. [0] http://cbloomrants.blogspot.ca/2016/07/introducing-oodle-mermaid-and-selkie.html http://cbloomrants.blogspot.ca/2016/07/introducing-oodle-mer...

illicium 10y ago

RAD use rANS for their compressors. See ryg's blog [0] for more details, and a bunch more interesting posts about compression and various low-level optimizations. [0] https://fgiesen.wordpress.com/2015/12/21/rans-in-practice/ https://fgiesen.wordpress.com/2015/12/21/rans-in-practice/

gliptic 10y ago

There are now actually open source decompressors[0] for Oodle formats, and yes, many use rANS. Especially LZNA's clever use of SSE2 to decode and update 16 symbol models is interesting. FSE (which is tANS) is a different beast, though, and more suitable for rarely updated models. [0] http://encode.ru/threads/2577-Open-source-Kraken-Mermaid-Selkie-LZNA-BitKnit-decompression http://encode.ru/threads/2577-Open-source-Kraken-Mermaid-Sel...

lifthrasiir 10y ago
...and got DMCAed [1]. At the very least the discussion itself is interesting for the inside infos, though. [1] https://github.com/github/dmca/blob/master/2016/2016-08-30-Oodle.md https://github.com/github/dmca/blob/master/2016/2016-08-30-O...
- gliptic 10y ago
  That was because of the belief that he had used an illegal copy of the DLL, and that he had copied all implementation details (neither is true). A representative from RAD said they would withdraw the DMCA complaint now after that misunderstanding was cleared.