Results 1 to 4 of 4

Thread: rANS tutorial

  1. #1
    Member
    Join Date
    Nov 2018
    Location
    London
    Posts
    2
    Thanks
    0
    Thanked 2 Times in 1 Post

    rANS tutorial

    I've written this tutorial paper on rANS, intended to be brief and accessible, with just enough mathematical detail to prove worst-case bounds on compression rate. This will eventually form part of my PhD thesis, which I'm in the process of writing atm.

    https://arxiv.org/abs/2001.09186

    There's pseudo-code in the paper as well as a Python demo at https://github.com/j-towns/ans-notes...master/rans.py.

    Obviously credit to Jarek for inventing this algorithm. I've also found ryg's rANS implementation and blog posts very useful.

    I plan to iterate on the paper in the coming weeks and months so any constructive feedback is welcome.

  2. Thanks (2):

    Bulat Ziganshin (12th March 2020),Jarek (11th March 2020)

  3. #2
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,972
    Thanks
    296
    Thanked 1,299 Times in 736 Posts
    Why shifts if its in python anyway? Normally its a useful speed optimization, but the model can be much simpler without that.

  4. #3
    Member
    Join Date
    Nov 2018
    Location
    London
    Posts
    2
    Thanks
    0
    Thanked 2 Times in 1 Post
    You mean the bit shifts '<<' and '>>'? How would it be simpler without them?

  5. #4
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,972
    Thanks
    296
    Thanked 1,299 Times in 736 Posts
    Currently you have hardcoded statistics and p_prec, so it works.
    But if you'd try to encode an unknown external file, power-of-2 renormalization would add complexity.
    In particular, implementation of adaptive coding (with stats adjusted to already known data) would
    require either renormalization after each symbol (with corner cases like p_prec<log2(alphabet_size)),
    or binary decomposition and another type of counter.

Similar Threads

  1. Rans tricks
    By Lucas in forum Data Compression
    Replies: 14
    Last Post: 4th November 2019, 17:30
  2. How to build Bonfield's rANS coders on windows
    By Shelwien in forum Data Compression
    Replies: 4
    Last Post: 5th May 2019, 03:14
  3. Published rANS patent by Storeleap
    By Jarek in forum Data Compression
    Replies: 119
    Last Post: 19th February 2019, 11:21
  4. Replies: 45
    Last Post: 25th November 2016, 03:30
  5. AVX-512 and interleaved rANS
    By JamesB in forum Data Compression
    Replies: 41
    Last Post: 6th November 2016, 14:26

Posting Permissions

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