3
$\begingroup$

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?

Improve this question
$\endgroup$
  • $\begingroup$ What research have you done? P.S. I don't think this has anything to do with natural language processing... $\endgroup$ – D.W.♦ Jul 29 '14 at 18:55
  • $\begingroup$ This question is published as an exercise in the Stanford's book «Introduction to Information Retrieval», in chapter #5, «Index Compression». And as I understand, NLP and IR have a common base. Thus, relevant tags — NLP and IR and if NLP-tag is, probably, not so relevant here, but IR-tag is really actual. $\endgroup$ – Mike B. Jul 29 '14 at 19:06
  • $\begingroup$ Regarding to research, I googled for it and what I found is a lot of slides describing what is index compression and giving the same example I can see in the book with encoding/decoding the single number «13», but here I'm asking to decode a binary string with multiple numbers. $\endgroup$ – Mike B. Jul 29 '14 at 19:15
  • $\begingroup$ @Gilles, I'm agree with you, but just here I got the correct and practical answer I expected to receive from the beginning. So, the best solution will be to repost Amit's answer to the opened CS thread and close/delete the question here. $\endgroup$ – Mike B. Jul 30 '14 at 19:25
  • 2
    $\begingroup$ @Mike The answer that solves your concrete problem at hand for you is not always best at helping you understand. $\endgroup$ – Raphael♦ Jul 30 '14 at 20:01
5
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ Amit, thanks a lot for a quick and clear answer! $\endgroup$ – Mike B. Jul 30 '14 at 15:05
2
$\begingroup$

When encoding several numbers in sequence, we simply concatenate the encodings of the individual numbers. The gamma code is an example of a prefix-free code: no codeword is a prefix of another codeword. Due to this property, the encoding of every string has a unique prefix which is a codeword; this prefix encodes the first number. After removing it, you continue to find the second number, and so on, until exhausting the string.

As an example, let's decode 000100000100. The only prefix forming a codeword is 0001000, encoding 8. Removing this, we are left with 00100, which encodes 4. So the complete decoded sequence is 8,4.

As an aside, the gamma code is complete, which means that almost every infinite string (in fact, every infinite string other than $0^\omega$) is the encoding of some infinite sequence of numbers.

Improve this answer
$\endgroup$
  • $\begingroup$ How do you detect a free prefix code (FPC) in any given binary string? How did you decide that for the string «000100000100» FPC will be «0001000» (=8) and not, let say, «00010000»? Suppose, I found a FPC for my string. Now I have to to continue to «concatenate the encodings of the individual numbers», but how do I know where should I split the string on individual numbers? $\endgroup$ – Mike B. Jul 30 '14 at 6:20
  • $\begingroup$ @Mike The whole set of codes, that is the encoding scheme, is prefix-free. It's not a property of a single word, that would not make much sense. $\endgroup$ – Raphael♦ Jul 30 '14 at 6:58
  • $\begingroup$ @Raphael, OK, but stil, how should I detect this prefix-free and how to split the rest of the string on separate digits in order to perform their decoding? $\endgroup$ – Mike B. Jul 30 '14 at 8:01
  • $\begingroup$ @Mike There will be a unique prefix which belongs to the code. In your example, I couldn't have chosen 00010000 since it's not a codeword. You can find it by, for example, trying all prefixes. In the particular case of the $\gamma$ code, I'm sure you can think of something even simpler. $\endgroup$ – Yuval Filmus Jul 30 '14 at 14:31
  • $\begingroup$ Note that this answer uses a different encoding then @amit's answer ( which uses this encoding), the encoding here reverses the ones and zeros. If I use the first encoding to decode this example you would get: 1,1,1,2,1,1,1,2 $\endgroup$ – MikeF Feb 14 '19 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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