There’s a similar algorithm for indexing words in text collections (I know it from the ‘Managing Gigabytes’ book). Say you want to store the information that t

There’s a similar algorithm for indexing words in text collections (I know it from the ‘Managing Gigabytes’ book). Say you want to store the information that the word ‘algorithm’ occurs in documents 42, 2718 and 3141. That’s a sorted list, so as the author notes, you can just store the differences (42, 2676, 423). Those differences can still be arbitrarily large, but if there are many documents, you can expect most differences to be small. The trick is to store the numbers not as fixed-bit-size integers, but using a variable-length encoding. The algorithm stipulates using a Golomb code with the parameter b = ceil(N / n * ln(2)), where N is the number of documents in total, n is the number of documents containing our word, and ln is the natural logarithm. For our example, assuming 5000 documents in total, this gives N = 5000, n = 3, b = 1156, and our index entry is 10000101010001010110110010110100111, for a total of 35 bits.