11
$\begingroup$

In trying to understand the relationships between Huffman Coding, Arithmetic Coding, and Range Coding, I began to think of the shortcomings of Huffman coding to be related to the problem of fractional bit-packing.

That is, suppose you have 240 possible values for a symbol, and needed to encode this into bits, you would be stuck with 8 bits per symbol, even though you do not need a "full" 8, as 8 can express 256 possible values per symbol. A solution to this problem is something I've seen referred to as "fractional bit packing", where you are able "bitshift" by a non-power of two using multiplication. Just like multiplication of powers-of-two are shifting x * 2 == x << 1 and x * 4 == x << 2 and so on for all powers of two, so too you can "shift" with a non-power-of-2 by multiplying instead, and pack in fractional-bit-sized symbols.

The problem is similar with Huffman coding: you end up with codes that must be non-fractionally-bit-sized in length, and therefore it has this packing inefficiency. However, you can't just use the solution of fracitonal-bit-packing, because this solution assumes fixed sized symbols.

The question is, are there any papers or solutions to improve on huffman coding with a similar idea to fractional-bit-packing to achieve something similar to arithmetic coding? (or any results to the contrary).

$\endgroup$
  • 1
    $\begingroup$ Arithmetic coding is already optimal. There is no need to improve it. $\endgroup$ – Yuval Filmus Nov 8 '15 at 22:35
  • $\begingroup$ @YuvalFilmus yes i meant, how to improve on huffman coding to bring it up to par with arithmetic coding. $\endgroup$ – Realz Slaw Nov 8 '15 at 22:45
  • 1
    $\begingroup$ Just as a suggestion, you may find Asymmetric Numeral System (ANS) coding easier to understand than arithmetic coding. In particular, it's a bit easier to see that particular formulation as "fractional bit packing". $\endgroup$ – Pseudonym Nov 9 '15 at 6:26
  • $\begingroup$ @Pseudonym I found this page that seems to make this connection between rANS and Huffman Coding. Can't say I understand it yet, but I think it suffices. If you make the comment an answer I'll accept. $\endgroup$ – Realz Slaw Nov 16 '15 at 23:55
  • $\begingroup$ @YuvalFilmus I hope I've made the case that arithmetic coding did need improvement, and ANS is an improvement. $\endgroup$ – Pseudonym Nov 17 '15 at 2:53
12
$\begingroup$

Let's look at a slightly different way of thinking about Huffman coding.

Suppose you have an alphabet of three symbols, A, B, and C, with probabilities 0.5, 0.25, and 0.25. Because the probabilities are all inverse powers of two, this has a Huffman code which is optimal (i.e. it's identical to arithmetic coding). We will use the canonical code 0, 10, 11 for this example.

Suppose our state is a large integer, which we will call $s$. You can think of encoding as a function which takes the current state, and a symbol to encode, and returns the new state:

$$\begin{align*} \hbox{encode}(s, A) &= 2s\\ \hbox{encode}(s, B) &= 4s + 2\\ \hbox{encode}(s, C) &= 4s + 3\\ \end{align*}$$

So let's start with the state 11 (which is 1011 in binary), encode the symbol B. The new state is 46, which is 101110 in binary. As you can see, this is the "old" state with the sequence 10 added to the end. We have essentially "output" the bit sequence 10.

So far, so good.

Now think for a moment about how arithmetic coding works. If you put the probabilities over a common denominator, the symbol A actually represents the range $[\frac{0}{4},\frac{2}{4})$, the symbol B represents the range $[\frac{2}{4},\frac{3}{4})$ and the symbol C represents the range $[\frac{3}{4},\frac{4}{4})$.

Basically what we're doing here is multiplying everything by the common denominator. Imagine that the state was actually in base 4. Encoding a symbol B is really outputting the digit 2 in that base, and encoding a symbol C is outputting the digit 3 in that base.

However, symbol A is a little different, because it isn't a whole digit in base 4.

Instead, we can think of the alphabet as the set of symbols A_0, A_1, B, C, with equal probability. This, again, has an optimal Huffman code 00, 01, 10, 11. Or, again, we can think of this in base 4. To encode a symbol, we just do:

$$\begin{align*} \hbox{encode}(s, A_0) &= 4s + 0\\ \hbox{encode}(s, A_1) &= 4s + 1\\ \hbox{encode}(s, B) &= 4s + 2\\ \hbox{encode}(s, C) &= 4s + 3 \end{align*}$$

So now it's clear how to encode symbols B and C, but to encode a symbol A, we have a choice. Which of $A_0$ and $A_1$ should we use?

Now here's the clever idea: we steal one bit of information from the state $s$:

$$s' = \left\lfloor \frac{s}{2} \right\rfloor$$ $$i = s \bmod 2$$

and then $\hbox{encode}(s', A_i)$.

Using our previous example, $s=11$, we find that $s'=5$ and $i=1$, and then $\hbox{encode}(5, A_1) = 4\times 5+1 = 21$. The new state is 10101 in binary.

Now this doesn't produce exactly the same bit output as Huffman coding, but it does generate an output which has the same length. And what I hope you can see is that this is also uniquely decodable. To decode a symbol, we take the remainder when divided by 4. If the value is 2 or 3, then the symbol is B or C respectively. If it's 0 or 1, then the symbol is A, and then we can put the bit of information back by multiplying the state by 2 and adding either 0 or 1.

The nice thing about this approach is that it extends naturally to fractional-bit encoding, when the numerator and/or denominator of the probabilities are not powers of two. Suppose we have two symbols, A and B, where the probability of A is $\frac{3}{5}$ and the probability of B is $\frac{2}{5}$. Then we can encode a symbol with:

$$\begin{align*} \hbox{encode}(s, A_0) &= 5s + 0\\ \hbox{encode}(s, A_1) &= 5s + 1\\ \hbox{encode}(s, A_2) &= 5s + 2\\ \hbox{encode}(s, B_0) &= 5s + 3\\ \hbox{encode}(s, B_1) &= 5s + 4 \end{align*}$$

To encode the symbol A, we take $s' = \left\lfloor \frac{s}{3} \right\rfloor$ and $i = s \bmod 3$, and then $\hbox{encode}(s', A_i)$.

This is equivalent to arithmetic coding. It's actually a family of methods known as Asymmetric Numeral Systems, and was developed over the last few years by Jarek Duda. The meaning of the name should be obvious: to encode a symbol with probability $\frac{p}{q}$, you conceptually steal a base-p digit from the state, and then add a base-q digit. The asymmetry comes from interpreting the state as a numeral in two different bases.

The reason why it's a family of coding methods is that what we've seen here is impractical by itself; it needs some modifications to deal with the fact that you probably don't have infinite-precision integers to manipulate the state variable efficiently, and there are various ways that you can achieve this. Arithmetic coding, of course, has a similar issue with precision for its state.

Practical variants include rANS (the "r" means "ratio") and tANS ("table-driven").

ANS has a few interesting advantages over arithmetic coding, both practical and theoretical:

  • Unlike arithmetic coding, the "state" is a single word, rather than a pair of words.
  • Not only that, but an ANS encoder and its corresponding decoder have identical states and their operations are completely symmetric. This raises some interesting possibilities, such as that you can interleave different streams of encoded symbols and everything synchronises perfectly.
  • Practical implementations need, of course, to "output" information as you go, and not just collect it in a big integer to be written at the end. However, the size of the "output" can be configured in return for (usually modest) compression loss. So where arithmetic coders must output a bit at a time, ANS can output a byte or a nybble at a time. This gives you a direct tradeoff between speed and compression.
  • It appears to be about as fast on current-generation hardware as binary arithmetic coding, and hence competitive with Huffman coding. This makes it much faster than large-alphabet arithmetic coding and its variants (e.g. range coding).
  • It appears to be patent-free.

I don't think I'm ever going to do arithmetic coding again.

$\endgroup$
  • 3
    $\begingroup$ Now that is the clearest explanation on ANS encoding that I've ever seen. $\endgroup$ – Michael Deardeuff May 20 '16 at 23:47
2
$\begingroup$

As a simple example, if you had three symbols with probability 1/3rd each, your optimal Huffman encoding would use the three symbols 0, 10 and 11 with an average of 5/3rd bits.

There are 243 symbols created by concatenating 5 of the original symbols, each with probability 1/243. Which is much closer to 1/256. The optimal Huffman encoding will encode 13 of these groups in 7 bits and 230 groups in 8 bits, for an average of 7.9465 bits per group or 1.5893 bits per original symbol, down from 1.6667 bits for the original Huffman coding, with arithmetic coding taking 1.5850 bits.

So in theory you could just combine two symbols each into one larger symbol, or three symbols each into one larger symbol, and use Hufman coding for the combinations.

$\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.