Results 1 to 8 of 8

Thread: ao0ec: Bytewise adaptive order 0 entropy coder

  1. #1
    Member
    Join Date
    Jan 2014
    Location
    Bothell, Washington, USA
    Posts
    695
    Thanks
    153
    Thanked 183 Times in 108 Posts

    ao0ec: Bytewise adaptive order 0 entropy coder

    I wanted a bytewise adaptive order 0 arithmetic coder that I could use with Tree, but couldn't find what I wanted and didn't understand AC well enough to code it myself. So I saw on Matt's dce page that PPMD has a bytewise entropy encoder. I looked at Dmitry Shkarin's PPMD var J code but still didn't get it. So I stripped all the archive and PPMD stuff out, increased the code bins to 2^12, modified the model, and generally tweaked the code. Now I get it .

    The resulting program is called ao0ac. The format to compress is "ao0ac c <fname>". The format to decompress is "ao0ac d <fname.ao0>". The program is experimental and decompression adds ".rest" to the file name rather than providing a filename option or risking overwriting the original file. The program is license free.

    Compression and decompression use 300 KB of memory on my i7-4790K 4.00 GHz overclocked at 4.36 GHz (Task Manager).

    Results on enwik9:
    Compress: 1,000,000,000 -> 624,660,493 in 25.7 seconds
    Decompress: 32.0 seconds, file verifies

    Results on enwik8:
    Compress: 100,000,000 -> 61,608,976 in 2.6 seconds
    Decompress: 3.2 seconds, file verifies

    A .zip file of the source code is 3,081 bytes.
    Attached Files Attached Files
    Last edited by Kennon Conrad; 18th March 2015 at 10:53. Reason: Fixed uncompressed enwik8 size, fixed program name

  2. Thanks (3):

    Gonzalo (16th March 2015),Paul W. (15th March 2015),surfersat (16th March 2015)

  3. #2
    Member
    Join Date
    May 2012
    Location
    United States
    Posts
    343
    Thanks
    200
    Thanked 58 Times in 42 Posts
    Post #1
    Code:
    Today, 00:00


    Will play around with it.
    Thanks.

  4. #3
    Member
    Join Date
    Aug 2014
    Location
    Argentina
    Posts
    542
    Thanks
    239
    Thanked 92 Times in 72 Posts
    “ao0ec”... Damn ugly acronyms
    I mean... Thank you!

    BTW: The binary says "ao0ac" Is it a typo? That's also the name of the .zip...
    Last edited by Gonzalo; 17th March 2015 at 04:03.

  5. #4
    Member
    Join Date
    Jan 2014
    Location
    Bothell, Washington, USA
    Posts
    695
    Thanks
    153
    Thanked 183 Times in 108 Posts
    Quote Originally Posted by Gonzalo View Post
    “ao0ec”... Damn ugly acronyms
    I mean... Thank you!

    BTW: The binary says "ao0ac" Is it a typo? That's also the name of the .zip...
    Yes, it was a typo. The a is for arithmetic, but I started substituting entropy when I wrote the post.

    The name isn't so good, but since it is license free you can change it to whatever you like.

  6. #5
    Member
    Join Date
    Dec 2011
    Location
    Cambridge, UK
    Posts
    506
    Thanks
    187
    Thanked 177 Times in 120 Posts
    There's some similar code in fqzcomp at https://sourceforge.net/p/fqzcomp/co...simple_model.h
    It has a similar ancestry, from Eugene Shelwein but also with ideas from PPMD code.

    I've no idea how it compares speed wise, but it looks pretty similar - update the model and use a simple bubble sort step to maintain symbol sorted by frequency, although I do that step less often. I also added a sentinel to the symbol array to avoid having to check loop termination; by ensuring the sentinel marker has maximum frequency we naturally terminate during the sort step.

  7. Thanks (2):

    Kennon Conrad (18th March 2015),Paul W. (18th March 2015)

  8. #6
    Member
    Join Date
    Jan 2014
    Location
    Bothell, Washington, USA
    Posts
    695
    Thanks
    153
    Thanked 183 Times in 108 Posts
    Quote Originally Posted by JamesB View Post
    There's some similar code in fqzcomp at https://sourceforge.net/p/fqzcomp/co...simple_model.h
    It has a similar ancestry, from Eugene Shelwein but also with ideas from PPMD code.

    I've no idea how it compares speed wise, but it looks pretty similar - update the model and use a simple bubble sort step to maintain symbol sorted by frequency, although I do that step less often. I also added a sentinel to the symbol array to avoid having to check loop termination; by ensuring the sentinel marker has maximum frequency we naturally terminate during the sort step.
    I wish I had seen that earlier - it would have been easier to start there. Yes, it does look very similar. Some of the changes from PPMD look similar, such as the addition of a total frequency variable and renormalization being based on the total frequency rather than the frequency value for the most common symbol. I think a speed comparison would depend a lot on the file type since we went opposite directions with the bubble sort. PPMD does one bubble sort step per symbol, this code does one bubble sort step per 16 symbols, and my code does a full bubble sort per symbol (but mine isn't exactly bubble sort since it won't do 6 swaps to move a symbol up 6 steps - it moves 6 symbols down by one location and the current symbol up 6 locations).

    The sentinel is interesting. I didn't realize it would be guaranteed to be at an address right before the F array. It makes the code cleaner. I'm not so sure about the speed impact. On the decoding side there are some math optimizations available when the symbol is in the first array element, but it does make for cleaner code.

  9. #7
    Member
    Join Date
    Dec 2011
    Location
    Cambridge, UK
    Posts
    506
    Thanks
    187
    Thanked 177 Times in 120 Posts

    Re: ao0ec: Bytewise adaptive order 0 entropy coder

    I hacked up a quick demo using the code out of fqzcomp.

    The input/output is a bit different, so it's not so obvious how to compare speed. This is more similar to the arith_static and rans_static4 implementations I experimented with for I/O, but obviously they were using stationary probabilities instead of adaptive (and so were MUCH faster).

    I wonder if you'd do better using a simple order-1 stationary probability coder than an adaptive order-0 coder. The rANS-o1 coder is still much faster than an adpative order-0 artihmetic coder.

    jkb@seq3a[compress.../f_o0] g++ -O3 f_o0.c
    jkb@seq3a[compress.../f_o0] time ./a.out < /tmp/_jkb/enwik8 > /tmp/_jkb/enwik8.o0
    real 0m2.767s
    user 0m2.620s
    sys 0m0.140s
    jkb@seq3a[compress.../f_o0] ls -l /tmp/_jkb/enwik8.o0
    -rw-r--r-- 1 jkb team117 61632538 Mar 19 14:53 /tmp/_jkb/enwik8.o0
    jkb@seq3a[compress.../f_o0] time ./a.out -d < /tmp/_jkb/enwik8.o0 > /tmp/_jkb/enwik8.o0.txt
    real 0m3.603s
    user 0m3.540s
    sys 0m0.060s
    jkb@seq3a[compress.../f_o0] cmp /tmp/_jkb/enwik8.o0.txt /tmp/_jkb/enwik8

    jkb@seq3a[compress.../f_o0] time ../rANS_static4 -o0 < /tmp/_jkb/enwik8 > /tmp/_; ls -l /tmp/_
    Took 572383 microseconds, 174.7 MB/s
    real 0m0.606s
    user 0m0.500s
    sys 0m0.110s
    -rw-r--r-- 1 jkb team117 63639478 Mar 19 14:58 /tmp/_
    jkb@seq3a[compress.../f_o0] time ../rANS_static4 -d < /tmp/_ > /dev/null Took 452902 microseconds, 220.8 MB/s
    real 0m0.454s
    user 0m0.430s
    sys 0m0.030s

    jkb@seq3a[compress.../f_o0] time ../rANS_static4 -o1 < /tmp/_jkb/enwik8 > /tmp/_; ls -l /tmp/_
    Took 924360 microseconds, 108.2 MB/s
    real 0m0.958s
    user 0m0.880s
    sys 0m0.080s
    -rw-r--r-- 1 jkb team117 49122467 Mar 19 14:59 /tmp/_
    jkb@seq3a[compress.../f_o0] time ../rANS_static4 -d < /tmp/_ > /dev/null Took 727188 microseconds, 137.5 MB/s
    real 0m0.729s
    user 0m0.720s
    sys 0m0.010s

    I don't trust the timings on such a small file as likely it hasn't ramped up the clock speed yet on that CPU. However they're comparable to each other.

    For completeness (with caveat about differing I/O mechanisms):

    jkb@seq3a[tmp/_jkb] time ./ao0ac c enwik8
    Adaptive order 0 arithmetic compressor ao0ac
    enwik8:100000000 >61608976, 4.93 bpb

    real 0m3.955s
    user 0m3.880s
    sys 0m0.070s

    jkb@seq3a[tmp/_jkb] time ./ao0ac d enwik8.ao0
    Adaptive order 0 arithmetic compressor ao0ac
    enwik8.ao0.rest:61608976 >100000000, 4.93 bpb

    real 0m4.528s
    user 0m4.420s
    sys 0m0.100s
    Attached Files Attached Files

  10. Thanks:

    Kennon Conrad (19th March 2015)

  11. #8
    Member
    Join Date
    Jan 2014
    Location
    Bothell, Washington, USA
    Posts
    695
    Thanks
    153
    Thanked 183 Times in 108 Posts
    It looks like the majority of the timing difference between the order 0 arithmetic coders is in the sorting. Times are pretty similar if I only sort once per 16 symbols.

    I do plan to use some order 1 models but had to start with order 0 to see how it works. I may use some static models but I know at least some of them should be adaptive because some of the statistics for my compressor change significantly as the file is processed. For instance, the probability of a new symbol in Tree when compressing enwik9 goes from 100% at the start of the file to about 2% near the end of the file.

Similar Threads

  1. Simple bytewise context mixing demo
    By Shelwien in forum Data Compression
    Replies: 13
    Last Post: 3rd April 2020, 16:04
  2. nARANS (Nania Adaptive Range Variant of ANS)
    By Nania Francesco in forum Data Compression
    Replies: 9
    Last Post: 16th November 2014, 15:33
  3. Adaptive adaptation rate :)
    By Piotr Tarsa in forum Data Compression
    Replies: 29
    Last Post: 6th January 2012, 15:44
  4. flzp_ac2 (flzp + an order-2 arithmetic coder)
    By inikep in forum Data Compression
    Replies: 4
    Last Post: 25th June 2008, 21:37
  5. Bytewise vs Binary
    By Shelwien in forum Forum Archive
    Replies: 9
    Last Post: 30th March 2008, 16:51

Posting Permissions

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