Go to Homepage     Learn about Front Coding

Variable Byte Encoding: Compressing Posting Lists

Your entered:
Posting list after step 1(Sorting):
Posting list after step 2(Gap Encoding):
Posting list after step 3(VB Encoding):
Posting list after step 4(VB Encoded Bytestream):

Reverse VB Encoding
                    




Step 1: Posting list is sorted




Step 2: Posting list is updated by Gaps between the enteries of posting




Step 3: Each entry in the posting list is encoded to 128-encoded number sequence




Step 4: Each entry sequence is converted to a Bytestream using the following method. The last 7 bits of a byte are “payload” and encode part of the gap. The first bit of the byte is a Continuation Bit. It is set to 1 for the last byte of the encoded gap and to 0 otherwise.


Let's do one exercise!
Let the posting list is: 56->2->190
Compute VB Encoding Bytestream corresponding to it