6

I am trying to encode signed values ranging from -256 <-> 255 (i.e. 9 bit data represented by short) with arithmetic encoder, however I have discovered that existing implementations of Arithmetic coding (such as dlib, rANS) usually reads the file in the form of a string and treat the data as 8-bit.

The problem with this technique is that this splitting of signed data (shown in 3) in the form of string destroys the underlying histogram (shown in 4). I believe that such splitting may also be degrading the compression ratios (but I may be wrong).

I tested my hypothesis by implementing a Huffman encoding with 8-bit and 16-bit data and found that I was right, this maybe due to Huffman's dependence on making the tree by using probabilities.

(EDITED)My question is: How to encode/model symbols (which cannot be contained in a conventional 8-bit container) so that resulting symbols can be easily compressed with traditional arithmetic compressor implementations without affecting compression ratios.

Signed histogram:

Signed histogram

Splitted histogram:

Splitted histogram

16
  • 1
    Hi Asif, are you asking for someone to give you an algorithm here? Or something else? It's a little unclear.
    – TylerH
    Feb 14, 2018 at 14:49
  • 1
    Are you asking for code, do you want an algorithm, or are you asking for a library? Feb 14, 2018 at 14:49
  • 1
    Why not expand your 9-bit data to 16-bit? you'll get a lot of 0x00 and 0x01 's which wouldn't impact the compression (very much.... i think... maybe).... please tell if this makes no sense XD
    – Stefan
    Feb 14, 2018 at 14:52
  • 1
    @AsifAli A quick draft of using FastAC either directly coding zig-zag mapped 9-bit values or a split approach mentioned above. Both approaches seem to result in similar compression ratio. Given that, it seems you can do well enough with just a <= 256 symbol alphabets. Maybe rephrase the question so it's not asking for a library and I can write up an answer.
    – Dan Mašek
    Feb 14, 2018 at 22:35
  • 2
    It's not untested and unimplemented. Even that file you linked to uses multiple alphabet sizes, including 513, 65534, and 65537. All these modes are regularly unit tested. Read the documentation.
    – Davis King
    Feb 15, 2018 at 11:40

0