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)

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)

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

__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

levenshtein_distance

graphtage.levenshtein.levenshtein_distance(s: str, t: str) → 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