3
$\begingroup$

The top two competing entropy coders at the moment are Arithmetic Coding (AC) and Asymmetrical Number Systems (ANS).

A very interesting difference between the two is that AC is FIFO and ANS is LIFO. That is, in AC the first symbol you encode into the bitstream is also the first symbol you decode. However with ANS the last symbol you encode is the first symbol you decode.

Is there a fundamental difference between these approaches? Could one be converted into the other? What are the advantages/disadvantages of the two approaches?

$\endgroup$
  • $\begingroup$ Exercise: Show that the $k$-th order empirical entropy of a string is equal to that of the reversed string. $\endgroup$ – Pseudonym Jul 5 at 4:38
2
$\begingroup$

LIFO and FIFO encoders with adaptive models are equally capable, with minor implementation differences.

Fabian Giesen writes about this in a blog post:

Reverse encoding

As mentioned above, ANS coders are LIFO: whatever order you encode symbols in, the decoder will produce them in the opposite order. All my ANS coders (including the public ryg_rans) use the convention that the encoder processes the data in reverse (working from the end towards the beginning), whereas the decoder works forwards (beginning towards end).

With a static model, this is odd, but not especially problematic. With an adaptive model, decoder and model have to process data in the same direction, since the decoder updates the model as it goes along and needs current model probabilities to even know what to read next. So the decoder and the model want to process data in the same direction (forward being the natural choice), and the rANS encoder needs to be processing symbols in the opposite order.

To reiterate, in a FIFO coder,

  • Run the model forwards on the data to obtain intervals corresponding to estimated probabilities
  • Run the encoder forwards on this list of intervals.
  • Run the decoder, generating the decompressed data in its original order.

In a LIFO coder:

  • Run the model forwards on the data to obtain intervals
  • Run the encoder in reverse on this list of intervals. Streaming is done by encoding in blocks, which can be as large as your memory capacity.
  • Run the decoder, generating the decompressed data in its original order.
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.