Range coding

Since that time, patents on various well-known arithmetic coding techniques have also expired.

Thus range coding can achieve greater compression ratios than the one-bit-per-symbol lower bound on Huffman coding and it does not suffer the inefficiencies that Huffman does when dealing with probabilities that are not an exact power of two.

The decoder must have the same probability estimation the encoder used, which can either be sent in advance, derived from already transferred data or be part of the compressor and decompressor.

Because all five-digit integers starting with "251" fall within our final range, it is one of the three-digit prefixes we could transmit that would unambiguously convey our original message.

This is illustrated in the following code: To finish off we may need to emit a few extra digits.

One problem that can occur with the Encode function above is that range might become very small but low and low+range still have differing first digits.

When this happens we need to fudge a little, output the first couple of digits even though we might be off by one, and re-adjust the range to give us as much room as possible.

For example, imagine the input stream has led the encoder to the right-open interval [59888, 60188), that is, low = 59888 and range = 300.

Base 10 was used in this example, but a real implementation would just use binary, with the full range of the native integer data type.

Decoding uses exactly the same algorithm with the addition of keeping track of the current code value consisting of the digits read from the compressor.

In other words, range encoders tend to use bytes as coding digits, rather than bits.