If we are given a binary file of length n, where each bit independently is one with probability 1/3 and zero else. We want to construct a method that the expected length of the compressed sequence is less than 10 percent more than Shannon's lower bound (for all n large enough). I've got the lower bound is 0.918. I tried to use tuples of size 2, but it gives me an expected length of 1.88 by Huffman coding. Am I going in the right direction?
The Shannon entropy bound is 0.918 output bits per input bit.
If you just write the bits you're given, you'll spend 1 output bit per input bit.
This is already less than 10% more than the bound, so no compression is required.
You can use Arithmetic compressor or Rangecoder.
There is explanation with code for Arithmetic compressor and open-source implementation of Rangecoder.
I personally recommend to use Rangecoder, because of it works fastest, and has never been patented (patent for arithmetic compressor already expired).
