# Thread: Sequential implementation of ANS-like entropy coder

1. ## Sequential implementation of ANS-like entropy coder

> What is really interesting is combining FIFO with simplicity of ANS for large alphabet

Actually I'm still intending to use rangecoders for a while.
Most of rANS optimizations are easily applicable to rc,
and there's basically no difference in performance for binary alphabets.

Also, most non-linear model components (FSM counters, logistic mixing, SSE, etc)
are not compatible with non-binary alphabets anyway,
so I think its more important to look for speed optimizations for binary coders

But if you want a FIFO ANS, I might have some ideas.
Well, its obvious that order reversing is inherent if you
Its the same as converting decimal to binary basically -
you can do FIFO decoding if you know all the coefs...
which you might actually know if you use a combinatoric model.

However, in that case either encoding would have to look like
state+=(bit?probability:0)*LUT[freq0,freq1];
or decoding like
bit = state/LUT[freq0,freq1]%SCALE > probability;

So if you require
encoding: state'=state*SCALE+symbol.low
decoding: symbol=LUT[state%SCALE]; state/=SCALE;
Then its obvious that the order would be inverted.

Still,

1) We can combine ANS w/o renorm with a high-precision rangecoder, like
https://github.com/Shelwien/stegdict.../sh_v1m128.inc

this rc supports 64-bit symbol intervals, so we can encode 64-bit
rANS states with it, and its possible to pack quite a lot into 64 bits.
For example, it can be 4 bytes with a 16-bit freqtable.

Note that the number of ANS instances in this case is potentially unlimited,
because ANS states would be properly packed.

doesn't have to come from this specific state.

I mean, you always use
state'=(state/symbol.range)*SCALE+symbol.low+(state%symbol.range )

But the important part is actually

while the log2(symbol.range) bits of payload can be taken anywhere,
like from another block of data, or another interleaved stream at least.  Reply With Quote

2. ## Thanks (2):

encode (2nd July 2017),RamiroCruzo (2nd July 2017)

3. Indeed it would be nice to be able to remove the ANS need of buffer: of the actual data for i.i.d. source or simple context models (e.g. Markov), or additionally the probabilities for adaptive models.
The advantage of ANS is mainly the large alphabet case: to reduce the number of steps (and remove binarization), like LZMA -> LZNA using 16 size (4bit) alphabet with vectorized probability adaptation and symbol search.
I wonder if similar approach could be used to fill the cliff in Pareto frontier between zpaq and LZNA - context mixing on not binary but 4bit symbols?

Returning to FIFO ANS, prefix codes can be seen as a special case, e.g. A->00, B->010, C->011, D->1 corresponds to AABCDDDD symbol spread for tANS.
So there is a large family of tANS for which we can have FIFO - the question is if it can be enlarged?

For binary alphabet there are a few approaches for FIFO finite state machines, like quasi AC or M/Q code e.g. from CABAC.
However, taking it to larger alphabet is rather impractical due to much faster growth than for tANS: of memory requirements and preparation costs.
For this task there is a tough need to develop field combining automata theory with information theory - seeing states of automate as buffer containing fractional amounts of bits, like lg(x) in tANS automate.

Another question is to cross the arithmetic: FIFO RC - LIFO rANS boundary, but it might be impossible (?)  Reply With Quote

4. > context mixing on not binary but 4bit symbols?

LZNA approach should be compatible with linear mixing.
For example of bytewise linear mixing, see https://encode.su/threads/541-Simple...ll=1#post10847
It might be also still possible to apply logistic updates to linear mixer weights.
Some examples of linear vs logistic mixing results with optimized parameters:

Btw, as to FIFO huffman vs FSE, there's also my "fritcode" idea.
That is, if we'd work with "bits" that have a non-uniform probability (ie p0=0.9; p1=0.1), it becomes
possible to build optimal bitcodes for non-power-of-2 probabilities.
Then the skewed bitcode can be encoded with a secondary EC - with all bits having the same probability it should be simple/fast enough.
There's more in this post - https://encode.su/threads/?p=22277&pp=1 .  Reply With Quote

5. ## Thanks:

RamiroCruzo (2nd July 2017)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•