Python edit scripts: reconstruct and verify an alignment instead of only counting it

Last updated: 30 Sept 20264 min read

tutorial

An edit script records concrete insert, delete and replace operations that transform a source sequence into a target sequence.

Download Python source kit

Operation contract

The bounded label aligner keeps a complete distance matrix, then walks backward under an explicit tie policy: match or replace first, then deletion, then insertion. It returns an ordered script. Applying that script validates consumed source symbols and produces the target label, which checks the reconstruction rather than trusting the distance alone.

Failure and ownership boundary

The operations use code points, not grapheme clusters, and they are not permission to rewrite account identifiers. Several minimum scripts can exist; the chosen tie policy makes this fixture repeatable but does not establish one universally correct human correction. Python edit distance: rolling rows for insert, delete and replace uses less storage when only the number is required.

Working program

def align_labels(source, target):
    if not isinstance(source, str) or not isinstance(target, str) or max(len(source), len(target)) > 32:
        raise ValueError("bounded labels required")
    costs = [[0] * (len(target) + 1) for _ in range(len(source) + 1)]
    for row in range(len(source) + 1): costs[row][0] = row
    for column in range(len(target) + 1): costs[0][column] = column
    for row in range(1, len(source) + 1):
        for column in range(1, len(target) + 1):
            costs[row][column] = min(costs[row - 1][column] + 1, costs[row][column - 1] + 1,
                                     costs[row - 1][column - 1] + (source[row - 1] != target[column - 1]))
    row, column = len(source), len(target); reversed_steps = []
    while row or column:
        if row and column and costs[row][column] == costs[row - 1][column - 1] + (source[row - 1] != target[column - 1]):
            kind = "keep" if source[row - 1] == target[column - 1] else "replace"
            reversed_steps.append((kind, source[row - 1], target[column - 1])); row -= 1; column -= 1
        elif row and costs[row][column] == costs[row - 1][column] + 1:
            reversed_steps.append(("delete", source[row - 1], "")); row -= 1
        else:
            reversed_steps.append(("insert", "", target[column - 1])); column -= 1
    return costs[-1][-1], list(reversed(reversed_steps))

def apply_alignment(source, steps):
    position = 0; output = []
    for kind, before, after in steps:
        if kind not in {"keep", "replace", "delete", "insert"}:
            raise ValueError("unknown alignment operation")
        if kind != "insert":
            if position >= len(source) or source[position] != before:
                raise ValueError("alignment source mismatch")
            position += 1
        if kind != "delete": output.append(after)
    if position != len(source):
        raise ValueError("alignment left source unconsumed")
    return "".join(output)

distance, steps = align_labels("DEL", "DILHI")
print("distance:", distance)
print("reconstructed:", apply_alignment("DEL", steps))
print("edited steps:", sum(kind != "keep" for kind, before, after in steps))

Output

distance: 3
reconstructed: DILHI
edited steps: 3

Costs and limits

For lengths m and n, matrix construction costs O(mn) time and storage; reconstruction adds O(m+n) steps. The shorter rolling-row distance helper saves matrix storage but cannot directly supply this predecessor walk.

Common Mistakes

Verify that applying the returned script consumes the source and yields the target.
A minimum code-point edit is not a domain-approved identifier change.

Connected lessons

Python edit distance: rolling rows for insert, delete and replace, Python Unicode normalization: equality is not visual identity, Python longest common subsequence: rolling-row DP and its limits.

python

edit-script