Equality has no notion of near

An exact dictionary answers whether appol is present. It cannot say that apple is nearby. To ask that question, first state the allowed operations:

• delete one source symbol;
• insert one target symbol; or
• substitute one source symbol for one target symbol.

Give every operation unit cost. The edit distance $d(x,y)$ is the minimum cost of any operation sequence that turns $x$ into $y$. For appol and apple, one substitution and one insertion suffice, so $d\leq2$. No single permitted edit changes both the fourth character and the length, so $d=2$.

The qualifier “unit cost” is part of the definition, not an implementation detail. A keyboard-neighbor substitution might cost less than an arbitrary one. Opening a long missing span might cost more than extending it. Those policies define different rulers and can rank candidates differently.

Prefixes expose the recurrence

Let $x_1\ldots x_n$ and $y_1\ldots y_m$ be two strings. Define

$$D[i,j]=d(x_1\ldots x_i,\;y_1\ldots y_j).$$

The empty-prefix boundaries are forced:

$$D[i,0]=i,\qquad D[0,j]=j.$$

For nonempty prefixes, inspect the last operation of an optimal correction:

$$D[i,j]=\min\begin{cases} D[i-1,j]+1 & \text{delete }x_i,\\ D[i,j-1]+1 & \text{insert }y_j,\\ D[i-1,j-1]+[x_i\ne y_j] & \text{match or substitute.} \end{cases}$$

Here $[P]$ is 1 when proposition $P$ is true and 0 otherwise.

Why the recurrence is exact

The recurrence is not merely plausible. Take an optimal sequence correcting the first $i$ source symbols to the first $j$ target symbols. Its final action must be one of three kinds.

If it deletes $x_i$, everything before that final deletion must optimally correct $x_{1..i-1}$ to $y_{1..j}$. If a cheaper prefix correction existed, substituting it would make the whole sequence cheaper, contradicting optimality. The insertion case is symmetric. If the final action aligns $x_i$ with $y_j$, the preceding actions optimally correct both shorter prefixes, and the final alignment costs zero for equality or one for substitution.

Thus every optimal sequence appears in one branch and costs at least the minimum. Conversely, append the named final action to an optimal solution for any branch; each branch constructs a valid whole correction. The minimum is therefore both a lower and an upper bound. They meet.

Filling $(n+1)(m+1)$ cells takes $O(nm)$ time. If only the distance is needed, row $i$ reads only row $i-1$ and the already-computed left cell. Keep the shorter string across the row and storage falls to $O(\min(n,m))$.

EDIT-DISTANCE(SOURCE, TARGET)
Input:  strings SOURCE and TARGET, with length(TARGET) ≤ length(SOURCE)
Output: unit-cost edit distance between SOURCE and TARGET

previous ← [0, 1, ..., length(TARGET)]
for i ← 1 to length(SOURCE)
    current[0] ← i
    for j ← 1 to length(TARGET)
        change ← 0
        if SOURCE[i] ≠ TARGET[j]
            change ← 1
        current[j] ← min(previous[j] + 1, current[j - 1] + 1, previous[j - 1] + change)
    SWAP(previous, current)
return previous[length(TARGET)]

Rolling rows discard the path. If an explanation must highlight the edits, retain predecessor choices, recompute a constrained region, or use a divide-and-conquer traceback. Memory savings and witnesses are separate outputs; an API should say which it returns.

A gap has a beginning

Unit edit distance charges a deletion of length $r$ exactly $r$. In many correction policies, one contiguous missing span is likelier than $r$ independent omissions. An affine gap cost separates opening and extending:

$$g(r)=g_o+(r-1)g_e.$$

A direct recurrence asks where every possible gap began, adding a scan over prefix positions. Gotoh's insight is that the past relevant to the next cell has only three states:

• $M[i,j]$: the alignment ends with $x_i$ paired to $y_j$;
• $I[i,j]$: it ends inside a gap in the source; and
• $E[i,j]$: it ends inside a gap in the target.

For minimization, with substitution cost $c(i,j)$:

$$I[i,j]=\min(M[i,j-1]+g_o,\;I[i,j-1]+g_e).$$

$$E[i,j]=\min(M[i-1,j]+g_o,\;E[i-1,j]+g_e).$$

$$M[i,j]=\min(M[i-1,j-1],I[i-1,j-1],E[i-1,j-1])+c(i,j).$$

The exact initialization depends on whether a length-one gap costs $g_o$ or $g_o+g_e$; state that convention and test it. The three-state formulation replaces a search over all gap beginnings with constant work per cell, restoring $O(nm)$ time.

The transferable idea is larger than alignment: if the future needs to know a bounded summary of the past, make that summary an explicit state instead of rescanning history.

A threshold changes the reachable region

A spelling corrector often asks whether $d(x,y)\leq k$, not for every possible distance. Any path from $(0,0)$ to $(i,j)$ needs at least $|i-j|$ insertions or deletions. Therefore cells with $|i-j|>k$ cannot participate in a unit-cost answer at most $k$.

Computing only the diagonal band of width $2k+1$ reduces work to $O(k\min(n,m))$ for the bounded-distance decision, plus boundary handling. A row whose in-band values all exceed $k$ may settle rejection early because nonnegative future costs cannot repair the excess.

This is safe pruning: the rejected cells have a proved lower bound above the threshold. It is not “usually enough” search.

A transposition defines another problem

Fat fingers often reverse adjacent symbols. Damerau's edit model admits transposition. The optimal-string-alignment shortcut adds a local recurrence for adjacent swaps but forbids a substring from being edited more than once. That restriction makes it easier to compute and means it is not the unrestricted Damerau–Levenshtein distance. In particular, optimal-string-alignment distance can violate the triangle inequality.

That distinction matters when a later index prunes by metric balls. A function that looks like a distance but violates a required law can make an optimization silently discard valid answers.

A column can become two bit vectors

Under unit insertion, deletion, and substitution costs, vertically adjacent DP cells differ by only $-1$, $0$, or $+1$. Instead of storing every numeric cell, represent the positive and negative differences as bit vectors. Equality masks mark all pattern positions matching the current text symbol. Word-sized Boolean operations and addition propagate a whole column's frontier at once.

Myers's algorithm uses this relocatable bit-vector representation to process a pattern in $O(\lceil m/w\rceil)$ machine words per text symbol, where $w$ is the word width. For a short dictionary word that fits in one word, one iteration advances all pattern positions together.

Add a position-dependent bonus, an arbitrary substitution matrix, or affine gap state and the tiny step alphabet may disappear. General-score bit-parallel alignment exists, but it carries more machinery. The honest rule is:

representation eligibility = recurrence + cost laws + required output

The problem name alone licenses nothing. A score-only bit-vector path also does not produce edit locations. If the interface promises a highlighted correction path, account for how that witness is recovered.

Distance generates evidence, not decisions

Consider smthin. A distance-only system may prefer a short common word whose edit path is cheap even when a reader intended something. The distance has not malfunctioned; the product asked it to decide a question it does not answer.

A correction pipeline has three distinct stages:

1. Generate candidates without losing plausible corrections.
2. Rank them using edit evidence, corpus frequency, prefix or consonant agreement, corpus-local aliases, and surrounding terms.
3. Decide whether to preserve the literal query, offer alternatives, apply a replacement, or abstain.

Relevance is not confidence. A candidate may rank first by a narrow margin without earning an automatic rewrite. False correction is asymmetric: changing a rare valid identifier can be worse than returning no suggestion.

Keep the literal query as an alternative. Learn abbreviations within the searched corpus rather than importing a timeless universal slang list. Record the edit policy, threshold, candidate source, features, margin, and decision in the query receipt.

Negative results belong beside the winner

Several tempting shortcuts fail for different reasons:

Keep the exhaustive DP as the differential oracle. Generate short strings, cost policies within the supported regime, and thresholds; require the banded or bit-parallel result to equal the oracle. Retain the smallest counterexample when it does not.

Lessons

• “Almost” is defined by operations and costs, not by an algorithm's name.
• Wagner–Fischer follows from the exhaustive cases for an optimal final edit.
• Rolling rows preserve the distance but discard the correction path.
• Affine gaps become quadratic-time manageable when gap history is summarized by a finite state.
• A threshold creates a proved diagonal band; it does not justify heuristic truncation elsewhere.
• Transposition variants have different semantics and laws.
• Bit-vector speed is licensed by unit-cost differences and score-only output.
• Candidate generation, ranking, and correction decisions are separate jobs.
• The simple DP remains the executable specification for every faster path.

Practice

1. Fill the complete unit-cost matrix for kitten and sitting, then trace one optimal correction.
2. Prove that $|i-j|$ is a lower bound on any unit-cost path to cell $(i,j)$.
3. Change substitution cost to two. Which recurrence lines change, and does the rolling-row proof still hold?
4. Choose $g_o=3$ and $g_e=1$. Compare one gap of length four with four gaps of length one under the stated convention.
5. Construct a correction policy with a word-boundary bonus and explain why a unit-cost bit-vector result is not an oracle for it.
6. Design an abstention test using the top two candidate scores. State which empirical calibration it still needs before publication.

References

1. Robert A. Wagner and Michael J. Fischer. “The String-to-String Correction Problem.” Journal of the ACM 21(1), 1974.
2. Osamu Gotoh. “An Improved Algorithm for Matching Biological Sequences.” Journal of Molecular Biology 162(3), 1982.
3. Esko Ukkonen. “Finding Approximate Patterns in Strings.” Journal of Algorithms 6(1), 1985.
4. Fred J. Damerau. “A Technique for Computer Detection and Correction of Spelling Errors.” Communications of the ACM 7(3), 1964.
5. Gene Myers. “A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming.” Journal of the ACM 46(3), 1999.