# 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. ```rust fn new>(queries: &[Q], window_widths: &[usize], candidates_budget: usize, stream: &Stream) -> Result; fn scores<'scope>(&'scope mut self, scope: &'scope Scope<'scope, '_>, candidates: StringsView<'scope>, radius: Option, 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. ```rust 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]); ``` `use stringzilla::OverlapEngine;` ## OverlapEngine A forest of prepared query trees, probed by as many batches of candidates as a caller has. ```rust 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`](#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`](#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` ## new Sorts `queries` into one forest with the capabilities of `stream`, like [`Capabilities::cpu_enabled`](https://www.unum.cloud/docs/stringzilla/rust/runtime-dispatch.md#cpu_enabled) or a GPU's [`Capabilities::cuda_enabled`](https://www.unum.cloud/docs/stringzilla/rust/runtime-dispatch.md#cuda_enabled), fixing the capability once, on the device `stream` names, which it may join. ```rust pub fn new( queries: &[Query], window_widths: &[usize], candidates_budget: usize, stream: &Stream, ) -> Result 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_count Queries the forest holds, which is the first axis of every output. ```rust pub fn queries_count(&self) -> usize ``` ## widths_count Window widths the batch scores at, which is the last axis of every output. ```rust pub fn widths_count(&self) -> usize ``` ## scores Queues on the stream of [`scope`](https://www.unum.cloud/docs/stringzilla/rust/runtime-dispatch.md#scope) the window overlap of every prepared query with every candidate, at every width of the batch. ```rust pub fn scores<'scope>( &'scope mut self, scope: &'scope Scope<'scope, '_>, candidates: StringsView<'scope>, radius: Option, scores: &'scope mut [f32], scores_query_stride: usize, scores_candidate_stride: usize, ) -> Result<(), Status> ``` [`scores`](#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`](#scores) in memory its device reaches, such as a [`Strings`](https://www.unum.cloud/docs/stringzilla/rust/types.md#Strings) and a `Vec` in a [`UnifiedAllocator`](https://www.unum.cloud/docs/stringzilla/rust/memory-operations.md#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`](https://www.unum.cloud/docs/stringzilla/rust/types.md#DeviceMemoryMismatch).