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.

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). 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.

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).