rANS is one of a family of entropy coding methods that we can use to compress a stream of symbols losslessly. For some set of symbols , w/ accompanying probabilities , Shannon’s source coding theorem tells us that symbol with probability carries exactly bits of information. A symbol that shows up half the time costs 1 bit. One that shows up a quarter of the time costs 2 bits. One that shows up 3/8 of the time costs bits.
Huffman coding can help us cleanly with the first two. But it uses fixed width symbols. The third symbol is going to end up taking bits to decode. The result is that we can’t get perfect lossless compression.
rANS is one of a set of arithmetic coding methods that can achieve perfect compression, by not using fixed width symbols. Instead, the stream of bits is encoded into an integer, by a series of reversible arithmetic operations.
Encoding a sequence into an integer
The code is a single integer, call it the state . Each symbol we encode transforms through some arithmetic operation. The operation has to be reversible, because the decoder needs to recover both the symbol and the previous state from the new one.
The specific operation rANS uses is:
where is the frequency of symbol in our probability table, is its cumulative frequency (the sum of frequencies of all symbols that come before it in our enumeration), and is the total frequency . For our alphabet, that’s:
Symbol f_s c_s
A 4 0
B 3 4
C 1 7So .
Let me walk through encoding the sequence starting from some seed state . Pick 13 arbitrarily for now; we’ll talk about why the seed value matters later.
Encode (, ):
Encode (, ):
Encode (, ):
The state walked . After encoding three symbols, our whole “code” is the single integer . The entire message is packed into that number.
Now the payoff. Let’s check how much the state grew in bits. It started at bits. It ended at bits. We added bits total. Shannon says our three symbols carry bits of information. The state grew by almost exactly that muchThe per-step growth wasn’t exactly 1, 1.415, 3 bits either. Encoding grew the state by bits, less than Shannon’s bit for . Encoding grew it by bits, a hair over Shannon’s . These individual wobbles are a quirk of encoding integer states. Each step rounds slightly up or down depending on where lands relative to . The rANS guarantee is asymptotic, so over many symbols the wobbles average out and the per-symbol cost converges to the Shannon limit..
Importantly, we didn’t round anything to the nearest bit. Encoding grew the state by bits. Fractional bits!
Where did they come from? The formula again:
To first order, . So grows by approximately , which is the Shannon information content of .
One way to think of rANS encoding is as a change of base that smuggles in the symbol along the way. In base , the number has last digit and “rest” . In base , the encoded has the same rest, but the last digit is promoted from a digit in to a digit in , specifically . That promotion is where the symbol is injected: the promoted digit lands inside symbol ‘s range . The decoder, which we’ll build next, reads , sees which range the value falls in, and recovers both the symbol and the remainder.
Decoding reverses it
To decode, we invert the encoding. Given a state , recover the last-encoded symbol and the previous state in three steps:
- Read the low digit .
- Find the symbol whose range contains it, i.e. .
- Reconstruct the previous state:
Walking back from our encoded state :
Decode from :
- , which lies in ‘s range . Symbol is .
- Previous state: .
Decode from :
- , which lies in ‘s range . Symbol is .
- Previous state: .
Decode from :
- , which lies in ‘s range . Symbol is .
- Previous state: .
The state walked , the mirror image of the encoding walk, and we’re back at the seed. The decoded symbols appeared in the order .
Note the order. We encoded but decoded . rANS is last-in-first-out. The encoder behaves like a stack, and the decoder pops from it. In practice this means real rANS encoders process their input message in reverse order, so that the decoder, running forward through the compressed state, produces symbols in the correct forward order.
Renormalization
Until now, our compressed “code” has been a single integer . That’s mathematically tidy but not directly implementable. For a long input, grows linearly with the message length, so itself grows exponentially, and no fixed-width integer can hold it.
The fix is renormalization. The idea is we keep the state in a fixed range for some chosen and base . Common choices are for a bit-level compressed stream or for a byte-level one. Before encoding any symbol, check whether encoding would push the state above . If so, shift the low base- digits of out to an output stream, one at a time, until is small enough that encoding will leave the state inside .
This emitted stream is the actual output of the encoding algorithm. Instead of one giant integer, we get a stream of bits or bytes spilled during encoding, plus a small residual state (always in ) left over at the end. The compressed output is the concatenation of the two.
Decoding reverses the process. Starting from the residual state, decode a symbol via the formula from the previous section, which shrinks the state by a factor of about . If the state has dropped below , refill it by pulling digits from the stream back into the state as low digits, until the state is in again. We then just repeat until the stream is empty and the state matches the seed.
Putting it together
Here is complete rANS encode and decode, in pseudocode. Pick a state range , share the frequency table and the total between encoder and decoder, and that’s the whole scheme.
def encode(message, freq, M, L, b):
x = L # seed state
stream = []
for s in reversed(message): # process LIFO
f, c = freq[s]
while M * x >= b * L * f: # renormalize: spill low digit
stream.append(x % b)
x //= b
x = (x // f) * M + c + (x % f) # apply encode formula
return x, stream # residual state + digits
def decode(x, stream, freq, M, L, b, n):
slot_to_symbol = build_slot_table(freq) # e.g. [A,A,A,A,B,B,B,C]
message = []
for _ in range(n):
slot = x % M
s = slot_to_symbol[slot]
message.append(s)
f, c = freq[s]
x = (x // M) * f + slot - c # apply decode formula
while x < L and stream: # renormalize: refill low digit
x = x * b + stream.pop()
return messageslot_to_symbol is a lookup table of size holding which symbol owns
each of the slot positions. For our running alphabet with , it
is the list This is an way of solving the problem of finding the correct
range. You could also search for it..
The decode step is cheap. Per symbol it is one mod, one table lookup, one integer division, one multiply, one add, one subtract, and possibly a few digit-reads from the stream. No variable-length prefix code, no bit-by-bit decoding. Each symbol takes near-constant work, which is why rANS and its variants are popular in performance-sensitive compressors.
Encoding and decoding are mirror images. Encoding processes the message in
reverse and pushes digits onto the stream. Decoding processes the stream in
reverse (via pop) and produces the message in forward order. The whole
scheme is LIFO throughout: in symbols, and in stream digits.
That is rANS. A single integer carries fractional bits of information per symbol, arithmetic operations encode and decode reversibly, and renormalization keeps the whole thing to a bounded state plus a digit stream.