sparse_ngrams/lib.rs
1//! Sparse n-gram extraction from byte slices.
2//!
3//! Sparse grams are a way of selecting variable-length n-grams (longer than 2 bytes) without
4//! extracting all possible n-grams. The algorithm is deterministic: the same extraction logic
5//! works for every substring, so that substring searches are supported.
6//!
7//! # How it works
8//!
9//! Each consecutive byte pair (bigram) is assigned a priority based on how frequently it occurs
10//! in a large code corpus (see [`bigram_priority`]). A monotone deque tracks potential n-gram
11//! boundaries: an n-gram boundary occurs wherever a bigram has lower priority than the bigrams
12//! between it and the previous boundary.
13//!
14//! A substring of length 3..=[`MAX_SPARSE_GRAM_SIZE`] is emitted as a sparse n-gram when both its
15//! left and right boundary bigrams have a priority strictly below every interior bigram. All
16//! bigrams are always emitted.
17//!
18//! For a document of N bytes, this produces at most 3(N-1) n-grams: all bigrams plus algorithmically
19//! selected longer n-grams (up to [`MAX_SPARSE_GRAM_SIZE`] bytes).
20//!
21//! # Normalization
22//!
23//! The bigram priority model only scores ASCII byte pairs; any byte with the high bit set resolves
24//! to priority `0`. Callers building a case-insensitive index should normalize input first (fold
25//! uppercase to lowercase, map multi-byte UTF-8 to high-bit-set bytes) before extraction.
26//!
27//! # Example
28//!
29//! ```
30//! use sparse_ngrams::{NGram, collect_sparse_grams, MAX_SPARSE_GRAM_SIZE};
31//!
32//! let input = b"hello world";
33//! let grams = collect_sparse_grams(input);
34//! assert!(grams.len() > input.len() - 1);
35//! for gram in &grams {
36//! assert!(gram.len() >= 2);
37//! assert!(gram.len() <= MAX_SPARSE_GRAM_SIZE);
38//! }
39//! ```
40
41mod extract;
42mod ngram;
43mod query;
44mod table;
45
46pub use ngram::NGram;
47pub use query::QueryGrams;
48pub use table::bigram_priority;
49
50/// Re-export of the index-folding used internally by [`QueryGrams::append_char`], so callers that
51/// buffer already-folded bytes (and feed them via [`QueryGrams::append_byte`]) fold identically.
52pub use casefold::index_fold_char;
53
54/// Maximum length (in bytes) of a sparse n-gram.
55pub const MAX_SPARSE_GRAM_SIZE: usize = 8;
56
57pub use extract::{
58 collect_sparse_grams, collect_sparse_grams_deque, collect_sparse_grams_scan, max_sparse_grams,
59};