HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to decode multiple-digit gamma codes and get the gap sequence?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
theandgapsequencegetgammacodesmultiplehowdecode

Problem

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?

Solution

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.

  • First, read the first unary code, it is 1110 - so the first number


is "1110:001", which is 9

  • The next unary code is right after this, and is: "110" - so the 2nd number is "110:10" which is 6



  • The next unary code is "10", and the 3rd number is "10:1", which is 3



  • The next unary code is "111110", and the 4th number is "111110:11011", which is 32+16+8+2+1=59



  • 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

Context

StackExchange Computer Science Q#28783, answer score: 5

Revisions (0)

No revisions yet.