Finite State Entropy - A new breed of entropy coder
fastcompression.blogspot.fr
Finite State Entropy - A new breed of entropy coder
1–10 of 14 posts
Re: Finite State Entropy - A new breed of entropy coder
#2Well, this is interesting.
I toyed around with entropy encoding at one point based on a republished copy of an old Dr. Dobbs' Journal article I found, and I managed to cleanly reimplement the described algorithm in Python and reproduce the example mentioned in the article... but eventually I hit a problem I wasn't smart enough to debug. I'm eager to see whether this new algorithm is more approachable.
Re: Finite State Entropy - A new breed of entropy coder
#3There is a nice treatment on entropy coders in Managing Gigabytes (http://ww2.cs.mu.oz.au/mg/). I highly recommend the text as it gives good background on entropy encodings and it also takes a nice engineering approach to implementation.
Re: Finite State Entropy - A new breed of entropy coder
#4"In a nutshell, this coder provides the same level of performance as Arithmetic coder, but only requires additions, masks, and shifts."
Didn't IBM's Q-Coder also make the same claims?
Here's another one: http://www.gvu.gatech.edu/people/official/jarek/courses/7491...
Re: Finite State Entropy - A new breed of entropy coder
#5This was a nice article.
In the comments Jarek Duda discusses some of the more technical details of the implementation and of his ANS paper that enabled this writeup. One cool thing I noticed is this:
Another advantage of ANS is that we can slightly perturb
the initialization procedure using a pseudo-random number
generator initialized with cryptographic key (e.g. and
also the number of block): for example choosing between
the lowest weight symbol and the second best one.
This way we get simultaneously a decent encryption for free.
Re: Finite State Entropy - A new breed of entropy coder
#6"In a nutshell, this coder provides the same level of performance as Arithmetic coder, but only requires additions, masks, and shifts." Didn't IBM's Q-Coder also make the same claims? Here's another one: http://www.gvu.gatech.edu/people/official/jarek/courses/7491...
The Howard-Vitter coder only works for binary alphabet (0/1).
Re: Finite State Entropy - A new breed of entropy coder
#7"In a nutshell, this coder provides the same level of performance as Arithmetic coder, but only requires additions, masks, and shifts." Didn't IBM's Q-Coder also make the same claims? Here's another one: http://www.gvu.gatech.edu/people/official/jarek/courses/7491...
Same of Q-Coder :
"The Q-Coder is a new form of adaptive binary arithmetic coding"
Re: Finite State Entropy - A new breed of entropy coder
#8Arithmetic coding, one of the early victims of software patents.
Re: Finite State Entropy - A new breed of entropy coder
#9How does it compare to the algorithm used in FLAC or mpeg4 lossless? Is there a reasonable way to benchmark the differences?
https://en.wikipedia.org/wiki/Golomb_coding#Simple_algorithm
Re: Finite State Entropy - A new breed of entropy coder
#10How does it compare to the algorithm used in FLAC or mpeg4 lossless? Is there a reasonable way to benchmark the differences? https://en.wikipedia.org/wiki/Golomb_coding#Simple_algorithm
Golomb is way too static, it doesn't compress as well as Huffman, let alone FSE.