nARANS (Nania Adaptive Range Variant of ANS)

[Nania Francesco]

I could feel with Matt Mahoney successfully only for the code , but expect your comments regarding the program recall at least the intellectual fatherhood of creation but that was definitely from a native code originally created by others intend to make available to everyone (if we consider that rANS is different from the traditional Range Coder). This is the code of nARANS (Nania -Adaptive Range Variant of ANS -) and expect them to help me to improve it without upsetting the compatibility. Naturally this is part of LZA archiver !

[hexagone]

As with many coders, one can decide to choose adaptive or pre-scanned (to compute frequency distribution first). It is always a tradeoff. Your code is semi-adaptive which means that on the encoder side you do not pre-compute the frequency distribution and you do not need to store the frequencies but you need to rescale periodically. You lose a bit of accuracy so the space advantage of not storing the frequencies is lost. Speedwise, not sure whether rescaling offsets the time used to compute data frequencies. On the decoder side, the rescaling is going to affect negatively the speed.

[Nania Francesco]

Released new nARANS real encoder/decoder v.0.2.
Please Test !
In comparation with fpaq0pv3 is 4x faster ( with fpaq0pv4b1 >3x ) in decompression !

[Nania Francesco]

Released new NARANS adaptive Bit Coder. Slow in compression but 2-5% faster than standard bit coder in decompression!

[Matt Mahoney]

Tested on a 2.0 GHz T3200, Win32. I recompiled both programs for 32 bits using g++ 4.8.1 -O3.

C:\tmp>timer32 narans_bit \res\enwik8
 Nania - Adaptive Range Variant of ANS -
nARANS bit encode:
40023321144 clocks, 400.2 clocks/symbol (  4.8MiB/s)
nBLK: 100000000 to 61345753
nARANS bit decode:
13246145064 clocks, 132.5 clocks/symbol ( 14.4MiB/s)
decode ok!

Commit   =    315524 KB  =    309 MB
Work Set =    259140 KB  =    254 MB

Kernel Time  =     0.561 =    2%
User Time    =    27.206 =  100%
Process Time =    27.768 =  102%
Global Time  =    27.159 =  100%

C:\tmp>timer32 narans c \res\enwik8 enwik8.narans
 nARANS v.02
 Copyright(C) 2014 by NANIA Francesco (Italy)
nARANS encode:
6500777736 clocks, 65.0 clocks/symbol ( 29.3MiB/s)
nBLK: 100000000 to 63488269

Commit   =      1652 KB  =      2 MB
Work Set =      2668 KB  =      3 MB

Kernel Time  =     0.390 =    9%
User Time    =     3.026 =   76%
Process Time =     3.416 =   86%
Global Time  =     3.956 =  100%

C:\tmp>timer32 narans d enwik8.narans enwik8
 nARANS v.02
 Copyright(C) 2014 by NANIA Francesco (Italy)
nARANS decode:
nBLK: 63488273 to 100000000
4508861736 clocks, 45.1 clocks/symbol ( 42.2MiB/s)

Commit   =      1776 KB  =      2 MB
Work Set =      2796 KB  =      3 MB

Kernel Time  =     0.218 =    7%
User Time    =     1.981 =   66%
Process Time =     2.199 =   73%
Global Time  =     2.995 =  100%

[Nania Francesco]

Thanks Matt for the test. Regarding nARANS definitely has already been inserted into the LZA code while nARANS bit coder I don't see currently a simple use and quick in my program. However there would be a chance to further improve both. The problem with this system is that in compression you should do a reconstruction of frequency or probability in reverse, thus avoiding to use a buffer.

[Matt Mahoney]

I looked at the source code and I don't see an easy way to use it for higher level context modeling except for something like PPMd. You have to be able to update the model quickly somehow.

[Jarek]

The problem with this system is that in compression you should do a reconstruction of frequency or probability in reverse, thus avoiding to use a buffer.

I don't understand the problem?
While encoding you go in standard forward direction, filling the buffer with (s_i, D_i) pairs: that the i-th symbol is s_i from probability distribution D_i. Then use entropy coder in backward direction (using e.g. table[D_i][x]).
Now while decoding you don't change anything.

For example,
imagine we have order 1 bit coder: the next bit after "0" has D0 (binary) probability distribution, the next bit after "1" has D1 probability distribution.
Let say we want to encode
1100101
sequence (let say starting from distribution D)
encoder puts pairs into buffer:
(1,D), (1,D1), (0,D1), (0,D0), (1,D0), (0,D1), (1, D0)
and then encodes them in backward order - starting with e.g. encodingTable[D0][x,1].

Now decoder knows to start with D0, decodes the first symbol (1) using decodingTable[D0][x].
Thanks to it, it knows to use D1 for the next step - uses decodingTable[D1][x] to decode it (1) ... and so on.

[Nania Francesco]

You told yourself not to be an expert programmer. If we take as an example LZMA algorithm LZ77 family this has much of its power to the choices that he makes in a linear fashion with bit coder. Think in a linear fashion back is almost impossible, unless you put a trick as I put I. With my solution the coder is independent of the context in which it is being linked only to the encoded symbol (single bit encoder) and frequency + cum. However, if we have a prediction system that knows how to move forward and back does not become more necessary a buffer to store the frequency but only the symbol. I think there is a correlation between low-range and the rans or X. In my system encoding of frequency or probability should occur linearly while is just writing X which is in reverse order. X is nothing but the other side of the coin of the old code that was calculated in the old range coder.

What you are saying already I believe you did!

Released new NARANS adaptive Bit Coder. Slow in compression but 2-5% faster than standard bit coder in decompression!
Attached Files Attached Files
File Type: zip Narans Bit v0.zip (50.0 KB, 13 views)

[Jarek]

Think in a linear fashion back is almost impossible(...)

And you don't have to if storing (s_i, D_i) pairs - just go forward like for range coding: writing the pairs.
Only entropy coding is backward: using the stored "D_i" for given step (or other identification of context) - instead of trying to infer it somehow "thinking back".

In many cases there are also simpler ways, like entropy coder looking at the previous symbol for order 1.
However, writing (s_i, D_i) pairs in a buffer is the ultimate way - whatever you can do with range coding, you can straightforward do this way using ANS.

Regarding correspondence with range coding - in a given moment its internal state contains lg(total length / current range) bits of information.
In contrast, the current informational content of ANS automaton is ~ lg(x) bits.
ANS kind of allows to get rid of the "Low" value.
see slide 7: https://dl.dropboxusercontent.com/u/12405967/ANSsem.pdf