Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm reading the tutorial of Information Gain, and I see the following page: enter image description here

I know in the example above, I can encode this way:

A 0
B 10
C 11

and then this will need $1/3*1+1/3*2+1/3*2=1.6667$ bits per symbol. But how can I code to achieve the 1.58 goal in theory? Is that possible in practice?

share|improve this question
2  
Arithmetic coding can achieve this order of compression efficiency. –  achille hui Mar 28 at 13:13

2 Answers 2

up vote 14 down vote accepted

You can't do that by using binary codewords for single symbols A, B and C.

As mentioned in the comments, for example, arithmetic coding can be used to get near the limit when the input sequence is long.

Another simple example: You can consider "super-symbols" that consist of 100 As, Bs and Cs and encode one super-symbol at a time, so that each of the $3^{100}$ possible super-symbols corresponds to a $159$-bit binary codeword ($3^{100}\leq 2^{159}$), giving you effectively $1.59$ bits per original symbol. Or sequences of $10000$ symbols, so that each sequence corresponds to a $15850$ bit codeword ($3^{10000}\leq 2^{15850}$), giving effectively $1.585$ bits per symbol.

share|improve this answer
    
wow! love you ;) –  zhangxaochen Mar 28 at 13:28
6  
Or more simply: put $A=0,B=1,C=2$ and store it in ternary, and that will have $log_2(3)\approx1.5849625...$ bits per symbol in the long run. –  chubakueno Mar 28 at 16:57
1  
What do you mean by "storing it in ternary" when the question was how to encode ternary symbols in binary? –  JiK Mar 28 at 18:56
1  
You can pretend you just see a ternary number written as a string, and convert it to binary. –  chubakueno Mar 28 at 19:09
    
Oh, now I see. That seems to be the first example in the Wikipedia article on arithmetic coding. –  JiK Mar 28 at 19:15

The optimal length is given by the Huffman code. In this case, that corresponds to your proposed coding, with average code length 1.6667. So, this is optimal... if you restrict to a single symbol=>single codeword coding. But you can do better if, instead of coding each symbol alone, you code the pairs, or triplets, or... That is, if you encode the "extended source".

For example, taking the extension of order $2$, you'd have $3\times 3=9$ symbols, each with probability $1/9$, and you could code them thus:

 AA 000
 AB 001
 AC 010
 BA 011
 BB 100 
 BC 101
 CA 110
 CB 1110
 CC 1111

This gives an average length of $(3 \times 7/9 + 4 \times 2/9)/2=1.6111\cdots$. This is better, but still does not reach the Shannon limit.

For extension three, we'd have 27 symbols and the Huffman code would be

         n   L 
00**    (4)  4
0100    (1)  4
0101*   (2)  5 
011**   (4)  5
1****  (16)  5

with average length $[ 4 \times (4+1)/27 + 5 \times (2+4+16)/27]/3=1.605...$

You can do still better -and approximate asymptotically the theoretical value- by taking higher and higher order extensions. Or you can use arithmetic coding, which, essentially, does precisely that.

A simple coding -suboptimal but simple, and that achieves the goal in the original exercise - would be the extension of order 5, which gives $3^5=243$ symbols. This can be trivially coded by 8 bits each ($2^8=256 < 243$), what gives $8$ bits/$5$ symbols = 1.6 bits per symbol.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.