barrel_ngram_postings (barrel_ngram v0.7.1)
View SourcePosting-list codec and intersection.
A posting list is the set of local document ordinals that contain a given gram, stored ascending. On disk it is [Count][Delta]... where each value is a LEB128 varint and ordinals are delta-encoded against their predecessor (ordinals are strictly ascending, so deltas are non-negative and no zigzag is needed). This is the integer-ordinal form of the block codec used by the BM25 disk index.
intersect_all/1 ANDs several posting lists. It starts from the shortest list and galloping-searches each remaining list, so a rare gram bounds the work rather than the largest list.
Summary
Functions
Decode a delta+varint block back to ascending ordinals.
Encode a set of ordinals as a delta+varint block. The input is sorted and de-duplicated first, so callers need not pre-sort.
Intersect several ascending posting lists. Any empty input makes the whole intersection empty. The result is ascending.
Union several ascending posting lists into one ascending, unique list (k-way merge with dedup).
Types
-type ordinal() :: non_neg_integer().
Functions
Decode a delta+varint block back to ascending ordinals.
Encode a set of ordinals as a delta+varint block. The input is sorted and de-duplicated first, so callers need not pre-sort.
Intersect several ascending posting lists. Any empty input makes the whole intersection empty. The result is ascending.
Union several ascending posting lists into one ascending, unique list (k-way merge with dedup).