Why Is Arithmetic Coding Better Than Huffman Coding?

Arithmetic coding surpasses Huffman coding by representing an entire message as a single fractional number within a subinterval of zero to one, rather than assigning a separate integer-length codeword to each symbol. This approach eliminates the rounding overhead inherent in Huffman coding, allowing arithmetic coding to achieve compression ratios that closely approach the theoretical Shannon entropy limit. In classical computing, this makes arithmetic coding especially effective when symbol probabilities are highly skewed or when alphabets are small.

The Integer-Bit Limitation of Huffman Coding

Huffman coding works by building a prefix-free binary tree where more frequent symbols receive shorter bit sequences and less frequent symbols receive longer ones. While optimal for symbol-by-symbol coding, every symbol must be mapped to a whole number of bits.

According to Shannon's source coding theorem, the ideal average code length for a symbol \(s\) with probability \(p(s)\) is its self-information:

\[I(s) = -\log_2 p(s)\]

When \(p(s)\) is not an exact power of two, \(-\log_2 p(s)\) is a fractional number. Huffman coding must round this up to an integer bit length. For example, if a symbol has a probability of \(0.9\), its ideal information content is \(-\log_2(0.9) \approx 0.152\) bits. However, Huffman coding must assign it at least \(1\) bit, resulting in a significant \(0.848\) bits of wasted space per occurrence.

Encoding a Message as a Fractional Interval

Arithmetic coding bypasses the integer-bit constraint by treating the entire input sequence as a single unit. It starts with the half-open interval \([0, 1)\) and iteratively narrows it down as each symbol in the message is processed.

The process follows these steps:

  1. Partition the current interval: The current interval \([L, H)\) is divided into subintervals proportional to the probabilities of each symbol in the alphabet.
  2. Select the subinterval: When the next symbol \(s_i\) is read, the encoder selects the subinterval corresponding to \(s_i\) as the new active interval \([L_{new}, H_{new})\).
  3. Update bounds: If \(s_i\) has cumulative probability range \([C_{low}, C_{high})\) within the model, the new bounds are computed as:

\[L_{new} = L + (H - L) \cdot C_{low}\] \[H_{new} = L + (H - L) \cdot C_{high}\]

After all symbols in the message have been processed, the encoder outputs any single binary fraction that lies inside the final interval \([L_{final}, H_{final})\). Because a narrower interval requires more bits to specify a unique point within it, probable sequences produce wider intervals and shorter bitstrings, while improbable sequences produce narrower intervals and longer bitstrings.

Approaching the Shannon Entropy Limit

For a message of length \(N\), the width of the final interval is equal to the product of the probabilities of all symbols in the message:

\[W = \prod_{i=1}^{N} p(s_i)\]

To uniquely identify a number within an interval of width \(W\), the encoder needs approximately \(-\log_2(W)\) bits. Using the properties of logarithms, this becomes:

\[-\log_2\left(\prod_{i=1}^{N} p(s_i)\right) = \sum_{i=1}^{N} -\log_2 p(s_i)\]

This sum equals the exact total information content of the message, plus at most \(1\) or \(2\) extra bits of overhead for the entire message to terminate the binary fraction. Unlike Huffman coding, where rounding errors accumulate with every single symbol, arithmetic coding amortizes this tiny overhead across the whole message, converging to the Shannon entropy \(H(X)\) as \(N\) grows large.

Practical Considerations in Classical Computing

In classical computing, infinite-precision real numbers cannot be stored directly in finite hardware registers. Practical implementations of arithmetic coding use fixed-point integer arithmetic (such as 32-bit or 64-bit integers) combined with a technique called renormalization. Whenever the most significant bits of \(L\) and \(H\) match, those bits are shifted out to the output stream, and the remaining interval is scaled up to maintain precision.

Additionally, arithmetic coding cleanly separates the probability model from the coding engine. This allows the probability distribution to be adaptive—updating dynamically as the message is read—without needing to rebuild a Huffman tree, making it the foundation for modern compression standards like JPEG, H.264, and H.265.