Python edit distance: rolling rows for insert, delete and replace

Operation contract

The reconciliation helper returns a distance, not an edit script. It computes each cell from insertion, deletion and replacement costs while retaining only the previous row. The shorter label becomes the column dimension to reduce retained cells. Both labels are bounded to 64 code points before work begins.

Failure and ownership boundary

This metric treats a combining accent as a separate code point and assigns every replacement the same cost. It is not a rule for merging customer identities or correcting an account number. Normalize only under an explicit domain policy; Python Unicode normalization: equality is not visual identity and Python longest common subsequence: rolling-row DP and its limits solve related but distinct problems.

Working program

def label_distance(stored, imported):
    if not isinstance(stored, str) or not isinstance(imported, str):
        raise ValueError("text labels required")
    if max(len(stored), len(imported)) > 64:
        raise ValueError("label budget exceeded")
    if len(imported) > len(stored):
        stored, imported = imported, stored
    previous = list(range(len(imported) + 1))
    for row, stored_char in enumerate(stored, 1):
        current = [row]
        for column, imported_char in enumerate(imported, 1):
            current.append(min(current[-1] + 1, previous[column] + 1,
                               previous[column - 1] + (stored_char != imported_char)))
        previous = current
    return previous[-1]

print(label_distance("dispatch", "despatch"))
print(label_distance("", "DEL"))
try:
    label_distance("x" * 65, "DEL")
except ValueError:
    print("label budget rejected")

Output

1
3
label budget rejected

Costs and limits

For lengths m and n, time is O(mn) and working rows use O(min(m,n)) cells. Recovering the actual edit operations needs retained predecessor information or a different reconstruction method.

Common Mistakes

• Code-point distance is not visual-character distance.
• A small edit distance is not permission to merge records.

Connected lessons

Python longest common subsequence: rolling-row DP and its limits, Python Unicode normalization: equality is not visual identity, Python memoization: cache bounded states without hiding recursion depth.

Follow the related contract

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