LevenshteinEngine prepares a batch of queries once — Myers’ bit-parallel masks, the capability, and on a device the launch geometry — then scores as many batches of candidates against it as a caller has.
Preparation is the expensive half, so a long-lived engine amortizes it across every later round, and the round’s scratch grows to fit the widest batch it has seen and is never shrunk.
fn new<Q: AsRef<[u8]>>(queries: &[Q], symbol: LevenshteinSymbol,
stream: &Stream) -> Result<LevenshteinEngine, Status>;
fn distances<'scope>(&'scope mut self, scope: &'scope Scope<'scope, '_>,
candidates: StringsView<'scope>, bound: Option<usize>, distances: &'scope mut [usize],
distances_stride: usize) -> Result<(), Status>;LevenshteinSymbol::Bytes counts bytes and LevenshteinSymbol::Runes counts UTF-8 runes, each maximal ill-formed subpart decoding to one U+FFFD; the two alphabets are one engine and one verb rather than two spellings.
Costs are unit — one per substitution, insertion and deletion — and there are no gap costs and no substitution matrix.
The output is a [queries, candidates] block the caller owns: query q against candidate c lands at distances[q * distances_stride + c], the stride counting entries rather than bytes and being at least the candidate count.
A stride wider than the candidate count is what lets one round fill a sub-block of a larger matrix.
A bound of Some(limit) keeps a distance exact up to limit and reports limit + 1 for every candidate past it, on every backend, so a round can stop early; None keeps every distance exact.
use stringzilla::{Capabilities, LevenshteinEngine, LevenshteinSymbol, Stream, StringsView};
let cpu = Stream::default(Capabilities::cpu_enabled());
let mut engine = LevenshteinEngine::new(&["kitten", "saturday"], LevenshteinSymbol::Bytes, &cpu).unwrap();
let mut distances = [0usize; 4];
let candidates = StringsView::from_slices(&["sitting", "sunday"]);
cpu.scope(|scope| engine.distances(scope, candidates, None, &mut distances, 2)).unwrap();
assert_eq!(distances[0], 3); // kitten vs sitting
assert_eq!(distances[3], 3); // saturday vs sunday
// The same engine, a second round over an Arrow tape, no preparation repeated.
let mut again = [0usize; 4];
let arrow = StringsView::from_u32_tape(b"mittenkitten", &[0, 6, 12]).unwrap();
cpu.scope(|scope| engine.distances(scope, arrow, None, &mut again, 2)).unwrap();
assert_eq!(again[..2], [1, 0]); // kitten vs mitten and kitten
// Bounded at 1, a candidate two edits away reports exactly 2.
cpu.scope(|scope| engine.distances(scope, candidates, Some(1), &mut distances, 2)).unwrap();
assert_eq!(distances[0], 2); // kitten vs sitting is 3, past the bound
// Runes rather than bytes, for text where a codepoint is the unit.
let mut unicode = LevenshteinEngine::new(&["café"], LevenshteinSymbol::Runes, &cpu).unwrap();
let mut one = [0usize; 1];
cpu.scope(|scope| unicode.distances(scope, StringsView::from_slices(&["cafe"]), None, &mut one, 1)).unwrap();
assert_eq!(one[0], 1);LevenshteinSymbolWhich symbols a batch counts, since the alphabet picks the transpose and the mask layout alike.pub enum LevenshteinSymbolCorresponds to sz_levenshtein_symbol_t in the C API.
Bytes | 0 | Every byte is its own symbol, and a distance counts bytes. |
|---|---|---|
Runes | 1 | Every UTF-8 rune is one symbol, each maximal ill-formed subpart decoding to one U+FFFD. |
Debug, Clone, Copy, StructuralPartialEq, PartialEq, EqLevenshteinEngineA batch of prepared queries, scored against as many batches of candidates as a caller has.4pub struct LevenshteinEngineMyers' bit-parallel masks are built once per batch and reused by every round, so the preparation a one-shot distance repeats per pair is paid here exactly once. Construction also fixes the capability and, on a GPU, the launch geometry.
The fields mirror sz_levenshtein_engine_t one for one and only count, symbol and
capability 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 every verb below
takes &mut self for that reason.
use stringzilla::{Capabilities, LevenshteinEngine, LevenshteinSymbol, Stream, StringsView};
let cpu = Stream::default(Capabilities::cpu_enabled());
let mut engine = LevenshteinEngine::new(&["kitten", "saturday"], LevenshteinSymbol::Bytes, &cpu).unwrap();
// A `[queries, candidates]` block, query `q` starting at `q * stride`.
let mut distances = [0usize; 4];
let candidates = StringsView::from_slices(&["sitting", "sunday"]);
cpu.scope(|scope| engine.distances(scope, candidates, None, &mut distances, 2))
.unwrap();
assert_eq!(distances[0], 3); // kitten vs sitting
assert_eq!(distances[3], 3); // saturday vs sunday
// A candidate past a bound of 1 reports exactly 2.
let candidates = StringsView::from_slices(&["sitting", "sunday"]);
cpu.scope(|scope| engine.distances(scope, candidates, Some(1), &mut distances, 2))
.unwrap();
assert_eq!(distances[0], 2);
assert_eq!(distances[3], 2);
DropnewPrepares queries with the capabilities of stream, like Capabilities::cpu_enabled or a GPU's Capabilities::cuda_enabled, fixing the capability and, on a GPU, the launch geometry once for every round that follows, on the device stream names, which it may join.pub fn new<Query>(
queries: &[Query],
symbol: LevenshteinSymbol,
stream: &Stream,
) -> Result<Self, Status>
where
Query: AsRef<[u8]>,The queries themselves are read on the host, so they need no device residency; everything
the engine builds from them does. Ice Lake answers a LevenshteinSymbol::Runes batch
through its Skylake kernel, because Ice Lake's byte lanes have no rune arm.
queries_countQueries the batch holds, which is the first axis of every output.pub fn queries_count(&self) -> usizesymbolThe alphabet the batch was prepared over.pub fn symbol(&self) -> LevenshteinSymboldistancesQueues on the stream of scope the edit distances from every prepared query to every candidate, on the capability the constructor fixed.pub fn distances<'scope>(
&'scope mut self,
scope: &'scope Scope<'scope, '_>,
candidates: StringsView<'scope>,
bound: Option<usize>,
distances: &'scope mut [usize],
distances_stride: usize,
) -> Result<(), Status>distances receives a [queries, candidates] block: query q against candidate c lands
at distances[q * distances_stride + c], the stride counting entries rather than bytes and
being at least the candidate count. The round's scratch grows here when a batch needs more
than the last one did, and is never shrunk.
A bound of Some(limit) keeps a distance exact up to limit and reports limit + 1 for
every candidate past it, on every backend, which lets a round stop early. None keeps every
distance exact.
A GPU engine takes candidates and distances in memory its device reaches, such as a
Strings and a Vec in a UnifiedAllocator. A stream of another group than the
engine's is refused with Status::DeviceMemoryMismatch.