Results 1 to 10 of 10

Thread: nARANS (Nania Adaptive Range Variant of ANS)

  1. #1
    Tester
    Nania Francesco's Avatar
    Join Date
    May 2008
    Location
    Italy
    Posts
    1,565
    Thanks
    220
    Thanked 146 Times in 83 Posts

    nARANS (Nania Adaptive Range Variant of ANS)

    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 !
    Attached Files Attached Files
    Last edited by Nania Francesco; 14th November 2014 at 00:24.

  2. The Following 2 Users Say Thank You to Nania Francesco For This Useful Post:

    cade (14th November 2014),encode (14th November 2014)

  3. #2
    Member
    Join Date
    Nov 2014
    Location
    California
    Posts
    122
    Thanks
    36
    Thanked 33 Times in 24 Posts
    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.
    Last edited by hexagone; 14th November 2014 at 02:52. Reason: typo

  4. The Following User Says Thank You to hexagone For This Useful Post:

    Nania Francesco (14th November 2014)

  5. #3
    Tester
    Nania Francesco's Avatar
    Join Date
    May 2008
    Location
    Italy
    Posts
    1,565
    Thanks
    220
    Thanked 146 Times in 83 Posts
    Released new nARANS real encoder/decoder v.0.2.
    Please Test !
    In comparation with fpaq0pv3 is 4x faster ( with fpaq0pv4b1 >3x ) in decompression !
    Attached Files Attached Files
    Last edited by Nania Francesco; 15th November 2014 at 14:28.

  6. #4
    Tester
    Nania Francesco's Avatar
    Join Date
    May 2008
    Location
    Italy
    Posts
    1,565
    Thanks
    220
    Thanked 146 Times in 83 Posts
    Released new NARANS adaptive Bit Coder. Slow in compression but 2-5% faster than standard bit coder in decompression!
    Attached Files Attached Files
    Last edited by Nania Francesco; 16th November 2014 at 16:24.

  7. #5
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    Tested on a 2.0 GHz T3200, Win32. I recompiled both programs for 32 bits using g++ 4.8.1 -O3.

    Code:
    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%

  8. The Following User Says Thank You to Matt Mahoney For This Useful Post:

    Nania Francesco (16th November 2014)

  9. #6
    Tester
    Nania Francesco's Avatar
    Join Date
    May 2008
    Location
    Italy
    Posts
    1,565
    Thanks
    220
    Thanked 146 Times in 83 Posts
    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.

  10. #7
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 778 Times in 485 Posts
    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.

  11. The Following User Says Thank You to Matt Mahoney For This Useful Post:

    Nania Francesco (16th November 2014)

  12. #8
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    645
    Thanks
    205
    Thanked 196 Times in 119 Posts
    Quote Originally Posted by Nania Francesco View Post
    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.
    Last edited by Jarek; 16th November 2014 at 16:08. Reason: example

  13. #9
    Tester
    Nania Francesco's Avatar
    Join Date
    May 2008
    Location
    Italy
    Posts
    1,565
    Thanks
    220
    Thanked 146 Times in 83 Posts
    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)
    Last edited by Nania Francesco; 16th November 2014 at 16:24.

  14. #10
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    645
    Thanks
    205
    Thanked 196 Times in 119 Posts
    Quote Originally Posted by Nania Francesco View Post
    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
    Last edited by Jarek; 16th November 2014 at 17:50. Reason: added second paragraph

Similar Threads

  1. Replies: 33
    Last Post: 2nd July 2018, 20:18
  2. Adaptive adaptation rate :)
    By Piotr Tarsa in forum Data Compression
    Replies: 29
    Last Post: 6th January 2012, 16:44
  3. Hashing a large range of integers to a smaller range
    By mtwaha in forum Data Compression
    Replies: 3
    Last Post: 11th April 2011, 23:27
  4. New LZW variant
    By encode in forum Forum Archive
    Replies: 14
    Last Post: 28th January 2008, 22:33
  5. New move-to-front variant?
    By Lasse Reinhold in forum Forum Archive
    Replies: 7
    Last Post: 17th September 2007, 16:05

Posting Permissions

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