Edit Distances

§ Batch Engines

Three engines prepare one set of queries once and score it against as many collections of candidates as a caller has. Preparation fixes the alphabet or the vocabulary, resolves the SIMD tier, and takes the memory the rounds reuse; every later call only streams candidates past what is already there. Each engine writes into a writable buffer the caller supplies as out, so nothing is allocated per round and a round can fill one slice of a larger matrix.

Queries, candidates, and haystacks all arrive as sz.Strings, and every out buffer is any writable object supporting the buffer protocol — a NumPy array, an array.array, or a plain memoryview. Engine calls release the GIL, and calls into one engine take turns on its lock, so build one engine per thread to score in parallel.

§ Edit Distances

LevenshteinEngine(queries, symbol='bytes') computes unit-cost Levenshtein distances from every prepared query to every candidate. symbol='bytes' counts byte edits, symbol='runes' counts UTF-8 rune edits, and the choice is fixed at construction because it picks the mask layout as well as the tier.

distances(candidates, out, *, bound=None) fills a [queries, candidates] block of pointer-width unsigned integers, contiguous along its candidate axis. A bound keeps a distance exact up to it and reports bound + 1 for every candidate past it, on every backend, so a round can stop early; None keeps every distance exact.

import stringzilla as sz

engine = sz.LevenshteinEngine(sz.Strings(["hello", "world"]))
out = memoryview(bytearray(4 * 8)).cast("Q", (2, 2))
engine.distances(sz.Strings(["hallo", "word"]), out)
assert out[0, 0] == 1           # hello -> hallo

# Bounded at 0, any candidate that differs reports exactly 1.
engine.distances(sz.Strings(["hallo", "word"]), out, bound=0)
assert out[0, 0] == 1 and out[0, 1] == 1

# UTF-8 rune distances, where one accented codepoint is one edit rather than two.
runes = sz.LevenshteinEngine(sz.Strings(["café"]), symbol="runes")
out = memoryview(bytearray(8)).cast("Q", (1, 1))
runes.distances(sz.Strings(["cafe"]), out)
assert out[0, 0] == 1

§ Window Overlap

OverlapEngine(queries, widths) hashes every query’s fixed-width byte n-grams into one B-tree per query, at every width in widths, and probes that forest with each candidate’s own windows. A score is the share of a candidate’s windows the query also spells, in [0, 1], so it is asymmetric: swapping the two sides changes the answer when either repeats a window. Widths need not form a doubling chain, and a width past a text scores zero for every pair it spans.

scores(candidates, out, *, radius=None) fills a [queries, candidates, widths] block of 32-bit floats, contiguous along its width axis. A pair’s distance is the windows it misses over its longer side’s, summed over every width, and a radius in [0, 1] keeps every pair within it exact; a pair past it scores 0.0 at every width, on every backend, and None keeps every score exact.

import stringzilla as sz

engine = sz.OverlapEngine(sz.Strings(["the quick brown fox"]), [4, 8])
out = memoryview(bytearray(1 * 2 * 2 * 4)).cast("f", (1, 2, 2))
engine.scores(sz.Strings(["the quick brown cat", "nothing alike"]), out)
assert all(0.0 <= out[0, c, w] <= 1.0 for c in range(2) for w in range(2))

§ Multi-Pattern Matching

SubstringsEngine(needles, case_sensitivity='cased', overlap_policy='overlapping', hot_states=None, matches_budget=0) compiles a whole vocabulary into one Aho-Corasick automaton, so every haystack answers every needle in a single pass whatever the vocabulary size.

The policy belongs to the engine rather than to a call, because the round’s arena is sized for one cover and holds no other. Four verbs share the compiled automaton:

A capacity too small is not an error for find or replace: the boundaries and the report are filled either way, which is what sizes the next call. Passing None for matches or target makes the call a pure size query. engine.report is a dict of four counts from the last round — matches_emitted is the truth whatever the outputs could hold, matches_stored what was written, target_length what a rewrite needs, and shortfall what did not fit.

import stringzilla as sz

engine = sz.SubstringsEngine(sz.Strings(["he", "she", "his", "hers"]))
haystacks = sz.Strings(["ushers", "hershey"])

counts = memoryview(bytearray(2 * 8)).cast("Q")
engine.counts(haystacks, counts)
assert counts[0] + counts[1] == 7

matches = memoryview(bytearray(8 * 4 * 8)).cast("Q", (8, 4))
offsets = memoryview(bytearray(3 * 8)).cast("Q")
engine.find(haystacks, matches, offsets)

cover = sz.SubstringsEngine(sz.Strings(["he", "she"]), overlap_policy="leftmost-longest")
target = memoryview(bytearray(32))
offsets = memoryview(bytearray(3 * 8)).cast("Q")
cover.replace(haystacks, sz.Strings(["HE", "SHE"]), target, offsets)
assert bytes(target[offsets[1]:offsets[2]]) == b"HErSHEy"

bm25_scores treats the vocabulary itself as the query, needle_weights[i] carrying needle i’s IDF or boost, and writes one score per haystack without ever materializing a per-term frequency row. Term frequencies are raw overlapping counts, so the engine’s own overlap policy does not apply there. document_lengths defaults to each haystack’s byte length, and average_document_length is required whenever length_normalization is positive.

import stringzilla as sz

engine = sz.SubstringsEngine(sz.Strings(["cat", "dog"]))
weights = memoryview(bytearray(2 * 4)).cast("f")
weights[0], weights[1] = 1.0, 1.0
out = memoryview(bytearray(2 * 4)).cast("f")
engine.bm25_scores(sz.Strings(["cat and dog", "nothing here"]), weights, out, average_document_length=10.0)
assert out[1] == 0.0

§ Engines on a GPU

Every engine constructor takes keyword-only capabilities= and stream=. capabilities= defaults to every CPU capability, clamped to what this CPU runs, and a GPU producer’s mask, like sz.cuda_capabilities_enabled(0), builds the engine on that vendor. It prepares the batch where a kernel reaches it and resolves the launch geometry once, and every later round of that engine runs there. stream= is a cudaStream_t, a hipStream_t or an id<MTLCommandQueue> as an integer, which names the device, or None for the default stream of the default device, and it carries only the preparation: the engine does not keep it; a CPU engine takes no stream. SubstringsEngine also takes a haystacks_budget and OverlapEngine a candidates_budget, the most one round may carry on a device, which the CPU ignores. The device arena is sized once from those budgets and no verb allocates, so a substrings round past its budget is refused, while CUDA overlap keeps no per-candidate arena and ignores its budget.

Every verb then takes its own keyword-only stream, so one engine can be scored from several streams. LevenshteinEngine and OverlapEngine keep no round state on the device, so their rounds may run on any number of streams at once. SubstringsEngine rounds share one arena and one report, so the caller orders them, on one stream or with events between two.

A device engine reads its inputs in place, so they come from sz.Strings(texts).copy(gpu), and a host Strings raises BufferError, while a host engine reads a copy made for any capabilities. sz.cuda_stream_init(ordinal) makes a stream on any device, and sz.cuda_stream_free(stream) frees it once synchronized, with rocm_ and metal_ twins.

import stringzilla as sz

gpu = sz.cuda_capabilities_enabled(0)
stream = sz.cuda_stream_init(0)
engine = sz.LevenshteinEngine(sz.Strings(["kitten", "saturday"]), capabilities=gpu, stream=stream)
candidates = sz.Strings(["sitting", "sunday"]).copy(gpu, stream)
engine.distances(candidates, unified_out, stream=stream)
sz.synchronize(gpu, stream)  # before `unified_out` is read or `candidates` dropped
sz.cuda_stream_free(stream)

A device round enqueues and returns, so its out buffer has to be memory the device reaches, has to outlive the launch, and must not be read before the caller joins the stream. A plain NumPy array is host memory and is refused; a NumPy array over a cudaMallocManaged allocation works. SubstringsEngine.report is written by the device too, so it obeys the same rule. A host engine ignores stream, imposes no such requirement, and has always finished writing by the time it answers.