In brief - anywhere you used Huffman in the past, you can use ANS instead.
ANS (or ABS) are not very useful for high end compressors. They are awkward for adaptive modeling. Even if all you care about is decode speed (so you don't mind the buffering up the models to make the encode work backwards) it's just not a big win over arithmetic coding. Things like PAQ/CM , LZMA, H264, all the high compression cases that use adaptive context models, there's no real win from ANS/ABS.
Some specific cases where I see ANS being a good win :
JPEG-ANS obviously. Won't be competitive with sophisticated coders like "packjpg" but will at least fix the cliff at low bit rate caused by Huffman coding.
JPEGNEXT-ANS. I've been thinking for a long time about writing a "JPEGNEXT". Back end coefficient classification; coefficients in each group sent by value with ANS. Front end 32x32 macroblocks with various DCT sizes. Try to keep it as simple as possible but be up to modern quality levels.
LZ-ANS. An "LZX class" (which means large window, "repeat match", entropy resets) LZ with ANS back end should be solid. Won't be quite LZMA compression levels, but way way faster.
Lossless image DPCM. ANS on prediction residual values is a clear killer. Should have a few statistics groups with block classification. No need to transmit the ANS counts if you use a parametric model ala TMW etc. Should be easy, fast, and good.
blocksort-ANS. Should replace bzip. Fast to decode.
MPEG-class video coders. Fast wavelet coders. Anywhere you are using minimal context modelling (only a few contexts) and are sending values by their magnitude (not bit plane coders).
Other?
3 comments:
Fast arithmetic "range" coders, (where you only periodically update your symbol counts) can all be ANS now.
Might be worthwhile to figure out if there's a nice way to get universal ANS codes with low redundancy.
E.g. uniform is straightforward from the construction, but already quite useful. An efficient closed-form solution for geometric with parametric p (for some range) would be really handy; you'd need an escape once your ranges get too small, but that's not too horrible.
A lot of the binary models in e.g. H.264 just end up being used for mostly geometrically distributed run lengths. A good parametric "fractional Golomb" coder could replace that usage (while still adaptively estimating the expected run length) without necessarily giving up anything.
My background is in game development, and huffman is widely accepted as the gold-standard in compressing game information before letting it loose across the network/internet connection to other machines participating in a game.. Personally, I came up with my own huffman/range-encoder hybrid that encodes/decodes like huffman but generates bitcodes using a binary search on a space of the symbol probabilities to generate bitcodes. Maybe there's something to that worth looking into? Just me fumbling around with little math background.
I've been studying more about range/arithmetic coders in an attempt to get closer to entropy with my little bastardized hybrid when I discovered ANS/FSE and the comments about it being a viable alternative, with better compression to boot.
I've been struggling to grasp the core concept of ANS/FSE, and after staying up into the wee morning hours reading Janek's paper and Yann's blog, and the intercourse of ideas on linked forums, I finally had a visualization that made sense, thanks to your blog!
My application benefits most from speed and compression (figures) and expenditure of memory is virtually a non-issue. I will be performing some further fumbling in an attempt to get my own FSE up and running.
The typical approach with networked multiplayer games is to utilize a static huffman encoding, using a fixed pre-determined/measured table of byte value probabilities. My approach with the binary-search generated bitcodes operates the same way, but with a different means of extracting bitcodes from symbol probabilities. My hope (because a lack of math background leaves you with only blind hope) was to get the best of both worlds with huffman/range. Instead I seem to have gotten the worst, and then some.
If I can get huffman speeds with range-coding compression, that is a definite win. From what I've been able to glean, it would seem that the table-based tANS is what I should be aiming for, if speed is a top priority, because pixels need cycles too!
Any input for a layman is appreciated! I have to thank you for taking the time to operate your blog, it is an invaluable resource. Thanks!
Post a Comment