[Solved]: How to decode multiple-digit gamma codes and get the gap sequence?

Problem Detail: 

How to decode gamma code ($\gamma$ code):

1110001110101011111101101111011 

and get the gap sequence?

Detailed information about Gamma codes ($\gamma$ codes) with a brief example of decoding can be found here.

But in their example there is only one case when gamma code ($\gamma$ code) consists of one digit only, how to deal with multiple digits binary string?

Asked By : Mike B.

Answered By : amit

The above sequence it read as a concatination of 5 numbers:

You start from the left side, read the first unary code. It let's you know what is the length of the first number. The 2nd number starts right after the 1st, and you interpet it the same way.

1. First, read the first unary code, it is 1110 - so the first number is "1110:001", which is 9
2. The next unary code is right after this, and is: "110" - so the 2nd number is "110:10" which is 6
3. The next unary code is "10", and the 3rd number is "10:1", which is 3
4. The next unary code is "111110", and the 4th number is "111110:11011", which is 32+16+8+2+1=59
5. Next unary number is "110", which gives you the 5th and last number, which is "110:11", which is 7.

So, the decoding of the given gamma code is actually 9,6,3,59,7

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28783