If anybody (like me) would think that ANS will not bring any more surprises ...

While rANS allowed to reduce the number of multiplications of range coding from 2 to 1 ... this time we will reduce it to 0!

The idea comes from Yann's remark that we can see Huffman decoder as a special case of tANS decoder - when symbols are spread in ranges of 2^k size.

So what if we get rid of the "q=2^k" restriction and use q_s ~ L*p_s quantization for sizes of symbol ranges instead - you can test it in the last version of toolkit.

Unfortunately dH does not decrease to 0 with L as previously - it stops at a comparable rate as Huffman (usually better, but sometimes slightly worse).

What is interesting about this spreading in ranges is thatit allows to further simplify coding - to single addition and renormalization.

In rANS we have used:

p[s] ~ q[s]/M quantization (M divides L, both are a power of 2)

encoding:

C(s,x) = M floor(x / q[s]) + mod(x , q[s]) + B[s]

where B[s] = q[0] + ... + q[s-1]

decoding:

s = s(x mod M)

D(x) = (s, q[s] floor(x / M) + mod(x , M) - B[s])

where s is such B[s] <= mod(x , M) < B[s+1]

and we need normalization to return to x in I = {L,..., bL-1} range.

Let us choose M=L, b=2 degenerate rANS case. Equivalently, take tANS, b=2. Use quantization to L denominator:

p[s] ~ q[s]/L

This time L=M can be chosen as any number, making quantization trivial, e.g. q[s]=round(2^R * p[s]) and then L=sum_s q[s].

Now spread tANS symbols in ranges: symbol s in {B[s], ..., B[s+1]-1} positions

where B[s] = L + q[0] + ... + q[s-1] (larger by L this time)

x is in I = {L , ... , 2L-1} range, symbol s encodes from {q[s], ..., 2q[s] - 1} range

decoding step is

s = s(x); // like for rANS, different approaches possible

x = q[s] + x - B[s]; // the proper decoding step

while (x<L) x = x<<1 + "bit from stream"; // renormalization

encoding s:

while (x >= 2q[s]) {produce(x&1); x >>=1;} // renormalization

x = B[s] + x - q[s]; // the proper coding step

We get kind of extension of Huffman concept (it would be Huffman when all q are powers of 2) -with trivial quantization (instead of costly tree building) andusually slightly better rate (due to using more accurate probabilities).

It should be slightly faster than rANS at cost of slightly worse compression rate (comparable to Huffman) - possible SIMD or single step renormalization using CountLeadingZeros operation - maybe it could be useful for some ultrafast e.g. texture compression?

Obviously it can be simplified by storing B[s] - q[s].

dH depends on frequency order, but it is not a simple dependence (to work out).

Any good name for this Huffman-like variant? (hANS?)

Any more of interesting variants ... ?

------------------------------------

Example:For q[0]=1, q[1]=3, L=M=4, I={4,5,6,7}, the first position corresponds to '0', the other three to '1'

B[0]=L=4, B[1]=L+q[0]=5

B[0]-q[0]=3, B[1]-q[1]=2

Now from state x=4 we decode to symbol 0, new x = 4 - 3 = 1, then you read 2 bits to get back to I

From state 5,6,7 we decode to symbol 1, new x-=2 is 3,4,5, the renormalization reads 1 (for 3) or 0 (for 4,5) bits to get back to I.

Encoding is opposite: first you renormalize to get correspondingly to {1} or {3,4,5} range, then add correspondingly 3 or 2.