graphtage.levenshtein

An “online”, “constructive” implementation of the Levenshtein distance metric.

The algorithm starts with an unbounded mapping and iteratively improves it until the bounds converge, at which point the optimal edit sequence is discovered.

levenshtein classes

EditDistance

class graphtage.levenshtein.EditDistance(from_node: TreeNode, to_node: TreeNode, from_seq: Sequence[TreeNode], to_seq: Sequence[TreeNode], insert_remove_penalty: int = 1, *, preprice: bool = True)

Bases: SequenceEdit

An edit that computes the minimum sequence of sub-edits necessary to transform one node to another.

The edits used to transform the source sequence to the target sequence are graphtage.Match, graphtage.Remove, and graphtage.Insert.

The algorithm works by iteratively constructing the Levenshtein matrix one diagonal at a time, starting from the upper left cell and ending at the lower right cell. Each successive call to EditDistance.tighten_bounds() constructs a new diagonal of the matrix and fully tightens the bounds of its edits. Once the lower right cell is expanded, the matrix is complete and the optimal sequence of edits can be reconstructed.

Bounds of this edit are updated after each diagonal is added by observing that the final cost is bounded above by the minimum cost of an edit in the last-expanded diagonal. This results in a monotonically decreasing upper bound.

__init__(from_node: TreeNode, to_node: TreeNode, from_seq: Sequence[TreeNode], to_seq: Sequence[TreeNode], insert_remove_penalty: int = 1, *, preprice: bool = True)

Initializes the edit distance edit.

Parameters:

  • from_node – The node that will be transformed.

  • to_node – The node into which from_node will be transformed.

  • from_seq – A sequence of nodes that comprise from_node.

  • to_seq – A sequence of nodes that comprise to_node.

  • insert_remove_penalty – The penalty for inserting or removing a node (default is 1).

  • preprice – Whether to price the string pairs of the two sequences’ leaves in one batch before any cell of the matrix is built. Pass False when the elements are single characters, as graphtage.string_edit_distance() does: a character-level lattice is itself an EditDistance, and collecting its pairs would cost a pass over every cell of every string that gets rendered in exchange for a batch of one-character pairs that cost nothing to begin with.

__iter__() → Iterator[Edit]

Returns an iterator over this edit’s sub-edits.

Returns:

The result of AbstractCompoundEdit.edits()

Return type:

Iterator[Edit]

__lt__(other)

Tests whether the bounds of this edit are less than the bounds of other.

_best_match(row: int, col: int) → tuple[int, int, Edit]

Selects the predecessor cell that reaches this cell of the Levenshtein matrix most cheaply.

Each candidate is scored by the accumulated cost of its predecessor plus the cost of the edit that transitions from that predecessor to this cell. The number of edits along the path is the secondary key, which prefers a single substitution over an insertion paired with a removal of equal total cost.

Ties on both keys are broken by direction, in this fixed order: the diagonal (a substitution) wins over both borders, and the border insertion wins over the border removal. Reconstruction walks the matrix backwards, so preferring the insertion here places the removal earlier in the forward edit sequence, matching the convention of listing deletions before additions. This order is part of the output contract: changing it changes the edit sequence for inputs that have several optimal alignments.

Parameters:
Returns:

The row and column of the chosen predecessor, and the transition edit.

Return type:

Tuple[int, int, Edit]

_debug_tighten_bounds() → bool

Adds debugging assertions when tightening bounds; for debugging only

static _exact_cost(edit: Edit) → int

Tightens an edit until its bounds are definitive and returns its exact cost.

Parameters:

edit – The edit to price.

Returns:

The exact cost of the edit.

Return type:

int

Raises:

ValueError – If the edit cannot be tightened to a definitive bound.

bounds() → Range

Calculates bounds on the cost of this edit.

If the Levenshtein matrix has been fully constructed, return the cost of the lower right cell.

If the matrix is incomplete, then use super().bounds().lower_bound as the lower bound and the minimum cost in the last completed matrix diagonal as the upper bound.

Returns:

The bounds on the cost of this edit.

Return type:

Range

costs
edit_matrix: list[list[Edit | None]]
edits() → Iterator[Edit]

Returns an iterator over this edit’s sub-edits

from_node: TreeNode
from_seq: Sequence[TreeNode]
has_non_zero_cost() → bool

Returns whether this edit has a non-zero cost.

This will tighten the edit’s bounds until either its lower bound is greater than zero or its bounds are definitive.

initial_bounds: Range
invalidate_bounds_cache()

Invalidate the cached bounds. Call this when bounds may have changed.

is_complete() → bool

An edit distance edit is only complete once its Levenshtein edit matrix has been fully constructed.

on_diff(from_node: EditedTreeNode)

A callback for when an edit is assigned to an EditedTreeNode in TreeNode.diff().

This default implementation adds the edit to the node, and recursively calls Edit.on_diff() on all of the sub-edits:

from_node.edit = self
from_node.edit_list.append(self)
for edit in self.edits():
    edit.on_diff(edit.from_node)
Parameters:

from_node – The edited node that was added to the diff

path_costs
penalty: int
print(formatter: GraphtageFormatter, printer: Printer)

Prints this edit.

This is equivalent to:

formatter.get_formatter(self.sequence)(printer, self.sequence)
reversed_shared_suffix: list[tuple[TreeNode, TreeNode]]
property sequence: SequenceNode

Returns the sequence being edited.

This is a convenience function solely to aid in automated type checking. It is equivalent to:

typing.cast(SequenceNode, self.from_node)
shared_prefix: list[tuple[TreeNode, TreeNode]]
tighten_bounds() → bool

Tightens the bounds of this edit, if possible.

If the Levenshtein matrix is not yet complete, construct and fully tighten the next diagonal of the matrix.

to_node
to_seq: Sequence[TreeNode]
property valid: bool

Returns whether this edit is valid

levenshtein functions

exact_string_distance

graphtage.levenshtein.exact_string_distance(s: str | bytes, t: str | bytes) → int

Computes the Levenshtein distance between two strings without building an edit script.

EditDistance computes the same number, but it does so by materializing one graphtage.TreeNode per character and one live graphtage.Edit per cell of the Levenshtein matrix. Callers that only need the cost, such as graphtage.StringEdit and graphtage.LeafNode.edits(), go through this function instead and leave the lattice unbuilt.

Both arguments may be str or bytes, in either combination. Indexing bytes yields int byte values, which never compare equal to a str character, so a mixed pair costs one per aligned position exactly as the lattice charges for it.

The answer comes from graphtage.batch_distance.cost(), which reads a block that was priced in advance when one holds this pair and computes the pair when none does. That is how a caller facing a whole cross product of pairs pays for them in one vectorized batch rather than one at a time, and the number is the same either way.

Parameters:

  • s – the string from which to match.

  • t – the string to which to match.

Returns:

The Levenshtein edit distance metric between the two strings.

Return type:

int

levenshtein_distance

graphtage.levenshtein.levenshtein_distance(s: str | bytes, t: str | bytes) → int

Canonical implementation of the Levenshtein distance metric.

Parameters:

  • s – the string from which to match

  • t – the string to which to match

Returns:

The Levenshtein edit distance metric between the two strings.

Return type:

int