Hacker News Reader

Comment by binarycrusader | Hacker News Reader

> 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

...and here:

http://encode.ru/threads/2492-Kraken-compressor

http://cbloomrants.blogspot.ca/2016_05_01_archive.html

View on HN

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-en... [1] http://encode.ru/threads/1821-Asymetric-Numeral-System?p=360... [2] https://github.com/rygorous/ryg_rans

Yeah, it's all very hazy, and since RAD is (understandably) proprietary, it's difficult to figure out exactly when who did what.

Before Yann, this ANS variant was implemented by Andrew Polar in 2008: http://www.ezcodesample.com/abs/abs_article.html Here is a list of implementations: http://encode.ru/threads/2078-List-of-Asymmetric-Numeral-Sys...

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-Sel...

...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-O...

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.

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-mer...

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/

Reply on news.ycombinator.com