Crate sparse_ngrams 

Sparse n-gram extraction from byte slices.

Sparse grams are a way of selecting variable-length n-grams (longer than 2 bytes) without extracting all possible n-grams. The algorithm is deterministic: the same extraction logic works for every substring, so that substring searches are supported.

How it works

Each consecutive byte pair (bigram) is assigned a priority based on how frequently it occurs in a large code corpus (see bigram_priority). A monotone deque tracks potential n-gram boundaries: an n-gram boundary occurs wherever a bigram has lower priority than the bigrams between it and the previous boundary.

A substring of length 3..=MAX_SPARSE_GRAM_SIZE is emitted as a sparse n-gram when both its left and right boundary bigrams have a priority strictly below every interior bigram. All bigrams are always emitted.

For a document of N bytes, this produces at most 3(N-1) n-grams: all bigrams plus algorithmically selected longer n-grams (up to MAX_SPARSE_GRAM_SIZE bytes).

Normalization

The bigram priority model only scores ASCII byte pairs; any byte with the high bit set resolves to priority 0. Callers building a case-insensitive index should normalize input first (fold uppercase to lowercase, map multi-byte UTF-8 to high-bit-set bytes) before extraction.

Example

use sparse_ngrams::{NGram, collect_sparse_grams, MAX_SPARSE_GRAM_SIZE};

let input = b"hello world";
let grams = collect_sparse_grams(input);
assert!(grams.len() > input.len() - 1);
for gram in &grams {
    assert!(gram.len() >= 2);
    assert!(gram.len() <= MAX_SPARSE_GRAM_SIZE);
}

Structs

NGram

A compact n-gram identifier. See the module-level documentation for the bit layout.

QueryGrams

Streaming query n-gram state.

Constants

MAX_SPARSE_GRAM_SIZE

Maximum length (in bytes) of a sparse n-gram.

Functions

bigram_priority

Reconstructs the frequency-ranking priority of the ascii bigram (a, b). Absent or non-ascii bigrams resolve to 0; present bigrams get a strictly positive, unique priority where a higher value means a more frequent bigram. This priority is used to split strings into smaller n-grams.

collect_sparse_grams

Collect all sparse n-grams from the input byte slice into a new Vec.

collect_sparse_grams_deque

Monotone-deque extraction, with the deque held in fixed ring buffers. Calls emit once for every sparse n-gram, in emission order (all bigrams, plus algorithmically selected longer grams), as (gram, idx) where idx is the position of the character just after gram in content. emit decides what to do with each gram — push it into a Vec, write it into a pre-sized slice, feed it straight into an index, etc. — so no output buffer needs to be sized or allocated up front.

collect_sparse_grams_scan

Queue-free scan-based extraction. Calls emit once for every sparse n-gram, in the same order as collect_sparse_grams_deque, as (gram, idx) where idx is the position of the character just after gram in content.

index_fold_char

Re-export of the index-folding used internally by QueryGrams::append_char, so callers that buffer already-folded bytes (and feed them via QueryGrams::append_byte) fold identically. Folds a single char to its one-byte index_fold representation.

max_sparse_grams

Returns the maximum number of sparse n-grams that can be produced from content_len bytes of input. Use this to reserve capacity for the output (e.g. a Vec the emit closure pushes into, or a pre-sized slice it writes).