# Edit Distances

> StringZilla for Python

### 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.

| Engine              | Constructed from                               | Scores with                                                   |
| :------------------ | :--------------------------------------------- | :------------------------------------------------------------ |
| `LevenshteinEngine` | a batch of query strings and a symbol alphabet | `distances(candidates, out, bound=None)`                      |
| `OverlapEngine`     | a batch of query strings and window widths     | `scores(candidates, out, radius=None)`                        |
| `SubstringsEngine`  | a vocabulary of needles and an overlap policy  | `counts`, `find`, `replace`, and `bm25_scores` over haystacks |

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.

```python
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.

```python
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.

| Argument           | Default         | Meaning                                                                               |
| :----------------- | :-------------- | :------------------------------------------------------------------------------------ |
| `needles`          | required        | `sz.Strings` vocabulary; an empty needle is refused, valid UTF-8 needed when folding. |
| `case_sensitivity` | `'cased'`       | `'cased'` matches bytes, `'uncased'` folds both sides under full Unicode folding.     |
| `overlap_policy`   | `'overlapping'` | `'overlapping'`, `'leftmost-longest'`, or `'leftmost-first'`.                         |
| `hot_states`       | `None`          | States kept in the dense hot rows; `None` sizes them to a fixed byte budget.          |
| `matches_budget`   | `0`             | Matches one round may emit, read by a device tier only; `0` takes its default.        |

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:

| Call                                                | Writes                                                                                  |
| :-------------------------------------------------- | :-------------------------------------------------------------------------------------- |
| `counts(haystacks, out)`                            | One pointer-width count per haystack.                                                   |
| `find(haystacks, matches, offsets)`                 | One `(haystack, needle, offset, length)` row per match, plus one boundary per haystack. |
| `replace(haystacks, replacements, target, offsets)` | The rewritten haystacks into one target buffer, plus one boundary per haystack.         |
| `bm25_scores(haystacks, needle_weights, out, ...)`  | One 32-bit score per haystack, the vocabulary being the query.                          |

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.

```python
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.

```python
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.

```python
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.

`from stringzilla import LevenshteinEngine`

## LevenshteinEngine

Prepare a batch of queries once and score it against many collections of candidates.

```python
class LevenshteinEngine
```

Unit-cost Myers bit-parallel edit distance: every query is packed into match masks at
construction, and each round streams the candidates past them.

Example:

engine = sz.LevenshteinEngine(sz.Strings(['hello']), symbol='bytes')
out = memoryview(bytearray(8)).cast('Q', (1, 1))
engine.distances(sz.Strings(['hallo']), out)
out[0, 0]
1

## LevenshteinEngine

```python
LevenshteinEngine(
    queries: Strings,
    symbol: str = 'bytes',
    *,
    capabilities: Capability | None = None,
    stream: int | None = None,
)
```

## distances

distances(candidates, out, *, bound=None, stream=None) -> None

```python
def distances(
    candidates: Strings,
    out: _Buffer,
    *,
    bound: int | None = None,
    stream: int | None = None,
) -> None
```

Score every prepared query against every candidate, into `out`.

Example:

engine = sz.LevenshteinEngine(sz.Strings(['hello', 'world']))
out = memoryview(bytearray(32)).cast('Q', (2, 2))
engine.distances(sz.Strings(['hallo', 'word']), out)
out[0, 0]
1

- `candidates`: Texts forming the matrix columns, from [`Strings.copy`](https://www.unum.cloud/docs/stringzilla/python/hashing-and-checksums.md#copy) on a GPU.
- `out`: Writable 2-D buffer of pointer-width unsigned integers like numpy.uintp,
at least (len(queries), len(candidates)), contiguous along its candidate axis.
- `bound`: The largest distance reported exactly. A candidate past it reports
exactly bound + 1, and None keeps every distance exact.
- `stream`: A stream of the engine's device as an integer, or None for the
default. A device engine enqueues there and returns, so `out` must be device-reachable
and read only after the caller joins the stream; a host engine ignores it.