Edit distance

Ordinary Levenshtein distance allows one-element insertion, deletion and substitution at unit cost. It minimizes operations rather than counting unequal fixed positions, because insertion can shift later alignment.

Changing cat to cut needs one substitution. Adjacent transposition is not a separate one-step operation in this version. Adding it, weighting errors differently or changing the underlying character units defines another cost model.

References: [1]

A table stores optimum costs for prefix or suffix pairs. Each cell compares deletion, insertion and matching or substitution, adding the current operation cost before taking the minimum. Empty-input boundaries insert or delete the remaining elements.

Princeton’s alignment exercise uses gap cost2 and mismatch cost1 with the same three-way structure. The recurrence pattern is reusable, but those weighted scores are not ordinary unit-cost Levenshtein distances.

References: [2] [1]

For nonempty length-m and length-n inputs, the standard table takes O(mn) time and space. Scores alone need adjacent rows and linear auxiliary space; an edit script requires retained choices or specialized reconstruction. Several scripts may tie.

Distance can rank spelling or alignment candidates, but nearby strings need not share meaning or identity. Thresholds depend on length and element units, and scores from different cost models should not be mixed without explanation.

References: [1] [3] [2]