2
$\begingroup$

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.

$\endgroup$

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.