Fingerprints | StringZilla for Rust

§ Window Overlap

OverlapEngine hashes and sorts a batch of queries into one B-tree forest over every window width, then streams candidates through it. A window is a fixed-width byte n-gram, and the overlap of two texts at that width is the count of one’s windows that occur in the other, over whichever of the two holds more. Nothing is stored per candidate, so the candidates may change round to round while the queries and the widths stay.

fn new<Q: AsRef<[u8]>>(queries: &[Q], window_widths: &[usize], candidates_budget: usize,
    stream: &Stream) -> Result<OverlapEngine, Status>;

fn scores<'scope>(&'scope mut self, scope: &'scope Scope<'scope, '_>,
    candidates: StringsView<'scope>, radius: Option<f32>, scores: &'scope mut [f32],
    scores_query_stride: usize, scores_candidate_stride: usize) -> Result<(), Status>;

Widths are in bytes and need not form a doubling chain, since a window hash comes from a prefix difference that costs one modular multiply-add at any width; a width past a text scores zero for every pair it spans. The output is a [queries, candidates, widths] block with the width axis unit-strided: share [q, c, w] lands at scores[q * query_stride + c * candidate_stride + w], each in [0, 1]. The score is asymmetric — a candidate’s window occurrences count against a query’s distinct windows — so swapping the two sides changes the answer whenever either repeats a window. A radius of Some(share) is the share of the longer side’s windows, summed over every width, a pair may miss and still score exactly; a pair past it scores 0.0 at every width, on every backend, and None keeps every score exact.

use stringzilla::{Capabilities, OverlapEngine, Stream, StringsView};

let cpu = Stream::default(Capabilities::cpu_enabled());
let mut engine = OverlapEngine::new(&["the quick brown fox"], &[4, 8], 0, &cpu).unwrap();

let mut scores = [0.0f32; 2];
let candidates = StringsView::from_slices(&["the quick brown cat"]);
cpu.scope(|scope| engine.scores(scope, candidates, None, &mut scores, 2, 2)).unwrap();
assert!(scores.iter().all(|share| (0.0..=1.0).contains(share)));

// A pair missing more than a tenth of its windows scores zero at every width.
cpu.scope(|scope| engine.scores(scope, candidates, Some(0.1), &mut scores, 2, 2)).unwrap();
assert_eq!(scores, [0.0, 0.0]);

API

StructOverlapEngineA forest of prepared query trees, probed by as many batches of candidates as a caller has.4

overlap.rs:45 ↗

pub struct OverlapEngine

A window is a fixed-width byte n-gram, and the overlap of two texts at that width is the count of one's windows that occur in the other, over whichever of the two holds more. Every query is hashed and sorted into one B-tree over every width at construction, so the sort is paid once per batch rather than once per round, and nothing is stored per candidate.

The score is asymmetric: a candidate's window occurrences count against a query's distinct windows, so swapping the two sides changes the answer whenever either repeats a window.

The fields mirror sz_overlap_engine_t one for one and only count and widths_count are read from Rust, so the layout is load-bearing and the engine travels to C by pointer. Owning raw pointers makes it neither Send nor Sync, which is what the C contract wants: a compute verb grows the engine's round scratch, so it mutates, and OverlapEngine::scores takes &mut self for that reason.

Examples

use stringzilla::{Capabilities, OverlapEngine, Stream, StringsView};

let cpu = Stream::default(Capabilities::cpu_enabled());
let mut engine = OverlapEngine::new(&["the quick brown fox"], &[4, 8], 0, &cpu).unwrap();

// A `[queries, candidates, widths]` block with the width axis unit-strided.
let mut scores = [0.0f32; 2];
let candidates = StringsView::from_slices(&["the quick brown cat"]);
cpu.scope(|scope| engine.scores(scope, candidates, None, &mut scores, 2, 2))
    .unwrap();
assert!(scores.iter().all(|share| (0.0..=1.0).contains(share)));

Implements

Drop

newSorts queries into one forest with the capabilities of stream, like Capabilities::cpu_enabled or a GPU's Capabilities::cuda_enabled, fixing the capability once, on the device stream names, which it may join.

overlap.rs:72 ↗

pub fn new<Query>(
    queries: &[Query],
    window_widths: &[usize],
    candidates_budget: usize,
    stream: &Stream,
) -> Result<Self, Status>
where
    Query: AsRef<[u8]>,

window_widths are n-gram widths in bytes and need not form a doubling chain; a width past a text scores zero for every pair it spans. An empty list of widths is refused here rather than at the first round. candidates_budget bounds one round for a backend that keeps state per candidate, zero asking for its default, and is ignored by one that keeps none.

queries_countQueries the forest holds, which is the first axis of every output.

overlap.rs:99 ↗

pub fn queries_count(&self) -> usize

widths_countWindow widths the batch scores at, which is the last axis of every output.

overlap.rs:104 ↗

pub fn widths_count(&self) -> usize

scoresQueues on the stream of scope the window overlap of every prepared query with every candidate, at every width of the batch.

overlap.rs:126 ↗

pub fn scores<'scope>(
    &'scope mut self,
    scope: &'scope Scope<'scope, '_>,
    candidates: StringsView<'scope>,
    radius: Option<f32>,
    scores: &'scope mut [f32],
    scores_query_stride: usize,
    scores_candidate_stride: usize,
) -> Result<(), Status>

scores receives a [queries, candidates, widths] block: share [q, c, w] lands at scores[q * scores_query_stride + c * scores_candidate_stride + w], each in [0, 1], with the width axis unit-strided. Both strides count entries rather than bytes, the candidate stride being at least the width count and the query stride at least the candidates times that.

A pair's distance is the windows it misses over its longer side's, summed over every width. A radius of Some(share) keeps every pair within that distance exact: a pair past it scores 0.0 at every width, which lets a round skip it. None, or a share of 1.0 or more, keeps every score exact.

A GPU engine takes candidates and scores in memory its device reaches, such as a Strings and a Vec in a UnifiedAllocator, and joins the stream before turning its counts into shares. A stream of another group than the engine's is refused with Status::DeviceMemoryMismatch.