graphtage.batch_distance

Exact Levenshtein distances for every pair drawn from two collections of strings.

graphtage.levenshtein.levenshtein_distance() prices one pair of strings with a pure Python dynamic program, so a caller that needs the whole cross product of two collections pays the interpreter cost of every matrix cell. This module answers the same question for a whole batch at once, and dispatches to whichever registered backend is fastest for the size of the problem.

The answers are exact. Every backend returns what graphtage.levenshtein.levenshtein_distance() returns for the same pair, and test/test_batch_distance.py pins that agreement over a randomized corpus.

Two backends ship with Graphtage:

python: Calls graphtage.levenshtein.levenshtein_distance() once per pair. It is the oracle that the other backends are checked against, and the fallback for batches too small for vectorization to pay off.
numpy: A batched min-plus scan over numpy arrays. It advances every pair in the batch through one row of its Levenshtein matrix per array pass, so a batch costs as many passes as the longest string is long, rather than as many interpreter steps as the batch has matrix cells.

Set the GRAPHTAGE_BATCH_BACKEND environment variable to a backend name to pin the choice, which is useful for benchmarking one backend against another and for testing that they agree.

Graphtage reaches the batch through cost(), which prices a single pair the way graphtage.levenshtein.levenshtein_distance() does but answers from a pre-computed block when one holds the pair. graphtage.multiset.MultiSetEdit and graphtage.levenshtein.EditDistance each face a cross product of node pairs whose edits are constructed one at a time, so they call preprice() or preprice_product() before constructing any of them and let every later cost() read the answer out of the block.

batch_distance classes

BatchBackend

class graphtage.batch_distance.BatchBackend(*args, **kwargs)

Bases: Protocol

A strategy for computing the Levenshtein distance of every pair in a batch.

__init__(*args, **kwargs)

distances(pairs: Sequence[tuple[str, str] | tuple[bytes, bytes]]) → ndarray

Computes the Levenshtein distance of each pair.

Parameters:: pairs – The pairs to price. Every pair has two sides of the same type, and neither side is empty.
Returns:: A one-dimensional array of numpy.int64 holding one distance per pair, in the order the pairs were given.
Return type:: numpy.ndarray

is_available() → bool: Returns whether this backend can run in the current environment.

min_pairs: int: The smallest batch this backend accepts. The dispatcher skips it for anything smaller.

name: str: The name this backend is registered under, and that callers and the environment variable select it by.

speed_rank: int

Relative throughput, higher being faster.

The dispatcher picks the highest-ranked available backend whose BatchBackend.min_pairs the batch meets.

NumpyBackend

class graphtage.batch_distance.NumpyBackend

Bases: object

A batched min-plus scan over numpy arrays.

The batch is prepared in three steps before _scan() sees it:

Each pair is oriented so that its shorter string drives the row loop, which is free because the Levenshtein distance is symmetric. That gives the fewest, widest array passes.
Pairs of str and pairs of bytes are separated, because the two encodings assign different meanings to the same number.
Pairs are sorted by length and split into chunks, so that padding one long string does not widen the rows of every short pair that shares its batch.

__init__()

distances(pairs: Sequence[tuple[str, str] | tuple[bytes, bytes]]) → ndarray

Computes the Levenshtein distance of each pair.

Parameters:: pairs – The pairs to price.
Returns:: One distance per pair, in the order the pairs were given.
Return type:: numpy.ndarray

is_available() → bool: Returns True, because numpy is a hard dependency of Graphtage.

min_pairs = 32

name = 'numpy'

speed_rank = 10

PythonBackend

class graphtage.batch_distance.PythonBackend

Bases: object

The reference backend, which applies graphtage.levenshtein.levenshtein_distance() to each pair.

__init__()

distances(pairs: Sequence[tuple[str, str] | tuple[bytes, bytes]]) → ndarray

Computes the Levenshtein distance of each pair, one at a time.

Parameters:: pairs – The pairs to price.
Returns:: One distance per pair, in the order the pairs were given.
Return type:: numpy.ndarray

is_available() → bool: Returns True, because the pure Python backend has no requirements.

min_pairs = 0

name = 'python'

speed_rank = 0

batch_distance functions

all_flat

graphtage.batch_distance.all_flat(a: Sequence[str | bytes], b: Sequence[str | bytes], *, backend: str | None = None) → ndarray

Computes the Levenshtein distance of two collections position by position.

Parameters:

a – The strings to measure from.
b – The strings to measure to, the same number of them as a has.
backend – The name of the backend to use. The default, None, reads GRAPHTAGE_BATCH_BACKEND from the environment and otherwise picks the fastest backend that will take the batch.

Returns:

A one-dimensional array of numpy.int64 of length len(a) in which entry i equals levenshtein_distance(a[i], b[i]).

Return type:

numpy.ndarray

Raises:

TypeError – If a string is neither str nor bytes, or if a pair mixes the two.
ValueError – If the two collections differ in length, or if backend names a backend that is not registered or not available here.

all_pairs

graphtage.batch_distance.all_pairs(from_strings: Sequence[str | bytes], to_strings: Sequence[str | bytes], *, backend: str | None = None) → ndarray

Computes the Levenshtein distance for every pair drawn from two collections.

Repeated strings are computed once and shared, so a collection with few distinct values costs little more than the values themselves.

Parameters:

from_strings – The strings to measure from, which index the rows of the result.
to_strings – The strings to measure to, which index the columns of the result.
backend – The name of the backend to use. The default, None, reads GRAPHTAGE_BATCH_BACKEND from the environment and otherwise picks the fastest backend that will take the batch.

Returns:

A (len(from_strings), len(to_strings)) array of numpy.int64 in which entry (i, j) equals levenshtein_distance(from_strings[i], to_strings[j]).

Return type:

numpy.ndarray

Raises:

TypeError – If a string is neither str nor bytes, or if a pair mixes the two.
ValueError – If backend names a backend that is not registered or not available here.

available_backends

graphtage.batch_distance.available_backends() → tuple[str, ...]

Returns the names of the backends usable in this environment, fastest first.

Returns:: The names, ordered by descending BatchBackend.speed_rank and then by name.
Return type:: Tuple[str, …]

clear

graphtage.batch_distance.clear() → None

Discards every pre-priced block.

cost() answers the same afterwards, because the blocks only hold what it would otherwise compute.

cost

graphtage.batch_distance.cost(a: str | bytes, b: str | bytes) → int

Returns the Levenshtein distance between two strings, reading a pre-priced block when one holds it.

This is what graphtage.levenshtein.exact_string_distance() calls, and it returns exactly what graphtage.levenshtein.levenshtein_distance() returns for the same pair.

A pair that no block holds is computed and not recorded. Recording it would make the cache grow with the number of distinct pairs a diff asks about, which is the whole cross product, and nothing would ever evict it. Blocks are installed deliberately, by a caller that knows it is about to ask for a whole rectangle of pairs.

Parameters:

a – The string to measure from.
b – The string to measure to.

Returns:

The Levenshtein edit distance between the two strings.

Return type:

int

preprice

graphtage.batch_distance.preprice(pairs: Sequence[tuple[str, str] | tuple[bytes, bytes]]) → None

Prices a list of pairs and keeps the answers for cost().

This is the form for a caller whose pairs are not a whole rectangle, such as graphtage.multiset.MultiSetEdit, which draws one pair from two leaves but two from two key/value pairs. Pairs that mix str with bytes are left out and go through the scalar path.

Nothing is installed for a rectangle larger than PREPRICE_MAX_CELLS.

Parameters:: pairs – The pairs to price, which may repeat.

preprice_product

graphtage.batch_distance.preprice_product(from_strings: Sequence[str | bytes], to_strings: Sequence[str | bytes]) → None

Prices every pair drawn from two collections and keeps the answers for cost().

Call this before constructing the edits that will ask for those pairs. The block outlives this call, because the edits that read it are constructed and tightened long afterwards.

Nothing is installed for a rectangle larger than PREPRICE_MAX_CELLS, and the pairs then go through the scalar path one at a time.

Parameters:

from_strings – The strings to measure from, which may repeat.
to_strings – The strings to measure to, which may repeat.

register_backend

graphtage.batch_distance.register_backend(backend: BatchBackend) → None

Adds a backend to the registry.

Parameters:: backend – The backend to register. Its BatchBackend.name becomes the value that the backend argument and the GRAPHTAGE_BATCH_BACKEND environment variable accept.
Raises:: ValueError – If a backend of that name is already registered.