2
$\begingroup$

I'm trying to work out how to find the gamma $\gamma -code$ that encodes the postings list (12, 18, 21, 22).

Is the postings list encoded just by a list of the individual $\gamma$-codes for each integer? E.g. for 12 the gamma code is: 0001100, and so the first entry in the $\gamma$-code for the pointing list is just 0001100. Or is there another representation - am I thinking along the right lines?

Thanks in advance for any help!

$\endgroup$
2
$\begingroup$

I'm assuming that you're referring to the Elias gamma code. This code is a prefix code, also known as a self-terminating code. This means that you can encode a sequence of numbers by simply concatenating the encodings of the individual numbers. Since the code is self-terminating, the concatenated encoding can be decoded into the encodings of the individual numbers.

A prefix code is a code in which no codeword is a prefix of another codeword. This allows you to decode the list as follows. Read bits until you reach a prefix of the encoding which constitutes a codeword. This encodes the first number. Remove and repeat.

Finally, let me stress that the Elias gamma code is a way of encoding numbers using a string of bits. When you write 0001100, you should think of it as a string of 7 bits. Eventually these bits will be decomposed into 8-bit chunks (knows as bytes) and stored or communicated in this way – as a string of bytes.

$\endgroup$
  • $\begingroup$ Awesome, thanks for the help! Yes I am referring to the Elias gamma code. So the encoding of the positings list is not (0001100, 000010010, 000010101, 000010110) but it is : 0001100000010010000010101000010110. What do you mean by self-terminating? It's unclear to me how one could get back from the concatenation to the positings list from this now.. $\endgroup$ – T132 Feb 18 '18 at 11:04
  • $\begingroup$ Wikipedia has an article on prefix codes. Note that the encoding cannot really be "0001100, 000010010" and so on, since you are encoding the data as bits, and there are only two possible bits: 0 and 1. Comma and space are not bits. $\endgroup$ – Yuval Filmus Feb 18 '18 at 11:42

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.