I'm extending a framework for lossy compression of multidimensional floating-point data. At some point in the pipeline, sequences of symbols from a non-uniform distribution are losslessly compressed using entropy coding. The existing software used an implementation of arithmetic coding based on this post. As an extension, I implemented a second option, rANS.

However, analyzing the results, it seems that rANS needs around 1-2% more bits to encode the same data and this pattern is consistent among many different sequences of symbols of different lengths. Yet, as far as I understand, they should both be extremely close to the entropy limit. Indeed, looking at empirical results the arithmetic coder seems to only have a constant overhead of around 32 bits (the size of its normalized state) compared to the entropy limit.

So, my question is: Is there a known phenomenon that consistently makes certain variants of rANS slightly less efficient than arithmetic coding?

Some more information that might be useful:

  • I write/read from the compressed bit stream bit by bit, which should normally lead to optimal compression.
  • I have tried using various values of l (the lower bound on the valid state interval), such as 2^20 and 2^32, but this doesn't seem to have any effect.

If this is caused by a basic error in my implementation, I apologize and will take this question elsewhere (which is also why I didn't post the relevant code here).

Update: I have now also made b a variable (the ratio in between the upper and lower bound of the valid state interval, previously hard-coded to 2). Strangely enough, increasing b from 2 to higher powers of 2 seems to have mostly removed the overhead. With b = 256 I now get ~0.25% overhead typically. However, this doesn't really make much sense to me either, since I thought increasing b improved speed (by allowing the encoder to work with bytes or groups of bytes) while decreasing efficiency.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.