barrel_ngram_selector_sparse (barrel_ngram v0.9.0)
View SourceSparse (content-defined) gram selector.
Selects only a content-determined subset of trigrams, shrinking the index and the candidate sets. A gram at byte position i (the trigram over Bytes[i..i+2]) is kept iff a hash of its local window passes a sampling test: phash2(Window, SampleRate) =:= 0. The window has radius r, spanning Bytes[i-r .. i+2+r] (width 3 + 2r), so the choice depends only on local bytes and identical substrings select identical grams.
The boundary rule
When a literal L occurs in a document D at position p, a gram at literal-position i whose window lies entirely inside L (i >= r and i+2+r =< len(L)-1) has, in D, the identical window (that range sits inside the matched region), so it is selected in D iff selected in L. Grams whose window spills past L's edge see different bytes in D and are NOT reliable.
So select_grams_positional/2 (index side) selects over every position, padding document-edge windows with a sentinel, while reliable_grams_positional/2 (query side) selects only over INTERIOR positions whose window is fully inside the literal, and falls back to brute_force when there is no such gram. Relying on a boundary gram would be a silent false negative, so the query never does. select_grams/2 and reliable_grams/2 (the plain, non-positional behaviour callbacks) are exactly the gram sets of these with the offsets dropped -- implemented as a thin wrapper, not a separate computation, so the two can never drift apart.
Summary
Functions
Sparse samples grams, so an arbitrary trigram may be absent; the regex planner must not rely on the index being complete.
Opts with every tunable filled in, so two maps meaning the same thing compare equal regardless of which keys were given.
The deduplicated gram set of reliable_grams_positional/2.
The literal's grams the planner may intersect over, each with its offset within the literal (for the distance-check math): only interior positions whose window is fully inside the literal. brute_force when there is no such sampled gram.
The deduplicated gram set of select_grams_positional/2. Used by the phase-1-style (non-positional) EUnit invariant checks; the actual indexer calls the positional form directly.
Grams selected over the full byte string, each with the byte offset it occurs at (sentinel-padded windows at the edges). Used by the indexer to build the phase-2 positional postings.
Functions
Sparse samples grams, so an arbitrary trigram may be absent; the regex planner must not rely on the index being complete.
Opts with every tunable filled in, so two maps meaning the same thing compare equal regardless of which keys were given.
-spec reliable_grams(binary(), map()) -> barrel_ngram_selector:reliable().
The deduplicated gram set of reliable_grams_positional/2.
-spec reliable_grams_positional(binary(), map()) -> barrel_ngram_selector:reliable_positional().
The literal's grams the planner may intersect over, each with its offset within the literal (for the distance-check math): only interior positions whose window is fully inside the literal. brute_force when there is no such sampled gram.
-spec select_grams(binary(), map()) -> [barrel_ngram_selector:gram()].
The deduplicated gram set of select_grams_positional/2. Used by the phase-1-style (non-positional) EUnit invariant checks; the actual indexer calls the positional form directly.
-spec select_grams_positional(binary(), map()) -> [{barrel_ngram_selector:gram(), non_neg_integer()}].
Grams selected over the full byte string, each with the byte offset it occurs at (sentinel-padded windows at the edges). Used by the indexer to build the phase-2 positional postings.